PROBLEM LINK
DIFFICULTY
EASY
PREREQUISITES
Simple Math
PROBLEM
You are given an array of N numbers. You can perform a maximum of 1000 operations of the following kind
- Pick a prime number P ≤ N.
- Pick P numbers from the array and replace them (at their original position) with their mean.
Print a sequence of operations that will replace each number with the mean of the whole array.
QUICK EXPLANATION
There are 6 sample cases given. The last three are very curious 
You should notice that in the last three sample cases, no matter what the initial values in the array are, the final values will be the mean of the array. This is indeed true. A sequence of moves can be derived that do not even depend on the initial array!
EXPLANATION
Let us define what sequence of moves will change the array such that all the values will become equal to the mean of the initial values.
There are N values initially.
{ A1, A2 …, AN }
We assume that initially they are all different.
Now, we define TECHNIQUE(N) that will generate the sequence of operations for N numbers.
TECHNIQUE({A1, A2 ..., AN}) /*accepts an array of indices*/
1 let M be a sequence of moves, initially empty
2 let P be any prime number that divides N
3 if P = N
4 M.append({1, 2, ..., N}) (a single move, since N is prime)
5 return M
/*Otherwise*/
6 Divide N into P segments of size S = N/P
7 let S = { s1, s2 ..., sP } segments
8 for each segment s in S
9 M.append(TECHNIQUE(s)) /*Append all the moves from the array of moves returned*/
10 for i = 1 to N/P
11 M.append({s1,i, s2,i ..., sP,i})
12 return M
We append moves in Line 4 an Line 11. Both these moves contain prime number of indices, and hence, are valid moves.
After Line 8 - 9, the array will contain P unique values repeated N/P times. The array will always look like
{
A1, A1 …, A1, (repeated N/P times)
A2, A2 …, A2, (repeated N/P times)
…,
AP, AP …, AP (repeated N/P times)
}
And thus, we select P values in a loop of N/P. This makes all the values in the array equal.
You may be curious whether this technique will always satisfy the less than 1000 moves constraint. Let us calculate how many moves this technique makes in each turn.
Let us assume, that we select the prime number P that divides N.
M(N) = M(N / P) * P + (N / P)
It is left as an exercise for the reader to prove that
Given, N = P1r1P2r2…Pkrk
M(N) = N ( r1 / P1 + r2 / P2 … + rk / Pk )
Thus, it doesn’t matter which prime number you select in each step, so long as the prime number divides N.
SETTERS SOLUTION
Can be found here
TESTERS SOLUTION
Can be found here