blackBird's blog

Same solution but TLE !!!
By blackBird, 12 years ago, In English

Hi, This concerns two solutions of the same problems (problem D round 136 div 2 Link: http://www.codeforces.com/problemset/problem/221/D ).

The player, zhaozhiyun, submitted a code VERY similar to mine. His got accepted while mine got TLE'd. Here are the links to the two solutions.

His, Link 1: (Accepted one) http://www.codeforces.com/contest/221/submission/2081857 Mine, Link 2: (TLE one) http://www.codeforces.com/contest/221/submission/2078483

Can anyone tell why mine got TLE'd while his accept even though we have almost the same codes ?

Is it because of different server load during system test, etc ?

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

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If it happened to me as well an explanation please

→ Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I think contestant zhaozhiyun is just lucky. Because he got Accepted with time 3840ms of 4000 admissible.

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

This is what I think:

In the final part of the solution, zhaozhiyun's code loads each v[a] into the CPU cache only once and then iterates over all l[i] and r[i]. Your code reloads all v[a] for each query and thrashes the CPU cache. The cost of having the arrays l and r is relatively low, as they are accessed linearly and the CPU can predict this.

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

    Hi, Your explanation seem fair and valid.

    But it is still hard for me to digest it got TLE'd. Here are my complexity calculations.

    Order — ( n + n + m x icount x log(n)) --> O(m x icount x log(n)). Max For m : 1e5, icount: 450, log(n): 17 Worst case: 1e5 x 450 x 17 = 7e8 which is still good enough for 4 seconds! (Moreover, the worst case is hypothetical one)

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

      7e8 is not still enough for 4 seconds. Because there is some constant in asimptoty. for example, vector works more than O(1). And other operations are not simple (like + or — ). So it is normal, that your code got TLE.

      → Reply