11235 - Frequent values

[Kallol]

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.

[Hadi]

The solution I used during the contest: O(n log n) preprocessing -> O(1) query answering.

Can you tell about your solution?

This may give some ideas: http://www.topcoder.com/tc?module=Stati ... onAncestor

See the topic "Sparse Table (SP) Algorithm"

[Kallol]

sorry.
i got my mistake , j should be less than n , not an

[Kallol]

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;
}

[898989]

i am interseted in the solution about RMQ, but need more hints about the transformation process to RMQ problem.
thanks.

[Kallol]

any one help me checking some input for my code pasted above ??

[little joey]

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.

[Kallol]

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

[little joey]

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.

[little joey]

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;
   }

[SHAHADAT]

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.

[Kallol]

Thank you very much.

I really misunderstood the problem , Now I have got it. Hope , I will get it solved soon . Thanks once again !

[shankarrg]

how 2 reduce this problem 2 RMQ ?

[sunny]

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]

got it..

thanks