EQIDLIS - editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

This is supposed to be an easy problem, and all you have to do is simulate the given step. If there are T idlis in total and at the end of the distribution, each of the N students gets equal number of idlis, then each should get ( T / N ) idlis. So, if ( T % N ) != 0, then it is not possible to distribute equally and you should print -1. If T % N == 0, then it is always possible to distribute equally in a finite number of steps. Lets see an informal proof of the same.

Lets consider only the cases when T % N == 0. Let D = ceil( ( max - min) / 2 ). If ( max - min ) == 0, we are done. If ( max - min ) == 1, the array would look like {a, a,…, a, a+1, a+1,…, a+1} with some x number of (a+1)'s ( x >= 1 ) and N - x number of (a)'s ( N - x >= 1 ). We can see that for any possible x, T % N == x ( != 0 ), hence there will never be a case where ( max - min ) == 1 ( while having T % N == 0 ). For ( max - min ) >= 2, D >= 1 and max = max - D, min = min + D and the difference between these two numbers strictly decreases. So, in some finite number of steps, all the numbers will become equal.

A simple solution performing a O(n) search to find minimum and maximum in each step should be enough to pass in the given time.

{ As described in the problem statement, ACM-ICPC world finals opening ceremony was actually happening while you were reading this problem in the contest. I’m not sure if Dexter Murugan was there :wink: }

Exercise 1: Find the maximum value of the answer for 1 <= N <= 3000 and 0<= A* <= N,or at least a good upper bound

Exercise 2: If the maximum answer can be R, think of how to solve the problem in O( N + R logN )

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

3 Likes

any hints on the answers to the exercises?

1 Like

Loved the problem! Anf of course the explanation :slight_smile: