MedoN11's blog

Why does this code give AC and the other WA? They are nearly exactly the same...
By MedoN11, 10 years ago, In English

I have no idea, I find them really the same. I spent quite sometime debugging, but I can't reach anything.

Link to problem : http://www.spoj.com/problems/ACODE/

It's a dp problem.

Link to AC Solution ( C++ ): http://ideone.com/qYpw2x

Link to WA Solution (C++) : http://ideone.com/KxpmuI

If the code is not clear, or the logic. I can add more details.

Thanks.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

memset has wrong arguments. The third argument indicates the amount of bytes to be filled and as such should be 5001 * sizeof(long long). It works in one case because the array is initialized with zeroes (I believe that the arrays in heap get zero-initialized in C++, although I might be wrong or it might not be in the standard), so in the case of AC memset does nothing. In the case of WA about 3/4 of your dp end up being already "calculated" as 0.

Note that memset's second argument is also a byte. So, it works when filling ints with -1 because of two's complement, however it won't work with 1 for example in the fashion you might have expected.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Got it.

    Thanks alot for the help. AC :)

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also note it is possible to write

    sizeof memo instead of 5001 * sizeof (long long)

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

memset is wrong. Edit : I didn't see first comment

→ Reply