DESTROY - getting WA

general
,
1

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
2

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. :slight_smile:

2 Likes
3

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
4

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:)

5

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;
    }
}
6

Correct output is 11

7

Formatted the code for clarity.

8

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

9

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. 1,2
  2. 3,1
  3. 2,3
  4. 1,2
  5. 3

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

1 Like
10

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.

11

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
12

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

1 Like