The codeforces round #742 has recently ended, and I cannot understand why the brute force solutions of problem B are not giving TLE on system testing. We require the Xor values of the range [0,1,2,...,a-1], where a<=3e5 for 5e4 test cases. The Editorial says that Xor values can be precomputed in O(n) time, and then the test cases can be answered in O(1) time. Still, I have seen many submissions who have calculated these range Xor values individually for every test case and still didn't get TLE. Isn't the overall complexity for this operation supposed to be O(t*a)? Which is roughly around O(15e9) or O(1e10). I saw someone saying it got AC because of 'Pragmas'. Pragmas or not. Shouldn't 1e10 give TLE? Are Pragmas these powerful, or is there something I'm missing? Ps: I myself got AC using the said Brute Force, but I resubmitted thinking it would give TLE on system testing.
Yes I also realized later and was pretty shocked as my solution got accepted with this approach of calculating xor each time. Link to my submission link
Yeah i agree with u.
Sometimes I regret giving contests on Codeforces :( because of this reason.
I got TLE with that approach
I think you would have gotten AC had you used Pragmas.
I got tle even with pragmas. Here's the link 127947420
You need unroll loops
this saved me, I overlooked that sum of a is not bounded xD
I checked my contest room after your blog post, but there don't seem to be any hackable solutions. Most of them just used code from https://www.geeksforgeeks.org/calculate-xor-1-n/
I didn't got a TLE either , i calculated the xor of all values from 0 to a-1 but used a different method to calculate xor of all values. link to my sol : https://codeforces.com/contest/1567/submission/127968252
same here I have submitted the same code with pragma it got accepted but without pragma, its giving TLE without pragma (TLE)-> https://codeforces.com/contest/1567/submission/127985611 with pragma (ACCEPTED)-> https://codeforces.com/contest/1567/submission/127985840
what is pragma and why its not giving tle?
These pragmas are a way to smuggle different compiler optimization options, which happen to be more aggressive/better than the codeforces defaults: https://gcc.gnu.org/onlinedocs/gcc/Function-Specific-Option-Pragmas.html
thanks:)
Yeah, unfortunately because bitwise operators are so fast, it is hard to fail such solutions. My thinking was that if people managed to get a solution through with pragmas, it would be okay. We also thought that setting $$$\mathcal{O}(1)$$$ constraints would be too hard.
We also have a max test in the pretests. But as you said, pragmas and bitwise operators make all such solutions very fast. Sorry.
It shouldn't be too hard to fail such solutions.
Autovectorization and the use of SIMD instructions provides a 8-16x speed boost maximum in best cases. A part of this speedup may be eaten by loop overhead in tight loops, unless loops unrolling is enforced too. But that's all. And in reality, doing some customtest benchmarks with https://codeforces.com/contest/1567/submission/127985840 demonstrates only ~4 times speedup without loops unrolling and ~7 times speedup with loops unrolling.
For comparison, calculating something per single testcase vs. calculating it once per whole program execution may slowdown everything by a factor of $$$t = 5 \cdot\ 10^4$$$ and this is too much to be compensated by pragmas. That is if the other constraints are right.
Also the whole pragmas business exists primarily because the codeforces gcc command line options are not aggressive enough. Why not use
-O3 -funroll-loops -march=native -mtune=nativeinstead of-O2? If this is done, then custom pragmas to smuggle better compiler options would be only useful for minor finetuning. And everyone would get realistic performance numbers for their submissions.Well, I guess we should have had you as a tester :P. I myself am not very skilled about what goes on behind the scenes in C++ — to me pragmas are magic black boxes. Thanks for the detailed description!
And yes, sorry again for not seeing this beforehand. It is my mistake. Our idea was that hopefully anyone who was calculating the $$$\operatorname{XOR}$$$ from $$$1$$$ to $$$n$$$ would immediately see that prefix precomputation would be enough, but it appears not.
I got tle with that
Strange, I got a TLE when i calculated xor from 1....a for every test case. So i later used the a % 4 trick to get AC
TLE Soluntion https://codeforces.com/contest/1567/submission/127953349
It was giving TLE in python. I had to think for over half an hour to figure out that cumulative xor of n is 0 if (n == 4*k-1, k>1). so i only had to calculate xor of atmost 4 values.