Notice that the number of conditioners is low, motivating us to think about a brute force solution.
Let's count how many distinct sets of conditioners FJ can use to cool down the cows. For every conditioner, we have $2$ choices: use it or don't use it. Therefore, over all $M$ conditioners, there are $2^M$ sets of conditioners FJ can use, which happens to be relatively small at around 1000 subsets.
Thus, we can just generate all possible subsets of conditioners we can use, and for each one, check if it makes all cows comfortable. If it does, and the total cost is less than what our answer was, we update our answer.
Some implementation notes:
The overall time complexity of this solution is $\mathcal{O}(2^M\cdot (M+N) \cdot 100)$.
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> cowlocs;
vector<int> comfort;
vector<pair<int, int>> conditioners;
vector<int> cost;
vector<int> power;
int ans = 1e9;
int check(string subset) {
vector<int> cold(101); // generate coldness of all points
for (int i = 1; i <= 100; i++) {
for (int j = 0; j < conditioners.size(); j++) {
if (subset[j] == '1' && conditioners[j].first <= i &&
conditioners[j].second >= i) {
cold[i] += power[j];
}
}
}
bool works = true;
for (int i = 0; i < cowlocs.size(); i++) {
for (int j = cowlocs[i].first; j <= cowlocs[i].second; j++) {
if (cold[j] < comfort[i]) works = false; // check if comfortable
}
}
int price = 0;
for (int i = 0; i < subset.size(); i++) {
if (subset[i] == '1')
price += cost[i]; // calculate price of conditioners used
}
if (works) return price;
return 1e9; // does not work
}
void build_subset(string curr, int m) {
if (curr.size() == m) {
// full subset of conditioners
ans = min(ans, check(curr));
} else {
build_subset(curr + "1", m); // use conditioner
build_subset(curr + "0", m); // skip it
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
int s, t, c;
cin >> s >> t >> c;
cowlocs.push_back({s, t});
comfort.push_back(c);
}
for (int i = 0; i < m; i++) {
int a, b, p, c;
cin >> a >> b >> p >> c;
conditioners.push_back({a, b});
power.push_back(p);
cost.push_back(c);
}
build_subset("", m);
cout << ans << endl;
}
Here are some solutions that don't use recursion:
Nick Wu's Python code:
n, m = (int(x) for x in input().split())
regions = []
for _ in range(n):
regions.append([int(x) for x in input().split()])
acs = []
for _ in range(m):
acs.append([int(x) for x in input().split()])
ret = sum([x[3] for x in acs])
for used in range(2**m):
cool = [0] * 101
cost = 0
for i in range(m):
if used & (2 ** i):
cost += acs[i][3]
for x in range(acs[i][0], acs[i][1] + 1):
cool[x] += acs[i][2]
valid = True
for i in range(n):
valid = valid and all([cool[x] >= regions[i][2] for x in range(regions[i][0], regions[i][1] + 1)])
if valid:
ret = min(ret, cost)
print(ret)
Danny Mittal's Java code:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class AirCownditioningII {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(in.readLine());
int n = Integer.parseInt(tokenizer.nextToken());
int m = Integer.parseInt(tokenizer.nextToken());
CowInterval[] cowIntervals = new CowInterval[n];
for (int j = 0; j < n; j++) {
tokenizer = new StringTokenizer(in.readLine());
int from = Integer.parseInt(tokenizer.nextToken());
int to = Integer.parseInt(tokenizer.nextToken());
int requiredCoolness = Integer.parseInt(tokenizer.nextToken());
cowIntervals[j] = new CowInterval(from, to, requiredCoolness);
}
AirCownditioner[] airCownditioners = new AirCownditioner[m];
for (int j = 0; j < m; j++) {
tokenizer = new StringTokenizer(in.readLine());
int from = Integer.parseInt(tokenizer.nextToken());
int to = Integer.parseInt(tokenizer.nextToken());
int power = Integer.parseInt(tokenizer.nextToken());
int money = Integer.parseInt(tokenizer.nextToken());
airCownditioners[j] = new AirCownditioner(from, to, power, money);
}
int answer = m*1000;
for (int mask = 0; mask < 1 << m; mask++) {
int[] numberLine = new int[101];
int totalCost = 0;
for (int j = 0; j < m; j++) {
if ((mask & (1 << j)) != 0) {
totalCost += airCownditioners[j].money;
AirCownditioner airCownditioner = airCownditioners[j];
for (int x = airCownditioner.from; x <= airCownditioner.to; x++) {
numberLine[x] += airCownditioner.power;
}
}
}
boolean works = true;
for (int j = 0; j < n; j++) {
CowInterval cowInterval = cowIntervals[j];
for (int x = cowInterval.from; x <= cowInterval.to; x++) {
if (numberLine[x] < cowInterval.requiredCoolness) {
works = false;
}
}
}
if (works) {
answer = Math.min(answer, totalCost);
}
}
System.out.println(answer);
}
static class CowInterval {
final int from;
final int to;
final int requiredCoolness;
CowInterval(int from, int to, int requiredCoolness) {
this.from = from;
this.to = to;
this.requiredCoolness = requiredCoolness;
}
}
static class AirCownditioner {
final int from;
final int to;
final int power;
final int money;
public AirCownditioner(int from, int to, int power, int money) {
this.from = from;
this.to = to;
this.power = power;
this.money = money;
}
}
}