CACHEHIT - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Rezwan Arefin
Tester: Raja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic Math

PROBLEM:

Chef has a memory machine divided into N units numbered from 0 to N-1. Each B memory units are grouped together, that is, that is A_0,\ldots, A_{B-1} is stored in a block, A_B,\ldots, A_{2B-1} in another block and so on. The last block may contain less than B array elements.

Whenever the chef accesses an element, the whole block gets loaded into cache, if not already loaded.

Chef access memory M times, accessing memory unit i_j in j-th access. Find the number of times the cache is reloaded.

QUICK EXPLANATION

  • For first access, the block containing the first accessed element shall always be loaded.
  • After that, only when the block of the previously accessed element is different from the block of the current element, we load the new block into the cache.

EXPLANATION

First of all, how to find the block of a memory position x?

Here's how

\displaystyle\bigg\lfloor \frac{x}{B} \bigg\rfloor gives us the block number of memory position x

Now, the first access element’s block shall be loaded.

After that, we keep track of the current loaded block. If the next element also lies in the same block, then we don’t need to reload. Otherwise, we have to reload. We also update the current block.

pseudocode

current := -1 //Denoting empty cache
count = 0
for x in access:
      if x/B != current:
            cur := x/B
            count++

Bonus:
You have a cache that can store at most K values. Every time you access some element, if it is not present in the cache, the least recently used element is removed from the cache if the cache is full and the accessed element is added.

Find the contents of the cache after M access operations.

TIME COMPLEXITY

The time complexity is O(M) per test case.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int N = 1e5 + 5; 
int n, t, b, m; 

int main() {
  scanf("%d", &t); 
  while(t--) {
	scanf("%d %d %d", &n, &b, &m);
	int prev = 1e9, i, ans = 0; 
	while(m--) {
	  scanf("%d", &i); 
	  ans += (i / b) != (prev / b); 
	  prev = i; 
	}
	printf("%d\n", ans); 
  }
  return 0;
}
Tester's Solution
//raja1999

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;


//std::ios::sync_with_stdio(false);

main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,m,b,pos,prev,ans=0,i;
		cin>>n>>b>>m;
		prev=-1;
		for(i=0;i<m;i++){
			cin>>pos;
			if(pos/b != prev){
				ans++;
			}
			prev=pos/b;
		}
		cout<<ans<<endl;
	}
	return 0;
} 
Editorialist's Solution
import java.util.*;
import java.io.*;
class CACHEHIT{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int N = ni(), B = ni(), M = ni();
	    int prev = -1, ans = 0;
	    //prev is the block currently loaded into memory
	    for(int i = 0; i< M; i++){
	        int bl = ni()/B;//block of current element
	        if(prev != bl)ans++;
	        prev = bl;
	    }
	    pn(ans);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new CACHEHIT().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

3 Likes

Another way to solve this problem . use range for storing block.
https://www.codechef.com/viewsolution/34584989

Can someone point out error in my code…? i am doing xactly the same i guess…

cook your dish here

for i in range(int(input())):
N, B, M = map(int, input().split())
# input()
if M == 1:
input()
print(1)

else:
    ms = list(map(int,input().split()))

    if B == 1:
        print(len(set(ms)))

    else:
        cache = None

        inc = 0
        blocks = 0

        while inc < len(ms):
            if cache is None:
                blocks += 1
                cache = ms[inc] //B
                inc += 1

            else:
                if ms[inc] // B == cache:
                    inc += 1

                else:
                    cache = ms[inc] // B
                    blocks += 1
                    inc += 1



        print(blocks)

Can anybody plz tell me what’s wrong in this code…My idea was to count if element is not present in the previous block. My code is https://ideone.com/e.js/wviLNH

Hi guys try this video solution :raised_hands::raised_hands:

i have tried to explain in most clear way with concrete proof

3 Likes

can anyone tell me why TLE for this range based approach???

https://www.codechef.com/viewsolution/34624457

can anyone please point out the error as i was doing the same thing

/* 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
{
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;

    public Reader() {
        din = new DataInputStream(System.in);
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public Reader(String file_name) throws IOException {
        din = new DataInputStream(new FileInputStream(file_name));
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public String readLine() throws IOException {
        byte[] buf = new byte[100000]; // line length
        int cnt = 0, c;
        while ((c = read()) != -1) {
            if (c == '\n')
                break;
            buf[cnt++] = (byte) c;
        }
        return new String(buf, 0, cnt);
    }

    public int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');

        if (neg)
            return -ret;
        return ret;
    }

    public long nextLong() throws IOException {
        long ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        }
        while ((c = read()) >= '0' && c <= '9');
        if (neg)
            return -ret;
        return ret;
    }

    public double nextDouble() throws IOException {
        double ret = 0, div = 1;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();

        do {
            ret = ret * 10 + c - '0';
        }
        while ((c = read()) >= '0' && c <= '9');

        if (c == '.') {
            while ((c = read()) >= '0' && c <= '9') {
                ret += (c - '0') / (div *= 10);
            }
        }

        if (neg)
            return -ret;
        return ret;
    }

    private void fillBuffer() throws IOException {
        bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
        if (bytesRead == -1)
            buffer[0] = -1;
    }

    private byte read() throws IOException {
        if (bufferPointer == bytesRead)
            fillBuffer();
        return buffer[bufferPointer++];
    }

    public void close() throws IOException {
        if (din == null)
            return;
        din.close();
    }
}

public static void main(String[] args) throws IOException, java.lang.Exception{
    Reader in = new Reader();
    int t = in.nextInt();
    StringBuilder res = new StringBuilder();

    while (t-->0){
        int n = in.nextInt();
        int b = in.nextInt();
        int m = in.nextInt();
        int[] a = new int[m];
        for (int i=0;i<m;i++)
            a[i] = in.nextInt();
        int count = 0;
        if(b>1) {
            int index = -1;
            for (int i = 0; i < m; i++) {
                if (a[i] / b != index)
                    count++;
                index = a[i] / b;
            }
        }
        else count = m;
        res.append(count).append("\n");
    }
    System.out.println(res);
}

}

what does range function do in vector plz explain??

Nice explaination bro

1 Like

1.can anyone help me, what is wrong with my approach?

#include

using namespace std;

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t–){
long long int n,b,m,count;
cin>>n>>b>>m;
int a[m];
count=1;
for(int i=0;i<m;i++){cin>>a[i];
}
for(int i=0;i<m-1;i++){
if(a[i]<b && a[i+1]>=b )count++;
else if( a[i]>=b && a[i+1]<b)count++;
}
cout<<count<<endl;
}
}

ok

:ok_hand:t3: :+1:t3:

@anshtyagi, try running the code without this part:

    if B == 1:
        print(len(set(ms)))

The rest of the code should work even if the value of B is 1.

Hope this will explain what the error in your code was:
You have made it such that if numbers are repeated, only one of them is counted. This won’t work unless all the numbers repeated are consecutive. For example, if ms = [1,1,5], the output will be 2. But if ms = [1,5,1] will be 3, bout your program will print the output as 2.
Similarly, your previous output won’t work if the numbers repeated are consecutive.

Can anyone help me configure where I went wrong in logic.
https://www.codechef.com/viewsolution/34609169
Explanation :-

  1. I created a window till K-1.
  2. If the number lies in the current window, do nothing.
  3. If number is outside current window, state new window “start” and “end” and update ans.

Video Explanation