PROBLEM LINKS
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 
}
Exercise 1: Find the maximum value of the answer for 1 <= N <= 3000 and 0<= A[i] <= 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.
