11423 - Cache Simulator

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

11423 - Cache Simulator

Post 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.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post 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

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:

Post 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.
For help with problems, visit http://www.uvatoolkit.com/

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by baodog »

Nevemind. Got accepted.

Post Reply

Return to “Volume 114 (11400-11499)”