### OptimalKnight's blog

By OptimalKnight, history, 3 weeks ago,

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.

• +44

 » 3 weeks ago, # |   +9 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
•  » » 3 weeks ago, # ^ |   0 Yeah i agree with u.
 » 3 weeks ago, # |   -37 Sometimes I regret giving contests on Codeforces :( because of this reason.
 » 3 weeks ago, # |   +16 I got TLE with that approach
•  » » 3 weeks ago, # ^ |   +14 I think you would have gotten AC had you used Pragmas.
•  » » » 3 weeks ago, # ^ |   0 I got tle even with pragmas. Here's the link 127947420
•  » » » » 3 weeks ago, # ^ |   +34 You need unroll loops
•  » » » » » 3 weeks ago, # ^ |   0 this saved me, I overlooked that sum of a is not bounded xD
 » 3 weeks ago, # |   0 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/
 » 3 weeks ago, # |   0 I got TLE with the same method Submission link : https://codeforces.com/contest/1567/submission/127948781
 » 3 weeks ago, # |   +3 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
 » 3 weeks ago, # |   0 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
•  » » 3 weeks ago, # ^ |   0 what is pragma and why its not giving tle?
•  » » » 3 weeks ago, # ^ |   0 actually, I am also searching for it I have seen my friend's code which is just different from pragma nothing else then I got it.
•  » » » 3 weeks ago, # ^ |   0 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
•  » » » » 3 weeks ago, # ^ |   0 thanks:)
 » 3 weeks ago, # |   0 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.
•  » » 3 weeks ago, # ^ |   0 If you guys where aware of this situation, then why don't you put constraints on sum of b over all test cases?
•  » » 3 weeks ago, # ^ |   0 But I think most of the people got through the question.
•  » » 3 weeks ago, # ^ |   +20 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=native instead 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.
•  » » » 3 weeks ago, # ^ |   +14 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.
 » 3 weeks ago, # |   0 I got tle with that
 » 3 weeks ago, # | ← Rev. 2 →   +3 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
 » 3 weeks ago, # |   0 Yesterday, I submited that kind of solution and it give me tle, then I adjust it by placing it outside and I get AC.
 » 3 weeks ago, # |   0 i got TLE in B problem
 » 3 weeks ago, # |   0 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.
 » 3 weeks ago, # |   0 what is pragma?i got TLE in brute forcethen i used 4% trick & AC.