Preparing NOJ

LRU

3000ms 262144K

Description:

It costs a long time for CPUs to access data from memory, so most of CPUs have caches where requests for data can be served faster. To be cost-effective and to enable efficient use of data, caches must be relatively small. Therefore, we must use some policies to choose some data wisely and storage them in the cache. We divide the memory into many blocks which have the same size and index them from 1 to $$$10^9$$$, and every block has an unique index. A cache will have a capacity for $$$K$$$ blocks, which means it can storage at most $$$K$$$ blocks simultaneously. A cache hit occurs when the requested block is available in the cache, or we say a cache miss occurs. Now we introduce a LRU (Least Recently Used) placement policy on a fully associative cache.

  1. If the requested block is available in the cache, a cache hit occurs.
  2. If not, CPU can only access the block from the memory and write the block into the cache. If cache is not full, append the block into the cache.
  3. If the cache is full, cache is full, the block which haven't been visited for the longest time in the cache will be replaced by the new block.

An example for cache with capacity of $$$3$$$ blocks is shown below.

The $$$8^{th}$$$, $$$4^{th}$$$ and $$$3^{rd}$$$ are in the cache when the $$$6^{th}$$$ block is requested, so a cache miss occurs. At that time, the cache is full, and we must decide the block to be replaced. The most recent request of $$$8^{th}$$$ block is the $$$13^{th}$$$ request, the most recent request of $$$4^{th}$$$ block is the $$$14^{th}$$$ request and the most recent request of $$$3^{rd}$$$ block is the $$$11^{th}$$$ request. The $$$3^{rd}$$$ block will be replaced by the $$$6^{th}$$$ block because the $$$3^{rd}$$$ block hasn't been visited for longest time.

Now the sequence of requested blocks and the capacity of the cache are given, please determine the minimum capacity for the cache in order to ensure at least K requests to hit the cache.

Input:

The first line contains two integers $$$N$$$ and $$$K(1\le K\le N\le 10^5)$$$, denoting the length of sequence and the number of requests required to hit the cache. The second line contains $$$N$$$ integers and the $$$i^{th}$$$ integers $$$a_i(1\le a_i\le 10^9)$$$ denoting the index of the block requested by the $$$i^{th}$$$ request.

Output:

The output contains only one line. If it is possible to ensure at least $$$K$$$ requests to hit the cache, then output a single integer denoting the smallest capacity in blocks, otherwise output "cbddl"(without quotes).

Sample Input:

15 6
3 4 2 6 4 3 7 4 3 6 3 4 8 4 6

Sample Output:

3

Sample Input:

15 5
3 4 2 6 4 3 7 4 3 6 3 4 8 4 6

Sample Output:

3

Sample Input:

15 10
3 4 2 6 4 3 7 4 3 6 3 4 8 4 6

Sample Output:

cbddl

Info

CodeForces Gym

Provider CodeForces Gym

Origin 2021 Jiangxi Provincial Collegiate Programming Contest

Code GYM103366J

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/25/2021 22:32:04

Related

Nothing Yet