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 ? ? \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]