open the dragon scroll

why code chef is giving wrong answer for my code…while its giving me the desired output on my compiler…i have checked my code for various inputs and its giving me the right answer for all of them…
please check what’s wrong with it…here is my code http://www.codechef.com/viewsolution/4379071

Your code is giving wrong answer for the following test case:

1

8 170 1

your output is 143.

But the correct one is 248.
Let me explain.

binary of 170 is 10101010 .binary of 1 is 00000001
for 170 ,1111000 is a possible shuffle .For 1 00001000 is a possible shuffle.
therefore (1111000)xor(00001000) is (11111000),which is equal to 248.
You have succeded in finding the maximum number of (1,0)or(0,1) pairs but all these pairs must exist in the most significant side(left side), only then the answer will be maximum ,this is where you have erred by not checking it.

I have made a few changes in this part of your code:

 for(i=1;i<=n;i++)
    {
        s[i] =(pow(2,n-i)*e[i]);
    }

Since you have not checked if all the ones in the array "e" are moved to the left most significant side this part acts as the bug in your code.
I have changed this to 

int count =1;

    for(i=1;i<=n;i++)
    {   
        if(e[i]==1)
        {
         s[i] =(pow(2,n-count)*e[i]);
         count++;
         }
         else 
         s[i]=0;
    }

here is your corrected code which has got accepted. http://www.codechef.com/viewsolution/4380071
if you still have any doubts comment below.if you find this post helpful upvote and mark it as accepted answer.CHEERS HAPPY CODING :slight_smile:

3 Likes

thank u sooo much…i was missing that part… :slight_smile:

//