polish OI problem help

kpo · Post by **kpo** » Thu Jul 14, 2005 6:23 pm

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

Thanks.

Monsoon · Post by **Monsoon** » Thu Jul 14, 2005 7:20 pm

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

kpo · Post by **kpo** » Thu Jul 14, 2005 9:34 pm

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

misof · Post by **misof** » Thu Jul 14, 2005 10:44 pm

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

kpo · Post by **kpo** » Fri Jul 15, 2005 2:32 pm

thank you!