Can someone explain why my solution is getting WA in this problem - https://www.codechef.com/problems/DESTROY

Here is my solution - https://www.codechef.com/viewsolution/13196621

Thanks !!

Can someone explain why my solution is getting WA in this problem - https://www.codechef.com/problems/DESTROY

Here is my solution - https://www.codechef.com/viewsolution/13196621

Thanks !!

1 Like

Your code is failing on these test cases-

```
Compilation Successful
Input (stdin)
1
6
1 5 6 6 5 6
Your Output
4
Expected Output
3
Compilation Successful
Input (stdin)
1
4
1 5 6 6
Your Output
3
Expected Output
2
```

Logic- We can eliminate as-

Test Case 1

- 1,6
- 5,6
- 5,6

So 3 operations. I think what your code is doing is, eliminating 1,5 , then a 6,5 and getting left with 6,6.

Test case 2-

- 1,6
- 5,6

So 2 operations.

Reason- This error possibly arises when we only check adjacent elements. The problem states that operation one can “Choose **any** 2 elements” . Your solution works nicely when such elements are placed adjacently. Try to think more and accommodate this “any two element” feature too.

2 Likes

YOur code is failing here:

```
1
22
39 41 40 16 13 1 19 4 45 1 25 31 10 8 13 10 30 24 29 42 33 33
**Correct output:** 11
**Yours' output:** 12
```

1 Like

as already test cases have been provided by @bansal1232 and @vijju123

suggestion for your algorithm : first sort all your elements according to their frequency in decreasing order , then your algorithm would work fine.

happy coding:)

i have made neccessary changes but it is still giving WA

```
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
map<int,int> mp;
FORN(i,n)
{
int a;
cin>>a;
mp[a]++;
}
priority_queue<int> pq;
for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++)
{
pq.push(it->second);
}
int ans=0;
int k1 = 0,k2=0;
while(!pq.empty())
{
if(pq.size())
k1 = pq.top(),pq.pop();
if(pq.size())
k2 = pq.top(),pq.pop();
if(k1 == 0)
ans += k2;
else if(k2 == 0)
ans += k1;
else
ans += min(k1,k2),pq.push(ABS(k1-k2));
k1 = k2 = 0;
}
// cout<<pq.top()<<endl;
cout<<ans<<endl;
}
}
```

Correct output is 11

Formatted the code for clarity.

plz can u say which test case is it failing ??

It seems that repeating patterns are giving your code a tough time dear. Take this testcase for example-

```
Compilation Successful
Input (stdin)
1
9
1 2 3 1 2 3 1 2 3
Your Output
6
Expected Output
5
```

The order of removal being being-

- 1,2
- 3,1
- 2,3
- 1,2
- 3

Can you explain your approach? We might be able to suggest some improvements in logic/approach/implementation

1 Like

each time I’m popping top 2 frequecies(occurrences) of elements and taking their minimum(as we can eliminate their minimum in one chance) and pushing their absolute difference into the p_queue. And if only one element exists in the queue then no pushing done.

I thing i got the error. Since im eliminating the same pair together, hence im left with same elements at the end and the cost in eliminating them = no. of elements left out.

Thanks a lot!! @vijju123

1 Like

Its a VERY good practice to self-analyse. Will take you far in contests, take this word of mine.

1 Like