USACO 2023 December Contest Bronze Division - Candy Cane Feast

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Let's analyze what's going to happen in one step of the algorithm. if the first cow eats it all, then we stop here, but if this doesn't happen, the first cow will double in size and we will keep running the algorithm and so on.

Therefore, the first value will only double in size 30 times, so we can brute force the algorithm and we need to be a bit careful however with dealing with the way cows grow in size.

Source codes

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

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    vector<long long> v(n+1);

    for(int i = 1; i <= n; i++)
        cin >> v[i];

    for(int i = 1; i <= m; i++)
    {
        long long x;
        cin >> x;

        long long start = 0;
        for(int j = 1; j <= n && x > start; j++)
        {
            long long val = min(x, v[j]);
            v[j] += max(0LL, (val - start));
            start = max(start, val);
        }
    }

    for(int i = 1; i <= n; i++)
        cout << v[i] << '\n';

    return 0;
}

import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
m = int(data[1])
v = [0] * n
idx = 2
for i in range(n):
    v[i] = int(data[idx])
    idx += 1
arrx = [int(x) for x in data[idx:idx + m]]
for x in arrx:
    start = 0
    for j in range(n):
        if x <= start:
            break
        a = v[j]
        if a < x:
            val = a
        else:
            val = x
        d = val - start
        if d > 0:
            v[j] += d
        if val > start:
            start = val
sys.stdout.write("\n".join(map(str, v)))