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):
s.size() - 2
should semantically result in-1
and data type ofsize_t
is unsigned integer of $$$4$$$ bytes.- This computation results in
0xFFFFFFFF
($$$4$$$ bytes, unsigned number).
- This computation results in
- 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):
s.size() - 2
should semantically result in $$$-1$$$ and data type ofsize_t
is unsigned integer of $$$8$$$ bytes.- This computation results in
0xFFFFFFFF FFFFFFFF
($$$8$$$ bytes, unsigned number).
- This computation results in
- 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 tolong long
in $$$32$$$ bit compilation. - We can use
int i
instead oflong 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.