thanhchauns2's blog

By thanhchauns2, history, 3 years ago, In English

Hi everyone, recently I came across this problem in the problemset, which I have came up with a solution like this: 125580675, which turned out to be RTE on test 7 in the system tests. I managed to copy the test to run and debug it locally, but it gave a correct answer and didn't help me anything.

The #7 test looks like this:

Test case #7

My solution on local IDE output this solution:

Output

For everyone who is reading this, excuse me, can you help me find the bug? I couldn't find it however I try.

Thank you so much for reading this! Hope you have a great standing in the next contests ^_^

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

| Write comment?
»
3 years ago, # |
  Vote: I like it -33 Vote: I do not like it

I wonder why you guys downvote this? Asking for help is being guilty?

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

If you submit the same code with C++17 (64 bit), you would get WA on test 8

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I think the reason is that overflow occurs on line 716 because .size() returns an unsigned int and K1.size() is less than K2.size():

ll sum = N * (K1.size() - K2.size());

Also, the solution works fine (doesn't RE) with codeforces's 64 bit g++, though I don't know why.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    In 64 bits the computation overflows to the correct value of sum (negative) because the right hand side is multiplied using 64-bit unsigned integers, while in 32 bits the multiplication will only be done using 32-bit unsigned integers before being converted to ll, resulting in loss of information.

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

    Thank you for telling me this! I didn't know .size() return unsigned int. Now I got it accepted.