Problem Link: https://codeforces.net/contest/514/problem/A Submission1 : https://codeforces.net/contest/514/submission/206932949 which gives me RTE but in next submission the same code is AC.
accepted submission: https://codeforces.net/contest/514/submission/206933863
You should notice that you changed the language of the submission: C++17 versus C++17 (64). The first one uses 32-bit architecture while the second one uses 64-bit architecture. This is what is happening:
Let's look at the following line:
The problem occurs you try to calculate
v.size()-2
. In the third test case, $$$n = 1$$$ and it has only one digit. The size of the vector will be equal to 1. Now,v.size()
equals1
. Thus,v.size()-2
equals-1
, right? Actually, no.v.size()
and other container sizes are always stored in an unsigned integer type. On a 32-bit architecture this is a 32-bit unsigned integer (i.e. the same asunsigned int
). When subtraction goes below zero on unsigned integers, integer overflow happens. In this case, the value ofv.size()-2
will be equal to $$$2^{32}-1$$$ or4294967295
. Since this value is put into a signed 64-bit variable, there are enough bits to store the value and the loop will start ati = 4294967295
indexing the array out of bounds and giving you RTE.In the second submission, the same problem occurs. This time
v.size()
is a 64-bit unsigned integer. Overflow happens with the subtraction and now,v.size()-2
will be equal to $$$2^{64}-1$$$ or18446744073709551615
. This will now be stored in a signed 64-bit variable. But the signed 64-bit variable does not have enough space to store this big positive integer. It will be converted to the negative equivalent value, which is exactly $$$2^{64}$$$ less than that positive value. Thus, the negative value will be the original $$$-1$$$ and the code will run succesfully.The best way to avoid this mistake is to always typecast container sizes to
int
orlong long
like this:or
This will ensure that the subtraction is done on signed integers and will not overflow.