Cache Hits Problem Code: CACHEHIT (JUNE COOKOFF 2020)

Cache Hits Problem Code: CACHEHIT (JUNE COOKOFF 2020)

Quick explanation: Given an array of n integers and an integer b. We have to divide n integers into some blocks of size b. It means if we have n=5 and b=3 then array elements are {0,1,2,3,4} so we have to divide as {0,1,2} as one block and {3,4} as another block. So, this is what they mean by the machine loads array into blocks. Initially cache is empty. We have to load array elements into blocks. Next, they will give m integers . Going sequentially through m elements, we have to check if given element is in cache or not , if not we have to load that block, if it is in the block of cache then no need to load any block. When ever we are loading a block we have to remove the previous block which is present.

So lets have an example to understand more easily.

Let n=7, b=3 , m=6. And the m elements are 0,4,5,3,4,6.

So first create blocks

• 0,1,2  -- block1

• 3,4,5  -- block2

--------- 0,1,2

• 6         -- block3

First given number “0” .So, we have to load block 1 .So as we load the number of times machine loaded=1.

--------- 3,4,5

Next given number “4”. It is not there in cache .

So we have to remove block1 and load block2 .

The number of times machine loaded=2.

Next given “5”. “5” is there in cache so need to load.

Given “3” . “3” is there in cache so need to load.

    Given “4” which is there in cache so no need to load.

    Next given 6 which is not there in cache so we 

--------- 6

    Need to remove block2 and load block 3. Hence 

    Number of times machine loaded=3.      

   

So the blocks are 

0	1	2
3	4	5
6

  N=7  & b=3

So the approach is, as m>=1 it means we will be asked at least 1 query. If we check the range in which given element is there then we are done with our job. In our case given numbers to find are  0,4,5,3,4,6.

First number =0 🡪 Calculate range in which 0 lies ==Lower bound is 0 we can calculate by formula m-m%b   i.e., 0-0%3=0. Upper bound is 0+3-1 which is 2 and formula is lower bound+b-1.By observation we can find it easily.

So for the next query if the number is present between its previous query range then no need to load else we have to load.

So check the code for better understanding .Hope the above explanation is clear.

/* package codechef; // don't place package name! */

 

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

{

// your code goes here

Scanner s=new Scanner(System.in);

int t=s.nextInt();

while(t-->0)

{

    int n=s.nextInt();

    int b=s.nextInt();

    int m=s.nextInt();

  int c=0;

    int x1=-1,x2=-1;

    int m1;

    m1=s.nextInt();

    x1=m1-(m1%b);

    x2=x1+b-1;

    m=m-1;

    c++;

    int x11,x22;

    while(m-->0)

    {

      m1=s.nextInt();

      x11=m1-(m1%b);

      x22=x11+b-1;

      if(x1==x11 && x2==x22)

      {

          

      }

      else

      {

          c++;

          x1=x11;

          x2=x22;

      }

       

    }

    System.out.println(c);

}

}

}

                    

Feel free to ask doubts in comments section.