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?
I would also like to add that many people wait for recent problems' ratings to be updated
GCC 9-64, 468 ms: https://codeforces.com/contest/1874/submission/226074388
GCC 7-32, 1450 ms: https://codeforces.com/contest/1874/submission/251101057
Slower, but acceptable.
But the standard code given by the editorial can't get accepted. https://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.
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.We need 64-bit C++
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.
Yes, we need C++17/20(64) back
I finally got AC with your code! 251136206
It took 30 submissions to go from 20185ms to 7956ms, optimizations used:
Bump allocator
Added mint template
Faster modular multiplication (32 bit)
Faster mod operation
2D array to 1D:
C[i][j] → C[i * n + j]C++14 (GCC 6-32)is 2 times faster thanC++17 (GCC 7-32), perhaps GCC 6 was smarter in this case?Last but not least, thanks to GCC Optimization Pragmas
omg that was insane
Thanks for your optimization!!
Make the 64-bit version greater again!