USACO 2022 February Contest, Bronze Problem 1. Sleeping in Class

Farmer John has noticed that Bessie has not been paying attention in class. He has asked another student in class, Elsie, to keep track of the number of times Bessie falls asleep in a given class. There are NN class periods (1≤N≤1051≤N≤105), and Elsie logs that Bessie fell asleep aiai times (0≤ai≤1060≤ai≤106) in the ii-th class period. The total number of times Bessie fell asleep across all class periods is at most 106106.

Elsie, feeling very competitive with Bessie, wants to make Farmer John feel like Bessie is consistently falling asleep the same number of times in every class -- making it appear that the issue is entirely Bessie's fault, with no dependence on Farmer John's sometimes-boring lectures. The only way Elsie may modify the log is by combining two adjacent class periods. For example, if a=[1,2,3,4,5],a=[1,2,3,4,5], then if Elsie combines the second and third class periods the log will become [1,5,4,5][1,5,4,5].

Help Elsie compute the minimum number of modifications to the log that she needs to make so that she can make all the numbers in the log equal.

SAMPLE INPUT:

3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0

SAMPLE OUTPUT:

3
2
0

For the first test case in this example, Elsie can change her log to consist solely of 3s with 3 modifications.

   1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3

For the second test case, Elsie can change her log to 7 with 2 modifications.

   2 2 3
-> 2 5
-> 7

For the last test case, Elsie doesn’t need to perform any operations; the log already consists of equal entries.

Problem credits: Jesse Choe

 USACO 2022 February Contest, Bronze Problem 1. Sleeping in Class 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Jesse Choe, Benjamin Qi)

Key Observation: After any modification, the quantity sum(a)=a1+a2+⋯+aNsum(a)=a1+a2+⋯+aN stays the same.

Solution: Rather than figuring out the minimum number of operations to make the array equal, let's figure out the maximum number of elements rr that could remain in the array after all modifications. Then the minimum number of modifications will equal N−rN−r.

For a certain rr to be achievable, sum(a)rsum(a)r must be an integer and it must be possible to partition the array into rr ranges such that each range sums to exactly sum(a)rsum(a)r. For example, in the first test case of the sample input, we can partition the array into r=3r=3 ranges each with sum sum(a)r=3sum(a)r=3:

[1 2] [3] [1 1 1]

For a single rr, checking whether this is possible can be done in O(N)O(N) time by iterating over the elements of aa from left to right. For each element, we can either choose to extend the current range or start a new one; see the code for details.

Time Complexity: O(N⋅(# divisors of sum(a)))O(N⋅(# divisors of sum(a)))

This allows us to solve the problem under the time constraints because the sum of the array is at most 106106, and the maximum number of divisors for any number ≤106≤106 is 240240.

Jesse’s code:

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	int sum_a = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum_a += a[i];
	}
	for (int r = n; r >= 1; r--) {
		if (sum_a % r == 0) {
			int targetSum = sum_a / r; // the desired sum for each range
			int curSum = 0;			   // the sum of the current range
			bool ok = true;
			for (int i = 0; i < n; i++) {
				curSum += a[i];
				if (curSum > targetSum) {
					/*
					 * Can't split the array into
					 * r equal elements.
					 */
					ok = false;
					break;
				}
				if (curSum == targetSum) {
					/*
					 * Start a new range
					 */
					curSum = 0;
				}
			}
			if (ok) {
				cout << n - r << endl;
				return;
			}
		}
	}
}

int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		solve();
	}
}