OJ Board

Can anyone help me with this problem:
http://www.oi.edu.pl/php/show.php?ac=e1 ... a/oi12/sam

Thanks.

I don't remember fully my solution, but you should use heap to solve this task. If you want more hints just ask.

thanks, but can you please give some more hints about the algorithm?

The problem in this task is known under the name "offline paging".

(Paging: you've got a large virtual memory stored on the swap, a smaller physical memory you use and you move pages of data to memory whenever you need them. Paging algorithms = strategies to select a page that has to be swapped off when memory is full. Offline = you know all future requests.)

In this situation Belady's algorithm is optimal.

Idea: When you have to remove a car from the carpet (=a page from the physical memory), remove the one that will be requested furthest in the future.

To be able to do this quicky, keep the cars that currently are on the carpet stored in a heap ordered according to the time when will the kid play with them the next time.

More on paging algorithms e.g. here: http://dimacs.rutgers.edu/~mpal/papers/dipl.ps

thank you!