USACO 2023 February Contest Silver Division - Bakery

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem can be solved using binary search on the answer.

For each step of the binary search, we want to find the range of eligible values for reductions for tc such that all orders are satisfied.

This part can be done using either binary or ternary search for each order depending on whether there are more cookies or muffins. For more cookies, we want to see what is the minimum number of moves we need to make to bring them down to a reasonable range in terms of time.

For more muffins, we want to do the same which will help us find the maximum budget required for cookies. If the range is valid, we have a potential answer.

Source code

The source code in C++ can be seen below.

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

struct str
{
    long long a, b, t;
};

bool chk(vector<str> &orders, long long T, long long tc, long long tm) {

    long long minX = 1, maxX = tc;
    for (int i = 0; i < (int) orders.size(); i++) {
        if (orders[i].a >= orders[i].b) {
            long long optX = tc - min(T, tc - 1);
            minX = max(optX, minX);
            long long otherX = -1;
            long long L = optX;
            long long R = tc - (T - min(T, tm - 1));
            // finding the smallest number of moves required for cookie reductions 
            while (L <= R) {
                long long mid = (L + R) / 2;
                if (mid * orders[i].a + (tm - (T - (tc - mid))) * orders[i].b <= orders[i].t) {
                    otherX = mid;
                    L = mid + 1;
                }
                else {
                    R = mid - 1;
                }
            }

            if (otherX != -1) {
                maxX = min(otherX, maxX);
            }
            else {
                return 0;
            }
        }
        else {
            long long optX = tc - (T - min(T, tm - 1));
            maxX = min(optX, maxX);
            long long otherX = -1;
            long long L = tc - min(T, tc - 1);
            long long R = optX;

            // finding the smallest number of moves required for muffin reductions
            while (L <= R) {
                long long mid = (L + R) / 2;
                if (mid * orders[i].a + (tm - (T - (tc - mid))) * orders[i].b <= orders[i].t) {
                    otherX = mid;
                    R = mid - 1;
                }
                else {
                    L = mid + 1;
                }
            }

            if (otherX != -1) {
                minX = max(otherX, minX);
            }
            else {
                return 0;
            }
        }
    }


    if (minX <= maxX) {
        return 1;
    }
    return 0;
}
void solve() {
    long long n, tc, tm;
    cin >> n >> tc >> tm;

    vector<str> orders(n);
    for (int i = 0; i < n; i++) {
        cin >> orders[i].a >> orders[i].b >> orders[i].t;
    }

    long long L = 0;
    long long R = tc + tm - 2;
    long long ans = R;

    while (L <= R) {
        long long mid = (L + R) / 2;
        if (chk(orders, mid, tc, tm)) {
            ans = mid;
            R = mid - 1;
        }
        else {
            L = mid + 1;
        }
    }

    cout << ans << '\n';
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }
    return 0;
}