Блог пользователя phantom654

Автор phantom654, история, 4 года назад, По-английски

For this problem, I submitted a code1 and it gave Runtime error. Here I have used long long int as the data type for all suitable variables using a 'typedef long long int ll' declaration at top

Now I just changed all the data types to 'int' by changing it to 'typedef int ll' and everything worked fine code2

In some other submission I changed the string declaration to char and again everything worked fine [code3](https://codeforces.net/contest/1363/submission/82147815)

I am not really able to understand the failure of code1. Please help me out !!!

** For this problem my friend too faced the same issue. ***

Failed code

Passed code — just changed long long int to int

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

I'm not sure, but it might be because of this:

for(ll i=s.length()-2;i>=0;i--)

s.length() has unsigned int type. When it's $$$1$$$, the result of s.length()-2 is $$$2^{32}-1$$$ due to overflow. If we try to cast it to long long, it remains $$$2^{32}-1$$$, so you try to access an incorrect index. But if we try to cast it to int, $$$2^{32}-1$$$ cannot be represented in int type, and it becomes $$$-1$$$ instead. So two overflow errors cancel themselves.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Yes this is the reason. When I print s.length()-2 it gives 4294967295(2^32-1) ( IN Codeforces IDE), and 18446744073709551615(2^64-1) in my local IDE(GEANNY 1.36) and in ONLINEGDB.

    So while casting (2^64-1) to ll, it is changed to -1. This is the reason my code was not running in codeforces IDE and was working fine in some other IDEs

    **This too seems weird as both are using GCC compiler only, ** but have different return types for s.length().BledDest Can you please clearify this

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The type of s.length() depends on the compiler. On most CF C++ compilers, it is a 32-bit number; though on C++ 17 64bit it's a 64-bit number. That's because most C++ objects (including string) use a synonym of std::size_t to store their size, and std::size_t can store the maximum possible size of an object — that's why it's a 64-bit number on 64-bit compilers, but a 32-bit number on 32-bit compilers.

      The common way to deal with these problems is to never rely on overflows and always make sure to cast size variables to signed types if you want to subtract something from them.