Page 1 of 1

11423 - Cache Simulator

Posted: Mon Mar 17, 2008 10:31 pm
by 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.

Posted: Wed Mar 19, 2008 12:36 am
by 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

Posted: Wed Mar 19, 2008 10:04 am
by 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.

Posted: Thu Mar 20, 2008 12:28 am
by baodog
Nevemind. Got accepted.