CHEFCOUN - Editorial

editorial
, , ,
1

PROBLEM LINK

Practice

Contest

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

AUTHOR’S AND TESTER’S SOLUTIONS

Setter’s solution

Tester’s solution

Editorialist’s solution

2 Likes
2

Great editorial @xellos0 :slight_smile:

3

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

4

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?

5

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.

6

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

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

Then Simplify and you should get the resulting equation.

7

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 :slight_smile:

8

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 :slight_smile:

1 Like
9

can someone point out what’s wrong with my code??
code -


[1]


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

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

11

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

12

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<<" ";
	}

Link to solution : https://www.codechef.com/viewsolution/15849780