USACO Bronze 2022 January - Drought

Official Analysis (C++)

Explanation

Let's go through the cows from left to right, making sure that all the cows we've processed have the same hunger value. Thus, we can break this problem up into cases:

Suppose the cows are numbered from $1$ to $n$, and we are currently looking at cow $i$. If cow $i+1$ has a greater hunger value, then it is sufficient to decrease cow $i+1$ to the same hunger value as cow $i$. To do this we will pick the pair of cows $i+1$ and $i+2$ and decrease their hungers until cow $i+1$ has the same hunger value as cow $i$. Of course, if cow $i+2$ ends up with a negative hunger value, then it is impossible and we output $-1$.

Now suppose cow $i$ has a greater hunger value than cow $i+1$. We obviously cannot decrease the hunger for cow $i+1$ any further since it will never be equal - we only can decrease the hunger for all the cows before $i+1$. To do this we select adjacent pairs of cows starting with the odd numbered cows and decrease their hunger values together (cows $1$ and $2$, cows $3$ and $4$, $\ldots$, cows $i-1$ and $i$).

The following sequence of feeding shows how this strategy can be applied:

5 5 5 5 3 ...
4 4 4 4 3 ...
3 3 3 3 3 ...

After this, all the cows before $i+1$ will be decreased to the same hunger value as cow $i+1$. However, when $i$ is odd, it is impossible to decrease it's hunger unless we also decrease the hunger value for cow $i+1$, so we output $-1$.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
	int n;
	cin >> n;
	vector<ll> hunger(n + 1);  // hunger for each cow, (1-indexed)
	for (int i = 1; i <= n; i++) { cin >> hunger[i]; }

Copy
from typing import List


def check(same_lvl: int, corn: List[int], hunger_lvl: List[int]) -> bool:
	# check if proposed corn is achievable
	hunger_lvl[0] -= corn[0]
	hunger_lvl[-1] -= corn[-1]

	for i in range(1, len(hunger_lvl) - 1):
		sum_of_corn = corn[i - 1] + corn[i]