EQUALIZ - Editorial

PROBLEM LINK

Practice
Contest

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

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

3 Likes

Where do I find more related stuff about this theory?