[Solution] Maximum Number Of Distinct Elements solution codechef | SnackDown 2021 – Online Qualifiers

SnackDown 2021 - Online Qualifiers - CodeChef

Maximum Number Of Distinct Elements solution codechef

Given an array BB of length NN, find an array AA of length NN where 0Ai1090≤Ai≤109 such that array CC where Ci=AimodBiCi=AimodBii{1,N}∀i∈{1,N} has maximum number of distinct integers.

In case of multiple answers, print any.

Maximum Number Of Distinct Elements solution codechef Input Format

  • First-line will contain TT, the number of test cases. Then the test cases follow.
  • Each test case contains two lines of input.
  • First-line contains a single integer NN.
  • Second-line contains NN space-separated integers B1,B2,,BNB1,B2,…,BN.

Maximum Number Of Distinct Elements solution codechef Output Format

For each test case, output in a single line NN space-separated integers A1,A2,,ANA1,A2,…,AN, the elements of the array AA such that array CC has the maximum number of distinct elements.

If the output array doesn’t follow the constraints or the number of distinct elements in the array CC is less than the optimal value, you will receive a wrong answer verdict.

Maximum Number Of Distinct Elements solution codechef Constraints

  • 1T1051≤T≤105
  • 1N21051≤N≤2⋅105
  • 1BiN1≤Bi≤N
  • 0Ai1090≤Ai≤109
  • Sum of NN over all tests is atmost 106106.

Maximum Number Of Distinct Elements solution codechef Sample Input 1 

3
3
2 1 3
2
1 1
6
1 2 3 3 2 1

Maximum Number Of Distinct Elements solution codechef Sample Output 1 

3 1 2
2 3
0 1 2 3 4 5

Maximum Number Of Distinct Elements solution codechef Explanation

Test Case 11: Array C={3mod2,1mod1,2mod3}={1,0,2}C={3mod2,1mod1,2mod3}={1,0,2}. So the number of unique elements are 33.

Test Case 22: Array C={2mod1,3mod1}={0,0}C={2mod1,3mod1}={0,0}. So the number of unique elements is 11.

Test Case 33: Array CC ={0mod1,1mod2,2mod3,3mod3,4mod2,5mod1}={0mod1,1mod2,2mod3,3mod3,4mod2,5mod1} ={0,1,2,0,0,0}={0,1,2,0,0,0}. So the number of unique elements are 33.

In all the 33 cases, the number of unique elements can’t be increased any further for any choice of the array AA.


Updating Soon…


Maximum Number Of Distinct Elements solution codechef

Game of Length solution codechef

 

Leave a Comment

Your email address will not be published. Required fields are marked *