I am doing backtracking, checking all permutations and saving the least value of operations and printing it. But my program is giving WA. I struggled more than 13 days , still cann’t find the what’s wrong.ADMIN Please help. My sol is : http://ideone.com/K0x9CH

please provide me some test cases where my solution will go wrong.

Your last submit at codechef returns 2 for the following test:
17 9 2
17 17 17 17 16 17 15 16 16 16 15 16 15 15 15 17 17
While the correct answer is 3.

And I have deleted you answer from editorial to not have duplicate questions.

Thanks, you are great, I don’t know how you did that, I am still in a surprise how did it print 2, because when I am printing all the valid sequence permutations and its respective operations the least value is 3 but when I am printing the final answer it prints 2.

This is only because I have access to this page:
as a co-author of this problem :slight_smile:

On this page:
I found at what test case your solution fails.

And then extract the proper sub-case where your answer differs from our answer.

So no magic.

It got AC but I still don’t understand what the problem was. I want to tell what change I made, what I cann’t understand the importance of this change.In my above code I declared (int res;) globally but didn’t initialise it. But when I initialise (res=18) there in the beginning, it gives correct answer. How does it matter because for each test case, I initialise it even for the first test case(see my code I did it in while loop res=18)

Explanation of why init of res leads to AC.

This is because you are changing element a[18] sometimes.
You do this here:


when n=17 and k=n+1.

Now the reason of WA is that when res declared without initialization it most probably occupy the next 4 bytes after the array a[] in memory so changing a[18] leads to changing res.

But when you do initialization of res in declaring it is probably stored in some other place in memory and changing of a[18] leads to changing of t which of course is also seems bad. But since you revert a[k] back doing a[k]-=1 in the end of the loop the value of t remains the same after backtracking and nothing bad happens.

Just for curiosity I swapped declarations of res and t in your WA submit and get AC:
So it seems that my understanding of this bug is correct :slight_smile:

1 Like

I didn’t know that initialisations place it at some other place. Thanks for help. Really helpful.

Actually, what you should learn from here is that you should always check that you don’t access elements of array out of range.

You get AC here simply by luck. A bit correcter way is to extend array a[] to be int a[19]. But still it is some kind of hacking.

You should reiterate your solution and get rid of accessing a[n+1] since it is bad.

Next time you again could have WA because of not properly checked accessing of elements of the array.

1 Like