pritishn's blog

[Help] CSES:Grid Paths , making all variables long long gives Accepted but using int gives TLE.
By pritishn, 4 years ago, In English

For the Grid Paths problem, if I use #define int long long and submit the solution, it gets accepted verdict, but using int gives time limit exceeded. How is this possible?

Link to accepted with long long : https://cses.fi/paste/6c2a837ed715717813be49/
Link to TLE with int : https://cses.fi/paste/1298e773dc80a66513be46/

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

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Run it locally and measure the time. Maybe both versions are close to TL and you just got lucky once.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I ran them locally 5 times ..
    flags : -Wno-unused-result -O2 -std=c++17

    using int
     0.74103 sec
    0.756871 sec
    0.79994 sec
    0.738276 sec
    0.733718 sec

    using long long
     0.691453 sec
    0.68186 sec
    0.689874 sec
    0.697802 sec
    0.683085 sec

    How can the long long version be faster? Have you ever encountered something like this?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      It is platform and compiler dependent. Usually the operations on types of target CPU's native word length are no slower (and usually faster) than the operations that might require casting the width to native size.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +4 Vote: I do not like it

        Oh, that explains it! I used custom invocation (on 32bit C++17) here on codeforces and it gave predicted results.

        long long = Used: 1014 ms, 0 KB
        int = Used: 561 ms, 4 KB

        Thanks Actium for the answer.

        → Reply