Hi Codeforces, I was trying to solve this problem, and I was struggling to see why my code TLEs when other people's code (you can search up cses hamming distance solution for this) passes with similar logic.
Turns out when I add #define int long long, my code magically passes and becomes quite a bit faster. I am dumbfounded by this phenomenon, and the only explanation that was somewhat reasonable was this (which is still crazy to me).
I guess sometimes long long really is faster than int.
Auto comment: topic has been updated by kunzaZa183 (previous revision, new revision, compare).
Auto comment: topic has been updated by kunzaZa183 (previous revision, new revision, compare).
The most expensive part of your code is
__builtin_popcountcalls. Even after#define int long longit's still a function that takes anunsigned intargument; forlong longyou should call__builtin_popcountllinstead.To speed up this function, you should use
#pragma GCC target("popcnt"), which converts it to the corresponding processor instruction (for the same result you may use a newer target like"avx"or"avx2"). Without the pragma, compiler uses an $$$O(\log 32)$$$ algorithm for this computation.I have no idea why your code speeds up after
#define int long long. Do you barely fit into TL, or is there a significant margin?Here are the results for the original code
Here are the results for the code with
#define int long longThere isn't much difference, but some test cases go from TLE (which is more than 1 second) to running in 0.8 seconds The other correct test cases also become faster, but not by much.
I've also tried putting in
#pragma GCC target("popcnt")as you have mentioned, and it has sped up the program massively. The code runs in 0.2 seconds in the worst test cases compared to the original 0.8 seconds.I've also tried using
__builtin_popcountll()too, but it doesn't seem to change the runtime by much (less than 0.01 seconds).It's just very strange that
#define int long longspeeds up the program at all; I've always seen it as something that slows down the program, but apparently not in this case.I've also tried putting in #pragma GCC target("popcnt") as you have mentioned, and it has sped up the program massively. The code runs in 0.2 seconds in the worst test cases compared to the original 0.8 seconds.
And what happens when you add
#pragma GCC target("popcnt")without#define int long long?almost no difference whether or not I put
#define int long longwith#pragma GCC target("popcnt")(around 0.2s for worst test cases)This is interesting. Can you provide the compiler version which you used to submit the code? The same goes for compiler flags that are used. Also it is important to know the margin between TL and correct (second, with long long) solution runtime.
Sure. The compiler flags on CSES C++20 are
-std=c++20 -O2 -Wallwith g++ 11.4.0. I've posted the runtimes in the reply to the previous comment.Auto comment: topic has been updated by kunzaZa183 (previous revision, new revision, compare).