MAXDISTKT - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest

DIFFICULTY:

SIMPLE

PREREQUISITES:

Greedy

PROBLEM:

Given an array B of length N. Find an array A of length N such that the number of distinct elements A_i\mod B_i\ \forall i\in \{1,2,\dots,N\} is maximised.

EXPLANATION:

Observation: If A_i\ge B_i in the final array A, we can replace A_i with A_i\mod B_i without changing the score.

Therefore, we can only consider A_i\in \{0,1,\dots,B_i-1\} for all valid i. Then, the problem is reduced to finding an array A such that 0\le A_i<B_i and the number of distinct elements in A is maximised.

Intuition for the solution

Consider an example B=[1,7,2, 3, 2].

The set of possible values for each A_i is as follows:

  • A_1=\{0\}
  • A_2=\{0,1,2,3,4,5,6\}
  • A_3=\{0,1\}
  • A_4=\{0,1,2\}
  • A_5=\{0,1\}

You want to select exactly one element from each set, such that the number of distinct elements is maximised. This can be remodelled equivalently as a simpler version of this classical problem (solution can be found here), which motivates the greedy solution!

We proceed greedily.

Generate the permutation array C of length N such that, B_{C_i}\le B_{C_{i+1}} for all valid i. This can be accomplished easily using a sorting algorithm.
Iterate over this array C; let the current index be i.

  • If cnt < B_{C_i}, set A_{C_i} to cnt and increase cnt by 1.
  • Else, we may set A_{C_i} to any valid value, since it doesn’t contribute to the total score. The value of cnt is not updated in this case.

It is trivial to deduce that, the number of distinct elements in A at the end is equal to the final value of cnt.

The proof of optimality is similar to the proof linked in the spoiler above, and is left to the reader as an exercise.

TIME COMPLEXITY:

Generating the array C takes O(N\log N) with sorting. Since we iterate once over C to compute the answer, the total time complexity is thus

O(N\log N+N)\approx O(N\log N)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

1 Like
2

Why don’t I print C array as output it also contains most no of unique elements possible

3

Because (C_i \mod B_i) is not guaranteed to be equal to C_i.
C is just an implementation detail to ease my explanation. My solution code doesn’t utilise it at all, and instead sorts an array of pairs (B_i,i) to compute the answer.

4

why did my solution Solution:52472444 (O(n)) give tle ?

5

Try to benchmark your solution with a T=10^5, N=10 max constraints testcase. It initializes a gigantic array of vectors on each iteration and this is very slow when T is large:

    while(t)
    {t--;
     vector<long int> v[200001];
    }
6

can anyone tell me what is wrong with my code CodeChef: Practical coding for everyone

7

In the following loop

    for(int i=n-1;i>=0;i--){
        if(p>0){
            p--;
            int ind=b[i].second;
            a[ind]=p;
        } 
    }

the value of p may be actually larger or equal to b[i].first and this is problematic.

8

cook your dish here

T=int(input())
def list_to_str(l):
pattern=""
for x in l:
pattern+=str(x)+" "
print(pattern)
for _ in range(T):
n=int(input())
l1=list(map(int,input().split()))
l2=[]
l1.sort()
for x in l1:
for i in range(x):
if l2.count(i)==0:
l2.append(i)
break
else:
l2.append(0)
list_to_str(l2)
Can someone please tell where I am going wrong.

9

Can somebody please tell me why is my code getting tle?
CodeChef: Practical coding for everyone

10

Solved! I had to define my pair array outside of int main ! :confused: