### era404's blog

By era404, history, 4 months ago,

Problem Link: https://codeforces.com/contest/514/problem/A Submission1 : https://codeforces.com/contest/514/submission/206932949 which gives me RTE but in next submission the same code is AC.

accepted submission: https://codeforces.com/contest/514/submission/206933863

• +2

 » 4 months ago, # |   0 Auto comment: topic has been updated by era404 (previous revision, new revision, compare).
 » 4 months ago, # |   +57 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: for(ll i=v.size()-2;i>=0;--i){ 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() equals 1. 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 as unsigned int). When subtraction goes below zero on unsigned integers, integer overflow happens. In this case, the value of v.size()-2 will be equal to $2^{32}-1$ or 4294967295. Since this value is put into a signed 64-bit variable, there are enough bits to store the value and the loop will start at i = 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$ or 18446744073709551615. 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 or long long like this: for(ll i=(int)v.size()-2;i>=0;--i){ or for(ll i=(ll)v.size()-2;i>=0;--i){ This will ensure that the subtraction is done on signed integers and will not overflow.
•  » » 4 months ago, # ^ |   0 Ow! nice explaination.... Now its clear what was happening.... Thank you