11423 - Cache Simulator

[sclo]

I keep getting TLE for this problem. I see that some people did it in less than 2 secs. We're given that there are at most 20000 lines, and at most 30 cache simulations, an at most 10^7 data references. For each data reference, my algorithm takes O(1) time (about 12 operations), so I don't see why it is TLE.

[rio]

Hard problem. Finally got AC after 20+ submissions.

Just only O(1) algorithm is not enough. Needs a efficient implementation.
First I was using deque, but it was using too much memory, and the memory access cost was causing TLE.
The upper limits of this problems is large, so you must be careful in memory accessing.

-----
Rio

[greve]

There is a good discussion about this problem on the topcoder forums:
http://forums.topcoder.com/?module=Thre ... 02&start=0

I implemented the algorithm mentioned and got AC in 1.320 seconds.

[baodog]

Nevemind. Got accepted.