# Internet Problem Solving Contest

## Solution to Problem L – Librarian

This is a classical problem from memory management, known as the Belady's anomaly. The book numbers correspond to virtual memory pages, the bookcase is the physical memory, and fetching a book from the storage is called a page fault.

The best way how to find the sequences is simply by experimenting, maybe with a help of a small program that simulates the librarian's bookcase and always removes the right book – it's easy to make a mistake when simulating the process by hand.

The Wikipedia link gives an example for N=3:

```1 2 3 4 1 2 5 1 2 3 4 5
```

Through understanding this example, a bit more precise googling or just wild guessing from the looks of it, we can derive a more general pattern for the anomaly:

S1 := 1, 2, ..., N+1,  1, 2,  N+2,  1, 2, ..., N+1, N+2

This sequence creates one more page fault when the number of pages increases from N to N+1. Thus for the easy task, all we need is to write an instance of it for some N>3, for example:

```4 14
1 2 3 4 5   1 2   6   1 2 3 4 5 6
```

For the hard task, we first need to understand how the extra page fault is generated, and then we can construct a sequence for the increase from N pages to N+2. After that, a sequence for N+3 will be easy. By combining all three sequences (for N+1, N+2 and N+3) we can get the final solution.

Consider the example sequence 1 2 3 4 1 2 5 1 2 3 4. Let us write down the steps along with the contents of the FIFO-like memory (the bookshelf):

 Request N+1 N+2 1 1 PF 1 PF 2 1 2 PF 1 2 PF 3 1 2 3 PF 1 2 3 PF 4 2 3 4 PF 1 2 3 4 PF 1 3 4 1 PF 1 2 3 4 2 4 1 2 PF 1 2 3 4 5 1 2 5 PF 2 3 4 5 PF 1 1 2 5 3 4 5 1 PF 2 1 2 5 4 5 1 2 PF 3 2 5 3 PF 5 1 2 3 PF 4 5 3 4 PF 1 2 3 4 PF 5 5 3 4 2 3 4 5 PF

The reason for the extra page fault is that after the "execution" of the middle part 1 2 5, the pages 1 and 2 are left at the end of the fifo and immediately pushed out byt the page 5. In the final part, they are thus re-added at the begginning of the FIFO and thus they push the page 5 out thus causing page fault at the end.

So what with the N+2 case? First we enlarge the first part, because we now need to fill N+2 pages in the larger FIFO and also we need 3 pages from the beginning in the middle part. Because of this the sequence will only work for N≥4. Thus we get the sequence:

S2 := 1, 2, ..., N+2,   1, 2, 3,  N+3,   1, 2, ..., N+2, N+3

Analogicaly, for N+3, we get (for N≥5):

S3 := 1, 2, ..., N+3,   1, 2, 3, 4,  N+4,   1, 2, ..., N+3, N+4

To put them together, we would choose N=5. For this size we have T(N,S1)=13, T(N+1,S1)=14 and T(N+2,S1)=T(N+3,S1)=7. Thus including S1 in the final sequence would generate a defficiency of 6 page faults in the case of N+2 and N+3. To counter this we would need to repeat S2 at least 7 times. Because T(N,S2)=T(N+1,S2)=15, T(N+3,S2)=8, this would againg create an another defficiency of 7*7 page faults in the case of N+3. Thus S3 would have to be repeated 7+7*7 times. This is however far above the limit of 300.

To fit into the maximum length, we need to make up a better sequences such that they have either more page faults, or that they work simultaneously for two or all three cases. One of such sequences is (for N=8):

S23 := 1 2 3 4 5 6 7 8 9 10   1 2 3 4   20 21   1 2 3 4 5 6 7 8 9 10 20 21

T(N,S23)=T(N+1,S2)=22, T(N+2,S2)=T(N+3,S2)=24. Thus we can use S1 and then 5 times S23. As a final note, we need a sort of "padding" between the sequences, to "flush out" the content of the FIFO so the next sequence does not have anything "cached" and generates all of the page faults.

A sample output for the hard task can thus look like this (pages 31,..,33 are used as padding):

```8
169
1 2 3 4 5 6 7 8 9   1 2  20   1 2 3 4 5 6 7 8 9 20   31 32 33
1 2 3 4 5 6 7 8 9 10   1 2 3 4  20 21   1 2 3 4 5 6 7 8 9 10 20 21   31
1 2 3 4 5 6 7 8 9 10   1 2 3 4  20 21   1 2 3 4 5 6 7 8 9 10 20 21   31
1 2 3 4 5 6 7 8 9 10   1 2 3 4  20 21   1 2 3 4 5 6 7 8 9 10 20 21   31
1 2 3 4 5 6 7 8 9 10   1 2 3 4  20 21   1 2 3 4 5 6 7 8 9 10 20 21   31
1 2 3 4 5 6 7 8 9 10   1 2 3 4  20 21   1 2 3 4 5 6 7 8 9 10 20 21
```