Cache Hits Codechef Solution: Chef has a memory machine. It has one layer for data storage and another layer for cache. Chef has stored an array with length NN in the first layer; let’s denote its elements by A0,A1,…,AN−1A0,A1,…,AN−1. Now he wants to load some elements of this array into the cache.
The machine loads the array in blocks with size BB: A0,A1,…,AB−1A0,A1,…,AB−1 form a block, AB,AB+1,…,A2B−1AB,AB+1,…,A2B−1 form another block, and so on. The last block may contain less than BB elements of Chef’s array. The cache may only contain at most one block at a time. Whenever Chef tries to access an element AiAi, the machine checks if the block where AiAi is located is already in the cache, and if it is not, loads this block into the cache layer, so that it can quickly access any data in it. However, as soon as Chef tries to access any element that is outside the block currently loaded in the cache, the block that was previously loaded into the cache is removed from the cache, since the machine loads a new block containing the element that is being accessed.
Chef has a sequence of elements Ax1,Ax2,…,AxMAx1,Ax2,…,AxM which he wants to access, in this order. Initially, the cache is empty. Chef is wondering how many times the machine will need to load a block into the cache layer. Can you help him calculate this number?
Input
- The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- The first line of each test case contains three space-separated integers NN, BB and MM.
- The second line contains MM space-separated integers x1,x2,…,xMx1,x2,…,xM.
Output
For each test case, print a single line containing one integer ― the number of times the machine loads a block into the cache.
Constraints
- 1≤T≤1001≤T≤100
- 1≤N,B,M≤5,0001≤N,B,M≤5,000
- 0≤xi<N0≤xi<N for each valid ii
Sample Input 1
1 5 3 3 0 3 4
Sample Output 1
2
Explanation
Example case 1: The machine stores elements [A0,A1,A2][A0,A1,A2] in one block and [A3,A4][A3,A4] in another block. When accessing A0A0, the block [A0,A1,A2][A0,A1,A2] is loaded. Then, accessing A3A3 removes the previous block from the cache and loads the block [A3,A4][A3,A4]. Finally, when Chef accesses A4A4, a new block is not loaded, since the block containing A4A4 is currently loaded in the cache.
Cache Hits – CodeChef Solution in JAVA
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in) ;
try{
int t = sc.nextInt() ;
while(t-- > 0){
int n = sc.nextInt() ;
int b = sc.nextInt() ;
int m = sc.nextInt() ;
int[] arr = new int[m] ;
for(int i = 0 ; i < m ; i++){
arr[i] = sc.nextInt() ;
}
int count = 1 ;
int block = arr[0] / b ;
for(int i = 1 ; i < m ; i++){
if(arr[i] / b != block){
count++ ;
block = arr[i] / b ;
}
}
System.out.println(count);
}
}
catch(Exception e){
return ;
}
}
}
Cache Hits – CodeChef Solution in CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)
{
int n,b,m;
cin>>n>>b>>m;
int prev_block=-1,ans=0;
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
x=x+1;
int curr_block=(x+b-1)/b;
if(curr_block!=prev_block)
{
ans++;
prev_block=curr_block;
}
}
cout<<ans<<endl;
}
return 0;
}Cache Hits – CodeChef Solution in Python
t = int(input())
for i in range(t):
n, b, m = map(int, input().split())
l = list(map(int, input().split()))
s = l[0] // b
c = 1
for j in range(1, m):
z = l[j] // b
if s != z:
c += 1
s = z
print(c)Disclaimer: The above Problem ( Cache Hits ) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.
