Page 3 of 4

Posted: Wed Jun 15, 2005 3:04 pm
by Mohammad Mahmudur Rahman
In fact, I talked about exactly your method in the previous post. But the confusion was whether the program should be called O(1) or O(n). After all, you must read all the inputs which takes linear time. Off course, input taking should not be considered in complexity analysis (Surely you've understood by this time that I have very poor knowledge in this :wink:) & then the solution is obviously O(1) for test case. But the algorithm is similar to distribution counting which is theoritically O(n). So, I just wanted to make sure if this is the case or should there be anything even faster. Thanks for your explanation, anyway. :)

10474_OLE

Posted: Thu Oct 27, 2005 4:57 pm
by mohsincsedu
hello i am a new solver!!!!! I do not understand why i got OLE!!!!!!
Plz tell me about this!!!!

Thanks in Advance :wink:

Posted: Thu Oct 27, 2005 7:26 pm
by Solaris

Posted: Thu Oct 27, 2005 9:52 pm
by mohsincsedu
Thanks Solaris...
But where is infinite loop in my code:
Here is my code:

Code: Select all

#include<stdio.h>

#define MAX 10010

void main()
{
	int table[MAX],i,N,Q,num,test = 1;
	long long res;

	while(scanf("%d %d",&N,&Q)==2)
	{
		if(!N&&!Q)
			break;
		for(i = 0;i<MAX;i++)
			table[i] = 0;
		for(i = 0; i<N;i++)
		{
			scanf("%d",&num);
			table[num]++;
		}
		printf("CASE# %d:\n",test++);
		for(i = 0;i<Q;i++)
		{
			scanf("%d",&num);
			res = 0;
			if(table[num])
			{
				for(i = 0; i<num;i++)
					res+=table[i];
				printf("%d found at %lld\n",num,res+1);
			}
			else
				printf("%d not found\n",num);

		}
	}
}

Posted: Fri Oct 28, 2005 9:15 pm
by Solaris

Code: Select all

       for(i = 0;i<Q;i++)
      {
         scanf("%d",&num);
         res = 0;
         if(table[num])
         {
            for(i = 0; i<num;i++)
               res+=table[i];
            printf("%d found at %lld\n",num,res+1);
         }
         else
            printf("%d not found\n",num);

      }
 
u r using same loop variable 'i' in the inner and outer loop. this may cause unexpected result.

and please check your code yourself for these kind of mistakes before posting.

Posted: Sun Oct 30, 2005 7:04 am
by mohsincsedu
Thanks a lot!!!!!
I got Ac..
:lol:
ok i obey ur Advised!!!

Posted: Sat Aug 11, 2007 3:29 pm
by lnr

Code: Select all

changed

thanks mmonish.
[/size]

Posted: Sun Aug 12, 2007 1:17 am
by mmonish
>>lnr
Ur partition function isn't right. I do some change in ur code & i think it will work.
long partition(int a[],int p,int r)
{
int x,temp,i,j;
x=a[r];
i=p-1;
for(j=p;j<r;j++)
{
if(a[j]<=x) // instead of if(a[j] > x)
{
i++;
temp=a;
a=a[j];
a[j]=temp;
}
}
temp=a[i+1];
a[i+1]=a[r]; //instead of a[j]
a[r]=temp;

return i+1;
}

gettin wrong answer why

Posted: Thu Feb 28, 2008 7:54 pm
by mirage
hey friends....
i m gettin a wrong answer for this simple prob.....
did the sort n search.....but the judge shows error
can't figure out why???
plz help:

Code: Select all

//where's the marble
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> v;
int find(int);
int main(){
	int a,b;
	int count=0;
	while(cin>>a>>b){
		if(a+b==0) return(0);
		cout<<"CASE# "<<++count<<":\n";
		int i=0;
		int u;
		while(i<a){
			cin>>u;
			v.push_back(u);
			i++;
		}
		sort(v.begin(),v.end());
		i=0;
		while(i<b){
			cin>>u;
			int res=find(u);
			if(res!=-1) cout<<u<<" found at "<<res+1<<"\n";
			else cout<<u<<" not found"<<"\n";
			i++;
		}
		v.clear();
	}
	return(0);
}
int find(int no){
	int i=0;
	while(i<no){
		if(v[i]==no) return(i);
		i++;
	}
	return(-1);
}

TLE...

Posted: Tue Mar 25, 2008 11:28 am
by Obaida
How I can avoid TLE... hear.. Some one plesase help me out...

Code: Select all

#include<stdio.h>
int main()
{
	int m,n,i,x[10005],y[10005],mid,j,pot,end,big,count,c=0;
	while(scanf("%d %d",&m,&n)==2&&(m!=0&&n!=0))
	{
		c++;
		for(i=1;i<=m;i++)
		{
			scanf("%d",&x[i]);
		}
		int pot =0;
		for(i=1;i<=m;i++)
		{
			for(int j=i+1;j<=m;j++)
			{
				if(x[i]>x[j])
				{
					pot=x[j];
					x[j]=x[i];
					x[i]=pot;
				}
			}
		}
		for(i=1;i<=n;i++)
		{
			scanf("%d",&y[i]);
		}
		printf("CASE# %d:\n",c);
		for(i=1;i<=n;i++)
		{
			 big=1;
			 end=m;
			 count =1;
			 while(end>=big)
			 {
					mid=(big+end)/2;
					if(x[mid]<y[i])
						big=mid+1;
					else if(x[mid]>y[i])
						end=mid-1;
					else
					{
						count=0;
						break;
					}
			 }
			 if(count==0)
				printf("%d found at %d\n",y[i],mid);
			 if(count==1)
				printf("%d not found\n",y[i]);
		}
	}
return 0;
}

Posted: Thu Mar 27, 2008 6:04 pm
by Jan
Use a faster sorting algorithm. (qsort, mergesort etc)

10474 WA

Posted: Thu Oct 30, 2008 5:04 pm
by Tahasin
I can't understand what's wrong with my program. I used quick sort and binary search.
Please someone help me....please
here is my program

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>

using namespace std;

void quick(int *A,int p,int r);
int partition(int *A,int p,int r);
int binary(int *a,int n, int k);


int main()
{
	int n,m;
	int count =0;
	while(scanf("%d %d",&n,&m)==2)
	{
		if(n==0 && m == 0)break;
		int a[100000],b[10000];
		for(int i = 1; i <= n; i++)scanf("%d",&a[i]);
		for(int i = 1; i<=m; i++)scanf("%d",&b[i]);
		quick(a,1,n);
		printf("CASE# %d:\n",++count);
		for(int i = 1; i <= m; i++)
		{
			int k = binary(a,n,b[i]);
			if(!k)printf("%d not found\n",b[i]);
			else 
			{
				if(a[k-1]==b[i])
				{
					while(a[k]==b[i])
					{
						k--;
					}
					k++;
				}
				printf("%d found at %d\n",b[i],k);
			}
		}
	}
}


int binary(int *a,int n, int k)
{
	int lb = 1, ub = n;
	int mid = (lb+ub)/2;
	while(a[mid]!=k && lb < ub)
	{
		if(a[mid]>k)ub = mid - 1;
		else if(a[mid]<k)lb = mid+1;
		mid = (lb+ub)/2;
	}
	if(a[mid]==k)return mid;
	else return 0;
}

void quick(int *A,int p,int r)
{
	int q;
	if(p<r)
	{
		q=partition(A,p,r);
		quick(A,p,q-1);
		quick(A,q+1,r);
	}
	
}

int partition(int *A,int p,int r)
{
	int x,i,j,temp;
	x=A[r];
	i=p-1;
	for(j=p;j<=r-1;j++)
	{
		if(A[j]<=x)
		{
			i++;
			temp=A[i];
			A[i]=A[j];
			A[j]=temp;
		}
	}
	temp=A[i+1];
	A[i+1]=A[r];
	A[r]=temp;
	return (i+1);
}


10474 - Where is the Marble? WA !!!!! DAMN......

Posted: Sun Jan 11, 2009 6:18 pm
by toru
Hi, i guess there is no prob if i do this by qsort && binary search..... or m i wrong????,
Anywayz i attach my code, any kind guru plzzzz help!!!!!!!!!!!!!!!!

Code: Select all


#include<stdio.h>
#include<stdlib.h>
#define MAX 100000

int fun_name(  const void *a, const void *b )
{
	long *p = (long *)a;  
	long *q = (long *)b;  
	return *p - *q ;   
}

int main()
{
	long n, m, test=0, i, beg, end, mid, found;
	long myarray[MAX], find[MAX];

	while(scanf("%ld %ld", &n, &m)==2)
	{
		if(n==0 && m==0)
			break;

		printf("CASE# %d:\n",++test);
	    
		for(i=0; i<n; i++)
			 scanf("%ld", &myarray[i]);
	
		qsort( myarray, n, sizeof(long), fun_name );

		for(i=0; i<m; i++)
			scanf("%ld", &find[i]);
		 		   
		for(i=0; i<m; i++)
		{
		   beg=end=mid=found=0;
		   
		   if(find[i]==myarray[0])
		   	   printf("%ld found at 1\n", item);
		   else
		   {
		     end=n-1;
		     mid=long((beg+end)/2);

		   while(beg<end && find[i]!=myarray[mid])
		   {
			   if(find[i]<myarray[mid])
				   end=mid-1;
			   else
				   beg=mid+1;

			   mid=long((beg+end)/2);
		   }

		   if(myarray[mid]==find[i])
		   	   printf("%ld found at %ld\n", find[i], mid+1);
		   else
			   printf("%ld not found\n", find[i]);
		   }
		}
	}
	return 0;
}
:( :( :( :( :( :( :( :(

Re: 10474 - Where is the Marble? WA !!!!! DAMN......

Posted: Mon Jan 12, 2009 2:27 am
by newkid
suppose after sorting your myarray is like this
[1, 3, 3, 3, 3, 3, 3]
now a query for 3 you will print
3 found at 4
which is not correct. fix your binary search portion. you need the lowest index that matches with the given query number..

Hope this helps..
toru wrote:Hi, i guess there is no prob if i do this by qsort && binary search..... or m i wrong????,
Anywayz i attach my code, any kind guru plzzzz help!!!!!!!!!!!!!!!!

Code: Select all


#include<stdio.h>
#include<stdlib.h>
#define MAX 100000

int fun_name(  const void *a, const void *b )
{
	long *p = (long *)a;  
	long *q = (long *)b;  
	return *p - *q ;   
}

int main()
{
	long n, m, test=0, i, beg, end, mid, found;
	long myarray[MAX], find[MAX];

	while(scanf("%ld %ld", &n, &m)==2)
	{
		if(n==0 && m==0)
			break;

		printf("CASE# %d:\n",++test);
	    
		for(i=0; i<n; i++)
			 scanf("%ld", &myarray[i]);
	
		qsort( myarray, n, sizeof(long), fun_name );

		for(i=0; i<m; i++)
			scanf("%ld", &find[i]);
		 		   
		for(i=0; i<m; i++)
		{
		   beg=end=mid=found=0;
		   
		   if(find[i]==myarray[0])
		   	   printf("%ld found at 1\n", item);
		   else
		   {
		     end=n-1;
		     mid=long((beg+end)/2);

		   while(beg<end && find[i]!=myarray[mid])
		   {
			   if(find[i]<myarray[mid])
				   end=mid-1;
			   else
				   beg=mid+1;

			   mid=long((beg+end)/2);
		   }

		   if(myarray[mid]==find[i])
		   	   printf("%ld found at %ld\n", find[i], mid+1);
		   else
			   printf("%ld not found\n", find[i]);
		   }
		}
	}
	return 0;
}
:( :( :( :( :( :( :( :(

Re: 10474 - Where is the Marble?

Posted: Fri Apr 29, 2011 8:05 pm
by devmehedee
No need for binary search or other optimization, Just count sort will do... After Count Sort, I used Linear Search and got clean AC (0.616s). :D