STONE05 - Editorial

PROBLEM LINK:

Practice
Div-2 Contest

Author: Vivek Kumar Mishra
Tester: Vivek Kumar Mishra
Editorialist: Prateek Chandra

DIFFICULTY:

HARD

PREREQUISITES:

Trees

PROBLEM:

Find the largest set of correlative numbers

EXPLANATION:

As we can see 1 \leq ans \leq n as the feasible range is clear we may use binary search to find out the answer.

SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>
using namespace std;

void findRem(vector &a,int n,int k,vector<vector> &r) {

for (int i = 0; i < n; i++) {
   int rem = a[i] % k;
   r[rem].push_back(a[i]);
}

}
bool isValid(vector &a,int n,int k,int m,vector<vector> &r){
for (int i = 0; i < k; i++) {
if(r[i].size() >= m) return true;
}
return false;
}

void solve(){
int n,k; cin>>n>>k;
vector a(n);
for(int i=0;i<n;i++) cin>>a[i];

vector<vector<int>> store_rem(k+1);
findRem(a,n,k,store_rem);   

int l=1,r=1e6,ans=1;
while(l<=r){
int m=(l+r)>>1;
if(isValid(a,n,k,m,store_rem)){
ans=m; l=m+1;
}else r=m-1;
}
cout<<ans<<“\n”;
}
int main() {
#ifndef ONLINE_JUDGE
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
#endif
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin>>t;
while(t–) solve();

}