DESTROY - Editorial

editorial
, , , ,
21

Want to know where this solution fails.

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

1 Like
22

XML error.! :frowning:

23

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

24

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

25

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?

26

@archit910
answer of this test case 1 10 1 1 1 3 3 3 2 2 2 2 will be 5
5 pairs are:
(1,2)(1,2)(2,3)(2,3)(1,3)

27

I want to know where i am going wrong in my code and which test case my code is failing.
please help!!!

28

or u can find a pair in which u have the highest frequency and lowest,it is algebraically equivalent to taking pair of highest frequencies when u sum it all up.

29

how is complexity of editorialist code is (n*logn)…??

suppose there is two number in priority queue

a=1e9

b=1e9-1;

this will goes to approax 1e9 times??

30

1
6
1 2 3 1 2 3

Optimal answer is 3,not 4.

31

Got it. Thanks!

32

1
6
1 1 2 2 3 3
Your code produces 4 as answer . The right answer is 3.

33

SAME here bro :frowning:

34

try 1 1 2 2 3 3

35

@arpn why the answer for 1 6 1 2 3 1 2 3 is 3. It should be 4??

36

@amunation: The answer for 1 1 2 2 3 3, should be 3. See the following pairs (1,2),(2,3),(3,1) can be destroyed in 3 steps.

37

@sid02 my fault. I considered 1 and 6 to be the elements of the array.

38

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.”.

1 Like
39

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

1 Like
40

@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: CodeChef: Practical coding for everyone