OptimalKnight's blog

Weak test cases?
By OptimalKnight, history, 3 years ago, In English

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.

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

Comments Comments (20)
| Write comment?
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -37 Vote: I do not like it

Sometimes I regret giving contests on Codeforces :( because of this reason.

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

I got TLE with that approach

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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/

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

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://mirror.codeforces.com/contest/1567/submission/127968252

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

same here I have submitted the same code with pragma it got accepted but without pragma, its giving TLE without pragma (TLE)-> https://mirror.codeforces.com/contest/1567/submission/127985611 with pragma (ACCEPTED)-> https://mirror.codeforces.com/contest/1567/submission/127985840

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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://mirror.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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I got tle with that

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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://mirror.codeforces.com/contest/1567/submission/127953349

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply