USACO 2021 December Contest Bronze Division - Air Cownditioning

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

If we only had one stall, the casework would have been easy. However, we don't so we need to be careful at leveraging the power of the operation we do.

The key observation worth noticing is that we will never perform an operation against the changes we have to make (if we must increase a temperature, we will never decrease it in that room).

Therefore, for a given position i, we only care about the previous position's difference, and in order to do that, whenever the difference changes, we might need to add more operations or lessen the impact.

Last but not least, when the sign changes, we must reset the counters.

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;
    cin >> n;

    vector<int> start(n+1), finish(n+1);
    for(int i = 1; i <= n; i++)
        cin >> finish[i];
    for(int i = 1; i <= n; i++)
        cin >> start[i];

    int ans = 0;
    int delta = 0;
    for(int i = 1; i <= n; i++)
    {
        if(delta >= 0 && start[i] <= finish[i])
        {
            if(finish[i] - start[i] > delta)
                ans += (finish[i] - start[i]) - delta;
        }
        else
        {
            if(delta < 0 && start[i] > finish[i])
            {
                if(start[i] + delta > finish[i])
                    ans += (start[i] + delta - finish[i]);
            }
            else
                ans += abs(finish[i] - start[i]);
        }
        delta = finish[i] - start[i];
    }

    cout << ans;
    return 0;
}

n = int(input())
finish = list(map(int, input().split()))
start = list(map(int, input().split()))
ans = 0
delta = 0
for i in range(n):
    if delta >= 0 and start[i] <= finish[i]:
        if finish[i] - start[i] > delta:
            ans += (finish[i] - start[i]) - delta
    else:
        if delta < 0 and start[i] > finish[i]:
            if start[i] + delta > finish[i]:
                ans += (start[i] + delta - finish[i])
        else:
            ans += abs(finish[i] - start[i])
    delta = finish[i] - start[i]
print(ans)