USACO 2022 January Contest Bronze Division - Drought

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem seems unapproachable at first, but it turns out that all we have to do is to run two scans left to right and try to subtract from the greater values, the smaller values as much as we can.

I recommend also reading these two solutions the official one as well as the one from USACO Guide

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

    while(t--)
    {
        int n;
        cin >> n;

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

        if(n == 1)
        {
            cout << 0 << '\n';
            continue;
        }

        long long ans = 0;
        for(int i = 2; i + 1 <= n; i++)
            if(v[i] > v[i-1])
            {
                long long dif = v[i] - v[i-1];
                ans += 2 * dif;
                v[i] = v[i-1];
                v[i+1] -= dif;
            }
        if(v[n] > v[n-1])
        {
            cout << -1 << '\n';
            continue;
        }
        reverse(v.begin() + 1, v.begin() + n + 1);
        for(int i = 2; i + 1 <= n; i++)
            if(v[i] > v[i-1])
            {
                long long dif = v[i] - v[i-1];
                ans += 2 * dif;
                v[i] = v[i-1];
                v[i+1] -= dif;
            }
        if(v[n] > v[n-1])
        {
            cout << -1 << '\n';
            continue;
        }
        reverse(v.begin() + 1, v.begin() + n + 1);
        if(v[1] < 0)
        {
            cout << -1 << '\n';
            continue;
        }
        cout << ans << '\n';
    }

    return 0;
}

t = int(input())
for _ in range(t):
    n = int(input())
    v = [0] + list(map(int, input().split()))
    if n == 1:
        print(0)
        continue
    ans = 0
    for i in range(2, n):
        if v[i] > v[i - 1]:
            dif = v[i] - v[i - 1]
            ans += 2 * dif
            v[i] = v[i - 1]
            v[i + 1] -= dif
    if v[n] > v[n - 1]:
        print(-1)
        continue
    v[1:] = v[1:][::-1]
    for i in range(2, n):
        if v[i] > v[i - 1]:
            dif = v[i] - v[i - 1]
            ans += 2 * dif
            v[i] = v[i - 1]
            v[i + 1] -= dif
    if v[n] > v[n - 1]:
        print(-1)
        continue
    v[1:] = v[1:][::-1]
    if v[1] < 0:
        print(-1)
        continue
    print(ans)