ADDIS - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given an array A.
You can choose an integer X and then replace each A_i with either A_i-X or A_i+X.

Find the minimum possible maximum frequency of an element in A.

EXPLANATION:

Consider some value Y, and suppose there are f_Y occurrences of Y in the array.

Whichever value of X we choose, some of these copies of Y will become Y-X and some will become Y+X.
In particular, this means at least half of the values of Y will shift in the same direction.

Thus, no matter what, the resulting array will surely have some element with at least \frac{f_Y}{2} occurrences.

This applies to any element Y.
So, a lower bound on the maximum possible frequency, is half of the largest frequency of any element in the array.

This lower bound is always attainable, because we’re allowed to choose any integer X.

We can, for example, choose X = 10^{10}, which is much larger than every array element.
Then, for any two different values Y_1, Y_2 in the array, we can never have Y_1 - X = Y_2 + X because this would require Y_1-Y_2 = 2X, which is impossible when Y_1, Y_2 \in [0, 10^9].

Thus, operations on different elements can’t conflict at all.
We can thus freely increment half the copies of Y by X and decrement the other half by X, attaining the above-mentioned lower bound.

The answer is hence the largest frequency of an element in the array, divided by 2.
Note that if the largest frequency is odd, then the result must be rounded up after division.

The largest frequency of an array element can be found by either using a map to collect frequencies, or by sorting and looking at segments of equal elements.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    import collections
    f = collections.Counter(a)
    ans = max(f.values())
    print((ans+1)//2)
1 Like