era404's blog

By era404, history, 11 months ago, In English

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

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by era404 (previous revision, new revision, compare).

»
11 months ago, # |
  Vote: I like it +57 Vote: I do not like it

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.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ow! nice explaination.... Now its clear what was happening.... Thank you