Hi all,↵
↵
I would like to share something which happened with me in today's contest. I solved the following problem: [Strong Password](https://mirror.codeforces.com/contest/1845/problem/C). Here is my submission link: [Submission](https://mirror.codeforces.com/contest/1845/submission/211501589).↵
↵
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.
↵
I would like to share something which happened with me in today's contest. I solved the following problem: [Strong Password](https://mirror.codeforces.com/contest/1845/problem/C). Here is my submission link: [Submission](https://mirror.codeforces.com/contest/1845/submission/211501589).↵
↵
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.
