SUBSEQDIST Editorial

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

\lceil log_{2}{f_{max}} \rceil

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

2 Likes

It’s mind blowing!

1 Like

why ans is not max_freq-1 ?

2 Likes

for example ,consider this testcase :
i/p → 4
3 3 3 3
o/p → 2
output isnt 3 and 2 is the minimum, transformations will be like
1st step → 3 4 4 3 (x = 1)
2nd step → 3 4 7 6 (x = 3)

5 Likes

Problem is actually good, you need very keen observation to solve this one.

5 Likes

This was a really good problem! Thanks

thanks for this to the point explanation.

Anyone can share the java code for this qn.

what does line 25 do in the editorial solution?

val = (long long)2 * val;

I was stuck on the same thought too. Consider 10 elements each with frequency 1000 and group them on basis of element value itself. ie each group has same element value.
You might think if in one operation we pick more than one element from each group it will just add more groups for next operation and your brain might just drop this approach at once. But thing to observe here is that more groups dont increase the required operations as subsequence you can choose in one operation has no fixed length. What matters is only how fast you can decrement the max frequency. and that is when you consider half elements from each group.

good logic ! Like most of them, I had worked out the logic as max_freq - 1 and thought finally I would break out of Q5 curse but anyways… I will do it someday surely soon.