PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Abhinav Gupta
Tester: Satyam, Tejas Pandey
Editorialist: Pratiyush Mishra
DIFFICULTY:
1737
PREREQUISITES:
None
PROBLEM:
Chef has an array A of length N.
In one operation, Chef can choose any subsequence of the array and any integer X and then add X to all the elements of the chosen subsequence.
Determine the minimum number of operations required to make all the elements of the array distinct.
EXPLANATION:
Suppose in the array there are distinct elements A_1,A_2…A_n, with frequencies f_1,f_2,...,f_n. Then for each element A_i, we will proceed as follows:
Case \;1: f_i = 1
In this case the number is already distinct, so no operation is required.
Case \; 2: f_i > 1
In this case we will select half of elements of A_i and increase it by an arbitrary high number.
We can do the operations for all the distinct elements at the same time.
So in each operation, we will select all the distinct elements A_i, such that f_i > 1 and increase half of the elements to a arbitrary higher value.
Thus in all we just have to calculate the maximum f_i, say f_{max} and in each operation we will reduce the frequency f_{max} by half, thus our answer would be
Since operations would be applied to all f_j < f_{max}, at the same time so we just have to calculate for maximum f_i.
TIME COMPLEXITY:
O(N), for each test case.
SOLUTION:
Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution