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

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.

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

Post by rio » Wed Mar 19, 2008 12:36 am

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

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 » Thu Mar 20, 2008 12:28 am

Nevemind. Got accepted.

Post Reply

Return to “Volume 114 (11400-11499)”