wsc2008qwq's blog

When can we have our C++17(64) back?
By wsc2008qwq, history, 9 months ago, In English

Gone crazy while solving problem 1874E - Jellyfish and Hack. I optimized my solution with best effort, and its execution time decreased from 20s at first to about 6s now (locally), but it got TLE on codeforces (time limit 8s).

When I was wondering how small the constant could be to pass the problem, I realized that I submitted with C++17(32), and I wanted to switch the language into C++17(64), but where is it???

What's more annoying is that almost all accepted submissions to this problem used C++17(64), mostly with an execution time longer than half of the time limit, so I think this problem can hardly be passed without C++17(64).

When can we have our C++17(64) back?

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

»
9 months ago, # |
  Vote: I like it +18 Vote: I do not like it

I would also like to add that many people wait for recent problems' ratings to be updated

→ Reply
»
9 months ago, # |
  Vote: I like it -26 Vote: I do not like it

GCC 9-64, 468 ms: https://mirror.codeforces.com/contest/1874/submission/226074388

GCC 7-32, 1450 ms: https://mirror.codeforces.com/contest/1874/submission/251101057

Slower, but acceptable.

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    But the standard code given by the editorial can't get accepted. https://mirror.codeforces.com/contest/1874/submission/251112344

    This solution used fast interpolating algorithm based on FFT so of course it's much more quicker. What I focus on is whether the intended solution can pass.

    Anyway, thanks for your reply and explanation.

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

      LL operations in the 32-bit environment are much slower than expected because there is no x64 CPU instruction nor registers to use. In that case, the 32-bit compilers could only simulate the x64 code by taking the data apart (high 32 bits and low 32 bits), calculating those parts individually (without efficient instructions either), and putting it back together.

      If the code depends heavily on LL type, it could highly TLE as those operations aforementioned are too slow. Also, this TLE on the editorial reflects that the proposer of this question may not have thought about other programming languages (especially those non-compile-based). They were too focused on the details of efficient algorithms and ignored the constant-level effects of the environment/different languages.

      Fun fact: LL type in 32-bit compilers may be a typedef of __int64.

      → Reply
»
9 months ago, # |
← Rev. 4   Vote: I like it -9 Vote: I do not like it

We need 64-bit C++

→ Reply
»
9 months ago, # |
  Vote: I like it +64 Vote: I do not like it

Why can the comments on this blog be so unrelated to the topic?

I think Codeforces should at least fix it before hosting any rated contest, or avoid problems that use 64-bit integer calculations, otherwise it may be unfair.

Of course, I can understand that this kind of bug must be very difficult to fix. So the above is just a beautiful wish of mine and some friends.

→ Reply
»
9 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Yes, we need C++17/20(64) back

→ Reply
»
9 months ago, # |
← Rev. 3   Vote: I like it +64 Vote: I do not like it

I finally got AC with your code! 251136206

It took 30 submissions to go from 20185ms to 7956ms, optimizations used:

→ Reply
»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Make the 64-bit version greater again!

→ Reply