### PROBLEM LINK

**Author:** Praveen Dhinwa

**Tester:** Alexey Zayakin

**Editorialist:** Jakub Safin

### DIFFICULTY

EASY

### PREREQUISITIES

none

### PROBLEM

The problem CHEFSUM is as follows: for a given array of size N, find the least number i such that the sum of its first i elements and last N-i+1 elements is the smallest.

Find a countertest - an array of size N such that the answer to this problem is incorrect when using 32-bit unsigned integers (working modulo 2^{32}).

### QUICK EXPLANATION

Make only the maximum overflow to zero. Use only two different numbers in the array; their difference should be 1.

### EXPLANATION

One strategy we could use is forcing just one of the sums to be evaluated incorrectly as the minimum, while all other sums are evaluated correctly – this gives us better control over the pseudocode we’re trying to break.

Since we’re dealing with overflow where the sums are evaluated mod 2^{32}, there’s an easy way to do that and incorrectly evaluate the largest sum – just make that sum equal to 2^{32}. This way, the pseudocode will evaluate the maximum as 0 instead and print the index that gives the maximum instead of the minimum (as long as all other sums are positive).

Another important observation comes from the solution of CHEFSUM: prefSum[i]+sufSum[i] is just the sum S of all elements of A plus A[i]. The maximum sum therefore appears for the maximum element of A (let’s denote it by a).

This allows us to considerably simplify the output array A. For example, we can use just two different numbers a,b in A and there’s nothing to lose by making b as large as possible, so b = a-1. The pseudocode will still evaluate all sums S+a as 0 and S+b as 2^{32}-1, so it will return one of the incorrect indices anyway (we don’t even need to care which one).

Finally, we can express exactly how many numbers a,b there should be and what the value of a should be: n_a and n_b respectively, where n_a + n_b = N and a (n_a+1) + b n_b = 2^{32}. This can be simplified to 2^{32} = n_a + 1 + b (N+1). Since N+1 > 1+n_a, this means n_a+1 is 2^{32} modulo N+1 (watch out, we need 64-bit integers to evaluate this!) and b the result of integer division of 2^{32} by N+1.

We need to check if such a solution is always valid. There are 2 conditions: N > n_a > 0 and 10^5 \ge a > 1. Fortunately, both hold for any input number N *in the given range*, so we’ve got a working solution – just print n_a times a and n_b times b.

The time complexity of this algorithm is O(N) only due to printing the output (we can describe the output in O(1)) and memory complexity is O(1).