Hi all,

I would like to share something which happened with me in today's contest. I solved the following problem: Strong Password. Here is my submission link: Submission.

I was not sure why it was giving runtime error, and after the contest, I tried submitting it in C++20. It passed without any problem! Here is the code snippet which was the reason of runtime error:

string s;
cin >> s;
...
 
vvll post(s.size(), vll(10, -1));
... 
for (ll i = s.size() - 2; i >= 0; --i) {
    for (int j = 0; j < 10; ++j)
        post[i][j] = post[i + 1][j];
    ...
}

vvll is vector<vector<long long>>, vll is vector<long long> and ll is long long.

Can you identify the source of runtime error here? Hint: what if input string is "0"?

Most of us assume size_t to be unsigned long long (as most of us compile our code using 64bit compilers locally). But this is not true from C++ library point of view.

Reason of failure of above code in C++ 17 (32 bit compiler):

1. s.size() - 2 should semantically result in -1 and data type of size_t is unsigned integer of $$$4$$$ bytes.
   • This computation results in 0xFFFFFFFF ($$$4$$$ bytes, unsigned number).
2. LHS is of data type signed long long, which is $$$8$$$ bytes.
   • LHS can safely handle consecutive $$$32$$$ bits which are all set to $$$1$$$.
   • Thus, $$$i$$$ will be set to 0x00000000 FFFFFFFF which is $$$4294967295$$$.

Reason of above code passing in C++ 17 (64 bit compiler):

1. s.size() - 2 should semantically result in $$$-1$$$ and data type of size_t is unsigned integer of $$$8$$$ bytes.
   • This computation results in 0xFFFFFFFF FFFFFFFF ($$$8$$$ bytes, unsigned number).
2. LHS is of data type signed long long, which is $$$8$$$ bytes.
   • LHS can't handle consecutive $$$64$$$ bits which are all set to $$$1$$$.
   • That value of $$$i$$$ is implementation defined and we can all agree that most of the implementations will simply treat this number as signed one, without any change in data.
   • Thus, $$$i$$$ will be set to 0xFFFFFFFF FFFFFFFF which is $$$-1$$$ and the code works as expected.

Possible workarounds?

• We can change s.size() to (int)s.size() and the problem will be fixed. But this will mean that we need to put this everywhere where we are converting the result to long long in $$$32$$$ bit compilation.
• We can use int i instead of long long i which will work.
• We can use $$$64$$$ bit compilation to never bother about these nasty conversions :)
• (Edit — New point) As mentioned in comments, there are possible cases of similar problems in 64 bit as well. We can use ssize in place of size() member function.

I am going with last point as it was a headache to figure out the problem during contest. And the worst part? I tried every possible combination of input in my local environment when the contest was live and there was nothing I could do to resolve this issue. Every possible combination was working as expected.