LEALCO GIVING WA

general
,
1

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

2

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

3

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.

4

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.

5

This is only because I have access to this page:
http://campus.codechef.com/files/stderr/1728327/
as a co-author of this problem :slight_smile:

On this page:
http://campus.codechef.com/viewsolution/1728327/
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.

6

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)

7

Explanation of why init of res leads to AC.

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


```
For(k,i,n+1){
    arr[k]+=1;
```

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:
http://www.codechef.com/viewsolution/1728612
So it seems that my understanding of this bug is correct :slight_smile:

1 Like
8

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

9

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