Official Analysis (C++)

Explanation

After Elsie has made all the modifications to the log array $A$, the log will show that Bessie sleeps the same number of hours every day. Let's call that number $\texttt{num\_hours}$.

Let's also define the total number of hours Bessie sleeps as $\texttt{sum}$.

We know that after all modifications, the length of the log will be $\texttt{sum}/\texttt{num\_hours}$. Since every modification reduces the length of the log by 1, the number of modifications Elsie makes will be $N-\texttt{sum}/\texttt{num\_hours}$.

Since $N$ and $\texttt{sum}$ are constant, to maximize the above expression our only option is to minimize $\texttt{num\_hours}$.

In order to do that, we iterate over possible values of $\texttt{num\_hours}$ from smallest to largest and check if it's possible to reduce the log to an array with all elements equal to it. As soon as we hit a valid element, we print out the number of modifications needed and end, since we know it's the best we can do.

To check if a value of $\texttt{num\_hours}$ is valid, we iterate over the given log and combine values. If at some point a combined value exceeds $\texttt{num\_hours}$, we know that $\texttt{num\_hours}$ is not valid.

Implementation

Time Complexity: $\mathcal{O}(N \cdot \texttt{sum})$ for each test case.

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

int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n;
		cin >> n;
		vector<int> elsie_log = vector<int>(n);

Copy
import java.io.*;
import java.util.*;

public class SleepingInClass {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
		for (int t = 0; t < testNum; t++) {
			int n = Integer.parseInt(read.readLine());
			int[] elsieLog = new int[n];

Copy
for _ in range(int(input())):
	n = int(input())
	elsie_log = [int(i) for i in input().split()]
	assert len(elsie_log) == n

	log_sum = sum(elsie_log)

	# Try all possible number of hours after modification
	for num_hours in range(log_sum + 1):
		# The sum must be divisible by num_hours