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 ^_^
I wonder why you guys downvote this? Asking for help is being guilty?
If you submit the same code with C++17 (64 bit), you would get WA on test 8
Yes, I think I know where the bug is, thank you!
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():
Also, the solution works fine (doesn't RE) with codeforces's 64 bit g++, though I don't know why.
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.
Thank you for telling me this! I didn't know .size() return unsigned int. Now I got it accepted.