You are not logged in. Please login at www.codechef.com to post your questions!

×

MIXCOLOR - Editorial

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

This question is marked "community wiki".

asked 10 Mar, 06:13

adkroxx's gravatar image

7★adkroxx
306718
accept rate: 7%

edited 13 Mar, 15:06

admin's gravatar image

0★admin ♦♦
19.3k348495534


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

link

answered 13 Mar, 15:13

i_say_hello's gravatar image

1★i_say_hello
11
accept rate: 0%

edited 13 Mar, 15:13

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??

link

answered 13 Mar, 21:52

ayan_19's gravatar image

1★ayan_19
12
accept rate: 0%

edited 13 Mar, 21:59

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

(13 Mar, 23:04) ayan_191★

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.

link

answered 13 Mar, 22:49

azad123's gravatar image

4★azad123
212
accept rate: 0%

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

link

answered 13 Mar, 23:08

azad123's gravatar image

4★azad123
212
accept rate: 0%

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

link

answered 17 Mar, 22:48

vicerys's gravatar image

2★vicerys
1
accept rate: 0%

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

link

answered 21 Mar, 16:47

paradox64ce's gravatar image

2★paradox64ce
11
accept rate: 0%

edited 21 Mar, 16:50

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

link

answered 22 Aug, 00:11

executable's gravatar image

3★executable
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,010
×3,409
×921
×892
×743
×264
×7

question asked: 10 Mar, 06:13

question was seen: 1,574 times

last updated: 22 Aug, 00:11