# CHEFCOUN - Editorial

Practice

Contest

Author: Praveen Dhinwa

Tester: Alexey Zayakin

Editorialist: Jakub Safin

EASY

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

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS

Setterâ€™s solution

Testerâ€™s solution

Editorialistâ€™s solution

2 Likes

Great editorial @xellos0

Can someone please point out the mistake in this code? Well everything could be wrong but still
https://www.codechef.com/viewsolution/15789379

na+nb=Nna+nb=N and a(na+1)+bnb=232a(na+1)+bnb=232. This can be simplified to 232=na+1+b(N+1)232=na+1+b(N+1)
How?

Can someone please explain this part?

Since N+1>1+na, this means na+1 is 2^32 modulo N+1 (watch out, we need 64-bit integers to evaluate this!) and b is the result of integer division of 2^ 32 by N+1.

In a(na+1) + bob = 2^32.

Substitute nb = N - na and a = b+1

Then Simplify and you should get the resulting equation.

suppose say a is divided by b ,then the respective quotient and remainder be q,r => we can write a=b*q+r. we also know that the remainder can never be greater than divisor ,so here (N+1) is the divisor ,b is the quotient and 1+na is the remainder obtained by so called % operator ,Hope this helps

Here is a video editorial on the problem, where we try to overflow the sum just before the minimum is hit.

Btw @xellos, very well written

1 Like

can someone point out whatâ€™s wrong with my code??
code -

``````
[1]

[1]: https://www.codechef.com/viewsolution/15885532``````

(mx - (n - 1) * x)/2 +1)

hey can anyone explain why we are dividing it with 2(how tester come up with this solution?)? I understand this portion: `mx - (n - 1) * x)` but not getting why on dividing it gives the value which will make it overflow.

What if I give the following counter case:-

Let M = 2X10^9
if my input(countercase) is
M M 0 0 0 0 0 â€¦

then
prefsum = M 2M 2M 2M 2M 2Mâ€¦
sufSum = 2M M 0 0 0 0
pref+suf = 3M 3M 2M 2M 2M 2M

Here as per the worng submission, 3M exceeds 2^32 so 3M%2^32 gives 1.7x10^9, so I will get the index 0, but the actual answer is index 2 with the minimum sum 2M (4x10^9).

My friendâ€™s approach was quite beautiful. Here is his short , simple and crisp solution.

``````for(int i=0;i<n;i++)
{
if(i<92681)
cout<<(i+1)<<" ";
else
cout<<1<<" ";
}
``````