REDUARRAY - Editorial


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

Author: klu_2100031675
Tester: pols_agyi_pols
Editorialist: iceknight1093




Frequency arrays


You’re given an array A.
In one move, you can choose a subarray [L, R] of A and an integer x, and replace every element of the subarray with x. The cost of this move is (R-L+1) \cdot x.

Find the minimum cost to make all the elements of the array equal.


The cost of a move is directly proportional to the length of the subarray we operate on.
Further, we aren’t limited in the number of moves we can make.

This means, when L \lt R, instead of operating on the entire subarray [L, R] we can just operate on each of the elements individually - the cost remains the same.

Now, suppose we want every element of the final array to be x.
Then, as noted above, our operation is essentially “change one element to x” with a cost of x.
Clearly, we need one such operation for every element of A that’s not x already.

That is, let \text{freq}[x] denote the number of occurrences of x in the array A.
This means that there are (N - \text{freq}[x]) elements that aren’t x.
The cost of converting everything to x is thus exactly x\cdot (N - \text{freq}[x]).

The overall answer is then the minimum of this across all x from 1 to N, that is,

\min_{x=1}^N \left(x\cdot (N - \text{freq}[x]) \right)

The \text{freq} array is the frequency array of A, which is easily computed in linear time.

Note that it’s not enough to consider only those x that appear in the array: it’s also valid to choose x = 1 and obtain a cost of N even when 1 isn’t present in A.
If you implement the frequency table using a dictionary/map, you might miss this case.


\mathcal{O}(N) per testcase.


Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    freq = [0]*(n+1)
    for x in a: freq[x] += 1
    ans = n
    for i in range(1, n+1):
        ans = min(ans, i * (n - freq[i]))

I used a map but luckily I also initialized the cost with a value of N, which happens to be the only potentially optimal cost for an absent element, so I got away with it.

can anyone share a code on pyth3 without using the counter method? I can’t fix the TLE error.

The Python implementation linked in the editorial above doesn’t use anything more than an array.

1 Like

sry, didn’t see that

also i wanted to know if all these questions in contests are solvable with pthon

without TLE i mean

The easier problems (as in, anything not exclusive to Div. 1) almost certainly are.
Harder problems may or may not be, often the only guarantee is that they’re solvable in C++.

1 Like

I am in div4. I can’t really judge when i should be starting C++. After completing all courses of python or at some other point?