## 11235 - Frequent values

Moderator: Board moderators

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
mf wrote:This one maybe is a bit tricky.

Code: Select all

7 1
1 2 2 2 2 2 3
3 5
0
Output: 3

If it didn't help, you could write a simple brute force solution and cross-check its output with your solution on random cases.
well , I dont understand , why this input is valid, coz in the roblem statement they wrote ,
The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the query.
here the value of j is greater than an which is 3.
Syed Ishtiaque Ahmed Kallol
CSE,BUET

Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
cmd wrote:
Hadi wrote: The solution I used during the contest: O(n log n) preprocessing -> O(1) query answering.
This may give some ideas: http://www.topcoder.com/tc?module=Stati ... onAncestor

See the topic "Sparse Table (SP) Algorithm"

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
sorry.
i got my mistake , j should be less than n , not an
Syed Ishtiaque Ahmed Kallol
CSE,BUET

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
I am getting bored of TLEs. I have taken input in O(n*logn) and processesd each query on O(logn). This should not exceed the time limit. Is there any tricky one to hault my program or is it just too slow??

can anyone check my code, plz ??

Code: Select all

#include<stdio.h>
#include<string.h>

#define INF 100005

class node
{
public:

int count;
int left;
int right;
int next;
};

node a[200005];
int start;
int current;
int end;
void insert(int v,int c)
{

a[v].count=c;
a[current].next=v;
current=v;
if(v!=start)
{
register int i=start;
int prev;
while(i>=0)
{
prev=i;
if(a[i].count<c)
{
i=a[i].right;
if(i<0)
{
a[prev].right=v;
}
}
else
{
i=a[i].left;
if(i<0)
{
a[prev].left=v;
}
}
}

}

return;
}

int counter(int from, int to)
{

register int i=from;
if(a[i].count==0)
{
i=a[i].next;
}
if(i>to || i>end)
{
return 0;
}
int max=a[i].count;
int prev;
while(i<=to && i>=0 && i<=end)
{
prev=i;
int x=a[i].right;
if(x>=0)
{
i=a[i].right;
}
else
{
break;
}
}
return a[prev].count;
}

int main(void)
{
register int n,q,i,j,count,val,v2,from,to;
while(1)
{
scanf("%d",&n);
if(n==0)
{
break;
}
for(i=0;i<200005;i++)
{
a[i].left=a[i].right=-1;
a[i].count=0;
}
scanf("%d",&q);
i=0;
val=-INF;

while(i<n)
{
if(val==-INF)
{
scanf("%d",&val);
start=val+100000;
current=start;
i++;
}
else
{
val=v2;
}

if(i>=n)
{
break;
}

count=1;
while(i<n)
{
scanf("%d",&v2);
i++;
if(v2==val)
{
count++;
}
else
{
insert(val+100000,count);
break;
}

}
if(i>=n && v2==val)
{
insert(val+100000,count);
}
else if(i>=n && v2!=val)
{
insert(v2+100000,1);
val=v2;
}
}

i=start;
end=val+100000;
int vp;
while(i<val+100000)
{
if(a[i].count>0)
{
vp=a[i].next;
}
i++;
while(a[i].count==0 && i<val+100000)
{
a[i].next=vp;
i++;
}
}
for(j=0;j<q;j++)
{
scanf("%d%d",&from,&to);
int t =counter(from+100000,to+100000);
printf("%d\n",t);
}

}

return 0;
}
Syed Ishtiaque Ahmed Kallol
CSE,BUET

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
i am interseted in the solution about RMQ, but need more hints about the transformation process to RMQ problem.
thanks.
Sleep enough after death, it is the time to work.

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
any one help me checking some input for my code pasted above ??
Syed Ishtiaque Ahmed Kallol
CSE,BUET

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Hmm. I'm not going to plough through your code. Create an input file, based on the 10 values of the sample input and containing all possible queries (55). They are easily checked by hand, and you'll discover that you have many wrong answers, including zeros, which indicate boundary errors.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
sorry .. but I think,the possible input can be 78. -1 to 10 , there are 12 numbers.

what I found from my code seemed to be correct with my calculation.

for input

10 78

-1 -1 1 1 1 1 3 10 10 10

I found the result (with query)

Code: Select all

from: -1 to: -1 ans is:  2
from: -1 to: 0 ans is:  2
from: -1 to: 1 ans is:  4
from: -1 to: 2 ans is:  4
from: -1 to: 3 ans is:  4
from: -1 to: 4 ans is:  4
from: -1 to: 5 ans is:  4
from: -1 to: 6 ans is:  4
from: -1 to: 7 ans is:  4
from: -1 to: 8 ans is:  4
from: -1 to: 9 ans is:  4
from: -1 to: 10 ans is:  4
from: 0 to: 0 ans is:  0
from: 0 to: 1 ans is:  4
from: 0 to: 2 ans is:  4
from: 0 to: 3 ans is:  4
from: 0 to: 4 ans is:  4
from: 0 to: 5 ans is:  4
from: 0 to: 6 ans is:  4
from: 0 to: 7 ans is:  4
from: 0 to: 8 ans is:  4
from: 0 to: 9 ans is:  4
from: 0 to: 10 ans is:  4
from: 1 to: 1 ans is:  4
from: 1 to: 2 ans is:  4
from: 1 to: 3 ans is:  4
from: 1 to: 4 ans is:  4
from: 1 to: 5 ans is:  4
from: 1 to: 6 ans is:  4
from: 1 to: 7 ans is:  4
from: 1 to: 8 ans is:  4
from: 1 to: 9 ans is:  4
from: 1 to: 10 ans is:  4
from: 2 to: 2 ans is:  0
from: 2 to: 3 ans is:  1
from: 2 to: 4 ans is:  1
from: 2 to: 5 ans is:  1
from: 2 to: 6 ans is:  1
from: 2 to: 7 ans is:  1
from: 2 to: 8 ans is:  1
from: 2 to: 9 ans is:  1
from: 2 to: 10 ans is:  1
from: 3 to: 3 ans is:  1
from: 3 to: 4 ans is:  1
from: 3 to: 5 ans is:  1
from: 3 to: 6 ans is:  1
from: 3 to: 7 ans is:  1
from: 3 to: 8 ans is:  1
from: 3 to: 9 ans is:  1
from: 3 to: 10 ans is:  1
from: 4 to: 4 ans is:  0
from: 4 to: 5 ans is:  0
from: 4 to: 6 ans is:  0
from: 4 to: 7 ans is:  0
from: 4 to: 8 ans is:  0
from: 4 to: 9 ans is:  0
from: 4 to: 10 ans is:  3
from: 5 to: 5 ans is:  0
from: 5 to: 6 ans is:  0
from: 5 to: 7 ans is:  0
from: 5 to: 8 ans is:  0
from: 5 to: 9 ans is:  0
from: 5 to: 10 ans is:  3
from: 6 to: 6 ans is:  0
from: 6 to: 7 ans is:  0
from: 6 to: 8 ans is:  0
from: 6 to: 9 ans is:  0
from: 6 to: 10 ans is:  3
from: 7 to: 7 ans is:  0
from: 7 to: 8 ans is:  0
from: 7 to: 9 ans is:  0
from: 7 to: 10 ans is:  3
from: 8 to: 8 ans is:  0
from: 8 to: 9 ans is:  0
from: 8 to: 10 ans is:  3
from: 9 to: 9 ans is:  0
from: 9 to: 10 ans is:  3
from: 10 to: 10 ans is:  3
Please help me if I thinking in wrong way. Another thing is that , I did not get WA , I got TLE
Syed Ishtiaque Ahmed Kallol
CSE,BUET

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
You misunderstood the problem. Carefully read the description again. I'm sorry, but I have to catch a train, so I have no time to explain, but I'm sure you'll understand it.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Here is a little program that will produce the input/output I wrote about:

Code: Select all

#include <stdio.h>

#define FILENAME "fulltest"

const int value[]={-1,-1,1,1,1,1,3,10,10,10};
const int values=sizeof(value)/sizeof(int);

int main(){
FILE *infile,*outfile;
int from,to,i;
int freq,maxfreq;

infile=fopen(FILENAME ".in","w");
outfile=fopen(FILENAME ".out","w");

fprintf(infile,"%d %d\n",values,(values*(values+1))/2);
for(i=0;i<values;i++) fprintf(infile,"%d%c",value[i],(i==values-1)?'\n':' ');
for(from=0;from<values;from++){
for(to=from;to<values;to++){
fprintf(infile,"%d %d\n",from+1,to+1);
maxfreq=0;
for(freq=1,i=from+1;i<=to+1;i++){
if((i<=to)&&(value[i]==value[i-1])) freq++;
else{ if(freq>maxfreq) maxfreq=freq; freq=1;}
}
fprintf(outfile,"%d\n",maxfreq);
}
}

fclose(outfile);
fclose(infile);
return 0;
}
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

New poster
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
to kollol->
you totally misunderstood the problem.

in the probelm description says
"The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the query."
that is the boundary of position.

suppose for test case

Code: Select all

10 1
-1 -1 1 1 1 1 3 10 10 10
pos:       1  2 3 4 5 6 7 8  9 10
and by the query 2 5 means

from position 2 to 5 output The number of occurrences of the most frequent value.

here output is 3.
because from position 2 to 5
-1 occurs 1 time
and 1 occurs 3 times.

and for tle if you just use a cleaver bruteforce u can get rid of tle.

hope it helps.
sorry for my poor english

-----------------------------------------------------------------
LIFE IS COMBINED WITH JOY AND SORROW.IT IS NOT ONLY FOR SITTING IN A ROOM AND TYPING CODE.
Last edited by SHAHADAT on Tue Jul 31, 2007 3:58 pm, edited 1 time in total.

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
Thank you very much.

I really misunderstood the problem , Now I have got it. Hope , I will get it solved soon . Thanks once again !
Syed Ishtiaque Ahmed Kallol
CSE,BUET

shankarrg
New poster
Posts: 2
Joined: Sat Jun 23, 2007 4:14 am

### FREQUENCY

how 2 reduce this problem 2 RMQ ?

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

### Re: FREQUENCY

shankarrg wrote:how 2 reduce this problem 2 RMQ ?
The sequence is in non-decreasing order.

Suppose, u want to know the maximum frequency in the range (a,b).
Now, k is an index between a and b. So the answer for this range is,

range(a,b)=
max( range(a,k) ,range(k+1,b) , frequency_of_number_at_position_k )

this is for the Sparse Table method.

shankarrg
New poster
Posts: 2
Joined: Sat Jun 23, 2007 4:14 am

got it..

thanks