DESTROY - Editorial

shubham99 · January 25, 2016, 12:50am

Correction - “We need to design an algorithm which reduces the chance of being unlucky and increases the change of being lucky.” instead of “We need to design an algorithm which reduces the chance of being lucky and increases the change of being lucky.”.

vsp4 · January 25, 2016, 12:58am

Consider the following case:

6

2 2 4 4 6 6

Your gives ans as 4, it should be 3. You need not pair to the same element always. So just subtract 1 and push back till it becomes zero

vsp4 · January 25, 2016, 1:06am

@rahul1995 a-b means you are pairing to the same element. Thats why its pairing 6,4 and 6,4 in the same case leaving behind 2 2 only.

Look at my similar submission: https://www.codechef.com/viewsolution/9227972

rahul1995 · January 25, 2016, 1:08am

Oh yes! Couldn’t think of that…Thanks

bodmas · January 25, 2016, 1:08am

Excellent. How did you come up with that? Why does it work?

anup_coder · January 25, 2016, 1:18am

Can someone find mistake in my


[1]


  [1]: https://www.codechef.com/viewsolution/9231730
though i manually checked different test cases.

shubhamrawat · January 25, 2016, 1:20am

Please can someone provide the test case where it fails?
My Submission

c0der · January 25, 2016, 11:05am

I want to submit for this problem but the submit button is not available

chinmay2 · January 25, 2016, 3:10pm

What is wrong with this


[1]??


  [1]: https://www.codechef.com/viewsolution/9230426

rahul2907 · January 25, 2016, 4:32pm

@shariquemohd you can directly submit to: https://www.codechef.com/submit/DESTROY ,i had just submitted like this.

dusht1408 · January 25, 2016, 5:10pm

Can’t see the solution.XML error.

drgn_hart · January 25, 2016, 5:27pm

I used a similar approach but not O(n). I think it is correct because there will exist a number different than itself to pair it with if occurrence of a number is less than half of the size of the array. On the other hand if a number repeats more than n/2 times you cannot find a number to pair it with after (size - maxcount) times. Hope you understood why it is right.
I used a different approch to calculate count and https://www.codechef.com/viewsolution/9228170 is the link to my solution.

uddhav · January 25, 2016, 7:00pm

Can someone please provide any test case in which given code gives wrong output.

tonysta · January 26, 2016, 7:25pm

Implemented using Max Priority Queue. But still getting WA.
Tried all the above test cases and Passed.
Can Anyone tell other test cases where my code might have failed
here is my link to solution https://www.codechef.com/viewsolution/9240904

code_hard123 · January 26, 2016, 8:37pm

Want to know where this solution fails.

https://www.codechef.com/viewsolution/9236770

abdul01010 · January 26, 2016, 8:47pm

XML error.!

tonysta · January 27, 2016, 9:05am

I have implemented using max heap.
I have passed all the test case given above.
But Still getting WA
Can someone tell me any test case where my code might fail.
my solution link
https://www.codechef.com/viewsolution/9240904

airdroidforpc · January 27, 2016, 12:39pm

Trying to submit but it doesn’t seems to work, submit

archit910 · January 27, 2016, 6:22pm

excellent

archit910 · January 27, 2016, 6:34pm

What will be the answer of this test case
1
10
1 1 1 3 3 3 2 2 2 2
and how ?
will it be 6 or 5?