step_by_step's blog

By step_by_step, 5 weeks ago, In English,

This is the same code submitted 4 times:

41614475 — AC (2620 ms)
41614527 — TL 4
41615246 — TL 3
41615282 — TL 46

The first submission spends 2137ms on the 3rd testcase while the third exceeds 3000ms.
Moreover I added this problem to my mashup to set custom TL. One submission spends 3432ms, another 3790ms.

So the difference is more than 1000ms.
The reason might be huge bitsets containing 300000000 elements which I use in my solution, but still I think that it isn't a correct behavior of Codeforces judge.

Does anybody know what causes this instability?

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it -54 Vote: I do not like it

"So the difference is more than 1000ms". Not 1000 but 100ms(or 300)

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I compared your solutions and found no differences (compared only first and second submissions). So I think that it's depends only on Ofast compiler flag and speed to access to memory (L1 and L2 cache) when solution works.

I speeded up your solution to 1.8 sec by added handmade bitset implementation. Now precalculating with Bitset in main function takes 0.9s against 2s with std::bitset on ideone server.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

    Yes, I know that all these solutions are identical. The problem is that my solution in this case is unstable, in most cases the precalculating works in 2s, but sometimes exceeds 3s.
    So I wonder if this instability is caused by std::bitset or CF judge.

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Codeforces measures against DDoS attack :) or just penalty for you-already-know-that-it-will-be-accepted submissions :3

»
5 weeks ago, # |
  Vote: I like it +39 Vote: I do not like it

Do you have similar variance on your machine as well?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +30 Vote: I do not like it

    When I run the code several times but don't do anything else with my computer it takes the same time. The maximal difference is 200ms.
    When I use other programs in the same time the code slows down by 1.5-2.0 times.

    So, maybe the changing of loading of CF servers causes this.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Perhaps. However, I've read somewhere that submissions that get TL are rerun in exclusive mode, so in theory that should not matter.