### watchdogs132's blog

By watchdogs132, history, 2 months ago, ,

Link to problem: https://www.spoj.com/problems/FREQUENT/

I know this is quite a famous problem and I have searched extensively about it , but my attempts at debugging my code have failed.

I use the approach of Segment Trees to solve this problem after having built a frequency array. Run time : $O(n)$ pre-processing per test case and $O(log (n))$ to answer each query.

#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;

const int N=200000;

int a[N],t[4*N],b[N]; //b is the frequency array

void build(int v,int tl,int tr){
if(tl==tr){
t[v]=b[tl];
}
else{
int tm=(tl+tr)/2;
build(2*v,tl,tm);
build(2*v+1,tm+1,tr);
t[v]=max(t[2*v],t[2*v+1]);
}
}

int query(int v,int tl,int tr,int l,int r){
if(l>r)
return -1e9;
if(l<=tl&&tr<=r)
return t[v];
int tm=(tl+tr)/2;
return max(query(v*2, tl, tm, l, min(r, tm)),
query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
int main()
{
int n,q;
while(true){
scanf("%d", &n);
if(!n)break;
scanf("%d", &q);
unordered_map<int,int>cnt;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
++cnt[a[i]];
}
for(int i=0;i<n;i++){
b[i]=cnt[a[i]];
}
build(1,0,n-1);
while(q--){
int l,r;
scanf("%d %d",&l,&r);
--l,--r;
if(a[r]==a[l]){  //This is when all numbers in the range are the same.
printf("%d\n",r-l+1);
}
else{
/*This is to handle the case as follows :111 22233 4444
idx1 and idx2-1 will cover the range 22233 and
then we do the max of all three blocks [111] [22233] [4444] which
in this case is basically max(3,3,4)=4 */
int idx1=upper_bound(a+l,a+l+r,a[l])-a;
int idx2=lower_bound(a+l,a+l+r,a[r])-a;
int ans=max(max(idx1-l,r+1-idx2),query(1,0,n-1,idx1,idx2-1));
printf("%d\n",ans);
}
}
}
return 0;
}


• -2

 » 2 months ago, # |   +7 It is not too hard to write a brute force algorithm and a random test case generator for this problem. Once you have done this, I think that it wouldn't be too difficult to find a small counterexample to your solution which you can use for debugging.
•  » » 2 months ago, # ^ |   0 Well I tried a bunch of test cases from here :https://web.archive.org/web/20180117155353/http://spojtoolkit.com/history/FREQUENT . As it turns out , my code gives the right output in each of those test cases . Do you have a counter example ?.
•  » » » 2 months ago, # ^ |   0 Try generating your own test cases.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 You know what? I simply copied the sample and randomly changed it a little and your algo already gives wrong answer (see the second query). testcase10 3 -1 -1 1 2 1 1 3 10 10 10 1 2 2 4 5 7 0 Lesson of the day: Eyeballing your code does not help you to debug it in most instances. You gotta move your hands, activate your brain and spend some effort in creating testcases.
•  » » » » 2 months ago, # ^ |   0 It says in the problem that the input array is non decreasing . In you test case ,if you present it in non decreasing form [-1 -1 1 1 1 2 3 10 10 10] ,then my code returns 2 2 1 which is correct .
•  » » » » » 2 months ago, # ^ | ← Rev. 6 →   0 It wasn't too hard to generate another test case to fail your code... testcase15 10 1 1 1 1 2 2 2 3 3 4 4 4 5 5 5 11 12 11 15 2 2 3 7 1 7 7 9 1 13 11 15 12 12 5 15 0 
•  » » » » » » 2 months ago, # ^ |   0 Yea , I see the error in my code . Basically this (a+l+r) needed to be a+min(l+r,n). Cheers!
 » 2 months ago, # |   0 Auto comment: topic has been updated by watchdogs132 (previous revision, new revision, compare).