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

Автор blackBird, 12 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

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

If it happened to me as well an explanation please

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.