### 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).