Блог пользователя OptimalKnight

Автор OptimalKnight, история, 3 года назад, По-английски

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 года назад, # |
  Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится -37 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

I got TLE with that approach

»
3 года назад, # |
  Проголосовать: нравится 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 года назад, # |
  Проголосовать: нравится +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.net/contest/1567/submission/127968252

»
3 года назад, # |
  Проголосовать: нравится 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.net/contest/1567/submission/127985611 with pragma (ACCEPTED)-> https://codeforces.net/contest/1567/submission/127985840

»
3 года назад, # |
  Проголосовать: нравится 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 года назад, # ^ |
      Проголосовать: нравится +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.net/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 года назад, # ^ |
        Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I got tle with that

»
3 года назад, # |
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

TLE Soluntion https://codeforces.net/contest/1567/submission/127953349

»
3 года назад, # |
  Проголосовать: нравится 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.