USACO 2023 January Contest Bronze Division - Air Cownditioning II

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Given that the constraints are very small (up to \(20\)), brute force makes a lot of sense and even more so, trying all subsets of ACs we choose at a given point.

The only thing we have to do is to find the minimal answer among all the options tried.

Source codes

The source codes in C++ and Python can be seen below.

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

struct str
{
    int L, R, cnt;
};

struct str2
{
    int a, b, p, m;
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<str> v(n+1);
    for(int i = 1; i <= n; i++)
        cin >> v[i].L >> v[i].R >> v[i].cnt;

    vector<str2> v2(m+1);
    for(int i = 0; i < m; i++)
        cin >> v2[i].a >> v2[i].b >> v2[i].p >> v2[i].m;

    int ans = (1<<29);
    for(int i = 1; i < (1<<m); i++)
    {
        vector<int> plc(101, 0);
        int cost = 0;
        bool ok = 1;
        for(int j = 0; j < m; j++)
            if(i & (1<<j))
            {
                cost += v2[j].m;
                for(int poz = v2[j].a; poz <= v2[j].b; poz++)
                    plc[poz] += v2[j].p;
            }
        for(int cow = 1; cow <= n; cow++)
            for(int pz = v[cow].L; pz <= v[cow].R; pz++)
                if(plc[pz] < v[cow].cnt)
                    ok = 0;
        if(ok)
            ans = min(ans, cost);
    }
    cout << ans;
    return 0;
}

n, m = map(int, input().split())
v = []
for _ in range(n):
    L, R, cnt = map(int, input().split())
    v.append((L, R, cnt))
v2 = []
for _ in range(m):
    a, b, p, mm = map(int, input().split())
    v2.append((a, b, p, mm))
ans = 1 << 29
for mask in range(1, 1 << m):
    plc = [0] * 101
    cost = 0
    ok = True
    for j in range(m):
        if mask & (1 << j):
            cost += v2[j][3]
            for poz in range(v2[j][0], v2[j][1] + 1):
                plc[poz] += v2[j][2]
    for L, R, cnt in v:
        for poz in range(L, R + 1):
            if plc[poz] < cnt:
                ok = False
    if ok:
        ans = min(ans, cost)
print(ans)