10474 - Where is the Marble?

[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 ) & 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.

[mohsincsedu]

hello i am a new solver!!!!! I do not understand why i got OLE!!!!!!
Plz tell me about this!!!!

Thanks in Advance

[Solaris]

http://online-judge.uva.es/board/viewtopic.php?t=7430

[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);

		}
	}
}

[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.

[mohsincsedu]

Thanks a lot!!!!!
I got Ac..

ok i obey ur Advised!!!

[lnr]

Code: Select all

changed

thanks mmonish.

[/size]

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

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

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

[Jan]

Use a faster sorting algorithm. (qsort, mergesort etc)

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

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

[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..

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

[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).