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.