PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: klu_2100031675
Tester: pols_agyi_pols
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Frequency arrays
PROBLEM:
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.
EXPLANATION:
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,
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.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
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]))
print(ans)