Lord.of.AMC's blog

385B (Bear and Strings)
By Lord.of.AMC, 11 years ago, In English

A lot of solutions (including mine) for problem B failed on test 36, and the only languages that failed in this way were C and C++. I noticed this was because in C and C++, the size of a string is an unsigned integer. This is not the same in other languages, however. Hence, if we repeat from 0 to s.size()-3 we are really repeating from 0 to some huge integer. In the case of test #36, it is 4294967294 which caused many of us to RE. No other language would have this error. Thus, a lot of substantially correct solutions got rejected because of this small semantical problem.

Did any of you who use C/C++ know that this was coming? Any suggestions on how to avoid this problem in the future? Thanks for your help.

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

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

You should always be careful when substracting something from unsigned integer. Instead of subtracting we can add 3:

for (int i = 0; i + 3 < s.length(); ++i)
→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It worked out for me when I wrote random tests and noticed the bug. So just try out minimal test cases at any problem ...

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

An approach not yet mentioned is to always compile with warnings enabled (-Wall option for GCC) and work to eliminate them. It would give a warning for

for (int i = 0; i < s.length () - 3; i++)

but have no complaints with the following:

for (int i = 0; i < (int) s.length () - 3; i++)

For programming contests where the size of everything can not exceed 2GB, an easy rule to follow is to always cast s.length () and such to int.

→ Reply