Karam_Kallasi's blog

By Karam_Kallasi, history, 6 weeks ago, In English

Can anyone help me to know why the first code gets Wrong answer and the second one gets Accepted(the only difference in the name of the array) Wrong answer code : 256383748 https://mirror.codeforces.com/contest/467/submission/256383748

Accepted code : 256383722 https://mirror.codeforces.com/contest/467/submission/256383722

you can compare them and see that there is no difference..

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Edit: Never mind, I misread the code.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    No it's not 2*a[i] + a[i-1], both pre[i] = pre[i-1] + a[i] and a[i] = a[i-1] + a[i] are doing normal prefix sum.

    it's adding a[i] one time, not two, cuz it's assignment = not adding +=

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah you're right, I wasn't thinking straight.

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Out of bound index here: pre[id+m-1].

You can double the value of N and keep everything the same.

»
6 weeks ago, # |
Rev. 7   Vote: I like it +4 Vote: I do not like it

I found the bug

Here is the accepted one: 256401238

Here is the same code but with the wrong answer: 256401281

The wrong answer one has this problem in this line (which I don't understand why it's causing it WA)

ll n , m , k , /* h[N]  ,*/ a[N]  ; // Strange Bug

Uncomment the declaration of h[N], and this code would get you ACCEPTED.

If anyone has an explanation for that, please tell us.


EDIT: The issue was about going out of bounds a[id+m-1], as mentioned by MuhammadSawalhy. That's why when we added an extra array, it worked and got accepted. with the extra array, we got the accepted answer because going out of bounds made it take the 0 value from the second array, but without it, it would just take a garbage value.

To fix this, increase the size of array 'a' so that it gives zero when id+m-1 exceeds the bounds.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    like it takes memory from the extra array that I defined before a[] ?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yes, accessing memory out of bounds might sometimes lead to accessing valid values from other variables or arrays due to the memory layout, but this behavior is not guaranteed so don't rely on this behavior, as it can be unpredictable