CS
Problems Base course RU

Problem

Replay ARC

caching hash table linked list simulation in production

A cache of c pages works by the ARC rule. It keeps four lists, in each of which pages are ordered from oldest to freshest: the cache holds the pages of the lists T1 (asked for once since they got into the cache) and T2 (at least twice), while the lists B1 and B2 are “ghosts”: the numbers of pages recently evicted from T1 and T2 respectively, without the pages themselves. The integer p is how many places the cache would like to give to T1; at first all lists are empty and p = 0.

The helper action EVICT(x): if T1 is not empty and (|T1| > p or (x is in B2 and |T1| = p)), the oldest page of T1 moves to the end of B1; otherwise the oldest page of T2 moves to the end of B2.

A request for page x:

  1. x is in T1 or T2: a hit; x moves to the end of T2.
  2. x is in B1: p ← min(c, p + max(⌊|B2| / |B1|⌋, 1)); EVICT(x); x is removed from B1 and put at the end of T2.
  3. x is in B2: p ← max(0, p − max(⌊|B1| / |B2|⌋, 1)); EVICT(x); x is removed from B2 and put at the end of T2.
  4. x is nowhere. If |T1| + |B1| = c: when |T1| < c, the oldest number of B1 is removed and EVICT(x) is done, otherwise the oldest page of T1 is simply removed. If instead |T1| + |B1| < c and |T1| + |T2| + |B1| + |B2| ≥ c: when the sum equals 2c, the oldest number of B2 is removed, and in either case EVICT(x) is done. After this x is put at the end of T1.

The sizes in the formulas are those before the changes at this step. Replay the cache’s work on a sequence of requests. Two tests are real requests to the Kennedy Space Center web server in July 1995.

Input

The first line holds c and the number of requests n (1 ≤ c ≤ 104, 1 ≤ n ≤ 5·105). The second holds n page numbers, integers from 0 to 106.

Output

Six numbers: the number of hits, the final p and the sizes of T1, T2, B1, B2 after the last request.

In the second example the second-to-last request is page 5, which lies in B2 when |T1| = p = 1. By the special EVICT rule T1 frees the place: page 4 goes to B1, and the last request, page 1, lands in T2.

Examples

Example 1

Input
2 9
1 2 3 1 2 3 1 4 1
Output
1 0 1 1 0 0

Example 2

Input
3 9
5 3 5 1 4 3 1 5 1
Output
2 1 0 3 1 0

Limits

Time · Python
8000 ms
Time · Go
1500 ms
Memory
256 MB
Judging
8 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Every step of the rules touches the lists only at the ends: take out the oldest, put at the end, remove a page from the middle by its number. Which structure does all this in O(1)?

2The idea

Each of the four lists is an ordered set: a doubly linked list plus a dictionary “page → its node”. In Python this is OrderedDict: popitem(last=False) takes out the oldest, move_to_end moves to the end, del removes by key. Then a request costs O(1), and all the work is carrying the rules over carefully.

3Walkthrough

The order of the checks matters: first T1 and T2 (a hit), then B1 and B2 (ghosts), then “nowhere”. On a ghost hit, p changes first, then EVICT is done, and in it the check “x is in B2” still sees x in B2, and only then is x removed from the ghost list and put at the end of T2. The divisions are integer, with a lower bound of 1: even with the opposite list empty, p moves by at least one.

What the ghosts do. If a request fell into B1, a page asked for once was evicted in vain, the cache should keep more fresh pages, and p grows. A hit in B2 means a frequent page was evicted in vain, and p decreases. The step is larger the smaller the list hit: a rare hit in a small list is a strong argument. Over the week of the NASA log in the article, a cache of a hundred pages keeps p at about seven: this stream likes frequency more, but with no places for newcomers at all, as in LFU, it loses.

3+Solution
4Complexity

O(1) per request, O(n) for all; memory O(c): the cache and the ghosts together hold at most 2c numbers.

5Common mistakes
  • The special case of EVICT. If the request came from B2 and |T1| is exactly p, T1 frees the place, not T2. Without this the answers diverge already in the second example.
  • The order of steps on a ghost hit. If x is removed from B2 first, the special case will not fire; if x is put into T2 first, EVICT may throw it out itself.
  • Division. Integer division with a maximum of one is needed; in floating point you get a different p and different answers.

Algorithms behind it

SYS Algorithm LFU and ARC Caches that remember frequency: LFU in O(1) on counter buckets and ARC, which divides its places between fresh and frequent by itself. O(1) per request for both 2 problems DS Data structure LRU cache A dictionary plus a doubly linked list: get and put in O(1), and out goes the one accessed longest ago. O(1) per get and put 2 problems
The algorithms catalogue