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 ?
If it happened to me as well an explanation please
I think contestant zhaozhiyun is just lucky. Because he got Accepted with time 3840ms of 4000 admissible.
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 alll[i]andr[i]. Your code reloads allv[a]for each query and thrashes the CPU cache. The cost of having the arrayslandris relatively low, as they are accessed linearly and the CPU can predict this.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)
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.
Okay :) Thanks :)