11235 - Frequent values

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Tue Jul 10, 2007 4:00 pm

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
Bangladesh

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Tue Jul 10, 2007 4:01 pm

cmd wrote:
Hadi wrote: 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"

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Tue Jul 10, 2007 4:02 pm

sorry.
i got my mistake , j should be less than n , not an :oops:
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Tue Jul 10, 2007 4:25 pm

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
Bangladesh

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Tue Jul 10, 2007 4:31 pm

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.
Mostafa Saad

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Wed Jul 11, 2007 3:21 pm

any one help me checking some input for my code pasted above ??
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Jul 12, 2007 10:31 am

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.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Thu Jul 12, 2007 6:17 pm

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
Bangladesh

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Jul 12, 2007 7:02 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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Jul 14, 2007 8:21 am

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.

SHAHADAT
New poster
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
Location: sust,bangladesh

Post by SHAHADAT » Sun Jul 15, 2007 11:14 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.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sun Jul 15, 2007 5:42 pm

Thank you very much. :oops:

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
Bangladesh

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

FREQUENCY

Post by shankarrg » Sun Aug 05, 2007 7:10 pm

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

Post by sunny » Sun Aug 05, 2007 9:08 pm

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

FREQUENT

Post by shankarrg » Mon Aug 06, 2007 11:00 am

got it.. :D

thanks

Post Reply

Return to “Volume 112 (11200-11299)”