MIXCOLOR - Editorial

editorial
, , , , , ,
#1

PROBLEM LINK:

Div1, Div2

Practice

Author: Shivangi Gupta

Tester: Triveni Mahatha

Editorialist: Adarsh Kumar

DIFFICULTY:

Easy

PREREQUISITES:

Sorting

PROBLEM:

You are given an array with N elements. In one operation you can replace A[i] by A[i]+A[j] where j \neq i. Find minimum number of operations required to make each element of array pairwise distinct.

EXPLANATION:

Lets keep a track on the current maximum of the array. If we add maximum to any element already present in the array, it will give us a new maximum as well as new element that was not present in the array before. We can do this process for all the elements that are repeating. Hence total no. of operation required = N - (total unique elements already present in the array). You can prove this using contradiction if you want to.

Main problem here reduces to finding total number of unique elements present in the array. This task can be solved using sorting and linear traversal of the array.

Time Complexity:

O(N.logN)

AUTHOR’S AND TESTER’S SOLUTIONS

Setter’s solution

Tester’s solution

2 Likes
#2

It is showing access denied when trying to view setters/testers solution.

#3

hello, I had my solution for this problem up and running in the practice section with various test cases being successful, But still it gave SIGSGEV while submitting…Don’t know how to improve…where it was running successfully in other online ides.
here is my solution https://www.codechef.com/viewsolution/17767577

I know (I have mistakenly put a line which can lead to WA) , But even after removing that I keep getting that SIGSGEV Error.
I don’t see any wrong in the algorithm(as it ran successfully under various test cases in various online IDEs)…What modification can be done in the code to avoid the SIGSGEV Error??

#4

You are getting error due to this line
vs[(a[j])]+=1
as the value of a[j] can be up to 10^9 and the size of vs array is max+100 which is smaller than 10^9.
Also you can create maximum array of 10^6 only So you can not solve it by using this method.You need to sort the elements first and then count the number of duplicates.

#5

well this is the thing you can traverse only up to 10^6 in 1 sec.

#6

how will it work in the case when max element of array is already equal to 10^9??@author

#7

I solved it using C++

<set>

Theorem: The Number of minimum moves = number of extra color i.e.
Total colors- # of distinct colors.

Proof:
We can get a new color by adding a repeated color with the highest color.

This way its just O(N).

link My Solution

2 Likes
#8

simply, we can find the number of unique elements using a set.
for those who are using this through array traversal this is definitely going to give NZEC or SIGSEGV as the range is 10^9.
check out this solution:
https://www.codechef.com/viewsolution/19804820

#9

yes , thats why I used the array size 10^9 once but, it is giving TLE @azad123

#10

No it’s O(N*logN) because insertion in set data structure takes O(logN) time. As it’s implemented as a red-black binary search tree in GNU C++.

#11

O(n) with just four lines of code in java