Home » 国际竞赛 » Details

USACO 2022 January Contest, Bronze Problem 3. Drought

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午3:49

USACO 2022 January Contest, Bronze Problem 3. Drought

The grass has dried up in Farmer John's pasture due to a drought. After hours of despair and contemplation, Farmer John comes up with the brilliant idea of purchasing corn to feed his precious cows.

FJ’s $N$ cows ( $1 \leq N \leq 10^{5}$ ) are arranged in a line such that the $i$ th cow in line has a hunger level of $h_{i}$ ( $0 \leq h_{i} \leq 10^{9}$ ). As cows are social animals and insist on eating together, the only way FJ can decrease the hunger levels of his cows is to select two adjacent cows $i$ and $i + 1$ and feed each of them a bag of corn, causing each of their hunger levels to decrease by one.

FJ wants to feed his cows until all of them have the same non-negative hunger level. Please help FJ determine the minimum number of bags of corn he needs to feed his cows to make this the case, or print $- 1$ if it is impossible.

INPUT FORMAT (input arrives from the terminal / stdin):

Each input consists of several independent test cases, all of which need to be solved correctly to solve the entire input case. The first line contains $T$ ( $1 \leq T \leq 100$ ), giving the number of test cases to be solved. The $T$ test cases follow, each described by a pair of lines. The first line of each pair contains $N$ , and the second contains $h_{1}, h_{2}, \dots, h_{N}$ . It is guaranteed that the sum of $N$ over all test cases is at most $10^{5}$ . Values of $N$ might differ in each test case.

OUTPUT FORMAT (print output to the terminal / stdout):

Please write $T$ lines of output, one for each test case.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

SAMPLE INPUT:

5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9

SAMPLE OUTPUT:

14
16
-1
-1
-1

For the first test case, give two bags of corn to both cows $2$ and $3$ , then give five bags of corn to both cows $1$ and $2$ , resulting in each cow having a hunger level of $3$ .

For the second test case, give two bags to both cows $1$ and $2$ , two bags to both cows $2$ and $3$ , two bags to both cows $4$ and $5$ , and two bags to both cows $5$ and $6$ , resulting in each cow having a hunger level of $2$ .

For the remaining test cases, it is impossible to make the hunger levels of the cows equal.

SCORING:

All test cases in input 2 satisfy $N \leq 3$ and $h_{i} \leq 100$ .
All test cases in inputs 3-8 satisfy $N \leq 100$ and $h_{i} \leq 100$ .
All test cases in inputs 9-14 satisfy $N \leq 100$ .
Input 15 satisfies no additional constraints.

Additionally, $N$ is always even in inputs 3-5 and 9-11, and $N$ is always odd in inputs 6-8 and 12-14.

Problem credits: Arpan Banerjee

USACO 2022 January Contest, Bronze Problem 3. Drought 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Arpan Banerjee, Benjamin Qi)

Define an operation on $(i, i + 1)$ as the act of decreasing both $h_{i}$ and $h_{i + 1}$ by one. Also define $f$ to be the final hunger value.

Half Credit:

For inputs 1-8, it suffices to try all possible values of $f$ from $0$ to $min (h_{i})$ and see if they result in valid solutions. This can be done by sweeping left to right across $h$ and remedying instances where $h_{i}$ is greater than $f$ by doing operations on $(i, i + 1)$ until one of $h_{i}$ or $h_{i + 1}$ equals $f$ . If there is a solution, this method must lead to it, because doing operations on $(i, i + 1)$ is the only way to make $h_{i}$ equal $f$ assuming no more operations on $(i - 1, i)$ are allowed.

This solution runs in $O (N max (h_{i}))$ time.

Arpan's code:

#include<bits/stdc++.h>
#define int long long
#define nl "\n"
using namespace std;

int n;
const int inf = 1e18;

int cost(vector<int> h, int f){
	int o = 0;
	for (int i = 0; i < n - 1; i++){
		if (h[i] > f){
			int sub = min(h[i], h[i + 1]) - f;
			h[i] -= sub, h[i + 1] -= sub;
			o += sub * 2;
		}
	}
	for (int i = 0; i < n - 1; i++)
		if (h[i] != h[i + 1])
			return inf;
	return o;
}

int exe(){
	cin >> n; vector<int> h(n);
	int mn = inf, ans = inf;
	for (int& i : h) cin >> i, mn = min(mn, i);
	for (int f = 0; f <= mn; f++)
		ans = min(ans, cost(h, f));
	return (ans == inf ? -1 : ans);
}

signed main(){
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios_base::failbit);
	int t; cin >> t;
	while (t--) cout << exe() << nl;
}

(Almost) Full Solution:

Consider any $i$ such that $h_{i - 1} < h_{i}$ . If $i = N$ , then there is no solution because no operation can bring $h_{N}$ closer to $h_{N - 1}$ . Otherwise, the only way to make $h_{i}$ equal to $h_{i - 1}$ is to do at least $h_{i} - h_{i - 1}$ operations on $(i, i + 1)$ . Similar reasoning applies when $h_{i - 1} > h_{i}$ (there is no solution if $i = 2$ , otherwise at least $h_{i - 1} - h_{i}$ operations must be performed on $(i - 2, i - 1)$ ).

One approach is to repeatedly find the leftmost pair $(i - 1, i)$ such that $h_{i - 1} \neq h_{i}$ and perform the appropriate number of operations to make $h_{i - 1} = h_{i}$ . It can be proven that this terminates in $O (N^{3})$ time, and is enough to solve all but the last input.

Ben's code:

#include <bits/stdc++.h>
using namespace std;
 
using i64 = int64_t;
 
i64 solve(vector<i64> h){
	const int N = (int)h.size();
	i64 ans = 0;
	auto operations = [&h,&ans](int idx, i64 num_op) {
		assert(num_op >= 0);
		h.at(idx) -= num_op; 
		h.at(idx+1) -= num_op;
		ans += 2*num_op;
	};
	bool flag = true;
	while (flag) {
		flag = false;
		for (int i = 1; i < N; ++i) if (h[i-1] != h[i]) {
			flag = true;
			if (h[i-1] < h[i]) {
				if (i == N-1) return -1;
				operations(i,h[i]-h[i-1]);
			} else {
				if (i == 1) return -1;
				operations(i-2,h[i-1]-h[i]);
			}
			break;
		}
	}
	// now h is all equal
	if (h[0] < 0) return -1;
	return ans;
}

int main() {
	int t; cin >> t;
	while (t--) {
		int N; cin >> N;
		vector<i64> H(N);
		for (auto& i: H) cin >> i;
		cout << solve(H) << "\n";
	}
}

Full Solution 1:

For a faster solution, let's start by moving left to right across $h$ and applying the necessary number of operations to $(i, i + 1)$ to make $h_{i}$ equal to $h_{i - 1}$ whenever we find $i$ such that $h_{i} > h_{i - 1}$ . After doing a pass through the array with this procedure, either $h_{N} > h_{N - 1}$ (in which case there is no solution), or $h$ will be non-increasing ( $h_{i} \leq h_{i - 1}$ for all $2 \leq i \leq N$ ).

In the latter case, let's reverse $h$ . Now $h$ will be non-decreasing ( $h_{i} \geq h_{i - 1}$ for all $2 \leq i \leq N$ ). After one more pass with the above procedure, all elements of $h$ will be equal except possibly $h_{N}$ . If $h_{N} > h_{N - 1}$ , then there is no solution. Otherwise, all elements of $h$ are equal, and it remains to verify whether these elements are non-negative.

This solution takes $O (N)$ time.

Arpan's code:

#include<bits/stdc++.h>
#define int long long
#define nl "\n"
using namespace std;

int exe(){
	int ans = 0, n;
	cin >> n; vector<int> h(n);
	for (int& i : h) cin >> i;
	if (n == 1) return 0;
	for (int j : {1, 2}){
		for (int i = 1; i < n - 1; i++){
			if (h[i] > h[i - 1]){
				int dif = h[i] - h[i - 1];
				ans += 2 * dif, h[i + 1] -= dif, h[i] = h[i - 1];
			}
		}
		if (h[n - 1] > h[n - 2]) return -1;
		// now h is non-increasing
		reverse(h.begin(), h.end());
		// now h is non-decreasing
	}
	// now h is all equal
	return h[0] < 0 ? -1 : ans;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios_base::failbit);
	int t; cin >> t;
	while (t--) cout << exe() << nl;
}

Full Solution 2:

Let $o_{i}$ be the total number of operations FJ performs on $(i, i + 1)$ for each $1 \leq i < N$ . The goal is to find the maximum $f$ such that there exists a solution to the following system of equations. Firstly, the final hunger value and the number of operations performed at every pair of indices must be non-negative:

f, o 1, \dots, o N - 1 \geq 0

Also,

f + o 1 = h 1

f + o 1 + o 2 = h 2

f + o 2 + o 3 = h 3

⋮

f + o N - 2 + o N - 1 = h N - 1

f + o N - 1 = h N

The first solution in the analysis can be interpreted as trying all possible values of $f$ from $0$ to $min (h_{i})$ , determining $o_{1}, o_{2}, \dots, o_{N - 1}$ in that order, and checking whether all of them are non-negative. For a faster solution, let’s rewrite the system of equations in the following form.

o 1 = h 1 - f \geq 0

o 2 = h 2 - h 1 \geq 0

o 3 = h 3 - h 2 + h 1 - f \geq 0

⋮

o N - 1 = h N - 1 - h N - 2 + h N - 3 - \dots \geq 0

h N - h N - 1 + h N - 2 - h N - 3 + . . . + h 2 - h 1 = 0 if N even

h N - h N - 1 + h N - 2 - h N - 3 + . . . - h 2 + h 1 - f = 0 if N odd

Observe that if $N$ is odd, the last equation uniquely determines $f$ , so we can simply plug this value of $f$ into the brute force solution.

If $N$ is even, then if there exists some $f$ such that this system of equations, then $f^{'} = 0$ will as well. Let $o_{1}^{'}, o_{2}^{'}, \dots, o_{N - 1}^{'}$ be the resulting numbers of operations. To find the maximum $f$ , observe from the above equations that increasing $f^{'}$ will decrease $o_{1}^{'}, o_{3}^{'}, \dots, o_{N - 1}^{'}$ , while $o_{2}^{'}, o_{4}^{'}, \dots, o_{N - 2}^{'}$ remain constant. Thus, we may take $f = min (o_{1}^{'}, o_{3}^{'}, \dots, o_{N - 1}^{'})$ .

Ben's code:

#include <bits/stdc++.h>
using namespace std;
 
using i64 = int64_t;
 
i64 solve(const vector<i64>& H) {
	const int N = (int)H.size();
	i64 f = 0;
	for (int i = 0; i < N; ++i)
		f += (i%2 == 0 ? 1 : -1)*H[i];
	if (N%2 == 0) {
		if (f != 0) return -1;
	} else {
		if (f < 0) return -1;
	}
	i64 last_o = 0;
	vector<i64> o(N-1);
	for (int i = 0; i+1 < N; ++i) {
		last_o = o[i] = H[i]-f-last_o;
		if (o[i] < 0) return -1;
	}
	if (N%2 == 0) {
		i64 mn = o[0];
		for (int i = 0; i < N; i += 2)
			mn = min(mn,o[i]);
		for (int i = 0; i < N; i += 2)
			o[i] -= mn;
	}
	i64 sum_o = 0;
	for (i64 i: o) sum_o += i;
	return 2*sum_o;
}
 
int main() {
	int t; cin >> t;
	while (t--) {
		int N; cin >> N;
		vector<i64> H(N);
		for (auto& i: H) cin >> i;
		cout << solve(H) << "\n";
	}
}

[/hide]