Official Analysis

Explanation

Since M=10M = 10 is given, we can iterate through all 2102^{10} possible subsets of air conditioners. For each of them, we check if this subset of air conditioners satisfy the requirements of the cows by iterating through all possible positions i∈[1;100]i \in [1;100]. For each position ii, we can iterate through all available air conditioners in the current subset to find out the temperature reduced at ii and iterate through all cows to find the cow at this position and its demand. If the requirement at each position is fulfilled, we update the minimal cost accordingly.

We can generate subsets with recursion or bitmasks: both ways are presented below.

Solution 1: Subset with Recursion

Time Complexity: O(2M⋅100⋅(M+N))\mathcal{O}(2^M \cdot 100 \cdot (M + N))

C++

#include <bits/stdc++.h>
using namespace std;


int N, M;
// {s, t, c}
vector<array<int, 3>> cows;
// {a, b, p, m}
vector<array<int, 4>> air_conditioners;
// uses[i] == true: the i-th air conditioner is used
vector<bool> uses;

Java

import java.io.*;
import java.util.*;


public class AirConditioningII {
	static int N, M;
	// {s, t, c}
	static List<int[]> cows = new ArrayList<>();
	// {a, b, p, m}
	static List<int[]> airConditioners = new ArrayList<>();
	// uses[i] == true: the i-th air conditioner is used

Python

cows = []  # List to store {s, t, c} for each cow
air_conditioners = []  # List to store {a, b, p, m} for each air conditioner


# the minimum amount of money needed to keep all cows comfortable
min_cost = float("inf")




def update():
	"""
	Based on 'uses', determine if the current subset of air conditioners suffices

Solution 2: Subset with Bitmask

Time Complexity: O(2M⋅100⋅(M+N))\mathcal{O}(2^M \cdot 100 \cdot (M + N))

C++

#include <bits/stdc++.h>
using namespace std;


/** @return if the given AC units satisfy the constraints of the cows */
bool check(vector<array<int, 3>> &cows, vector<array<int, 4>> &air_conditioners) {
	// iterate through all positions to check if the current subset is feasible
	for (int i = 1; i <= 100; i++) {
		// iterate through air conditioners to find the current cooling units
		int cooling = 0;
		for (int j = 0; j < air_conditioners.size(); j++) {

Java

import java.io.*;
import java.util.*;


public class AirCownditioning {
 	Code Snippet: Cow and AC Class (Click to expand)


	static final int MAX_STALL = 100;


	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

Python

from typing import NamedTuple


MAX_STALL = 100




class Cow(NamedTuple):
	start: int
	end: int
	cool_req: int

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum