10474 - Where is the Marble?

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

Moderator: Board moderators

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Wed Jun 15, 2005 3:04 pm

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. :)
You should never take more than you give in the circle of life.

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

10474_OLE

Post by mohsincsedu » Thu Oct 27, 2005 4:57 pm

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

Thanks in Advance :wink:

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Thu Oct 27, 2005 7:26 pm

Where's the "Any" key?

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

Post by mohsincsedu » Thu Oct 27, 2005 9:52 pm

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
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Fri Oct 28, 2005 9:15 pm

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.
Where's the "Any" key?

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

Post by mohsincsedu » Sun Oct 30, 2005 7:04 am

Thanks a lot!!!!!
I got Ac..
:lol:
ok i obey ur Advised!!!

lnr
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Post by lnr » Sat Aug 11, 2007 3:29 pm

Code: Select all

changed

thanks mmonish.
[/size]
Last edited by lnr on Sun Aug 12, 2007 1:09 pm, edited 1 time in total.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Sun Aug 12, 2007 1:17 am

>>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
New poster
Posts: 11
Joined: Sat Jan 19, 2008 9:37 pm

gettin wrong answer why

Post by mirage » Thu Feb 28, 2008 7:54 pm

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
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

TLE...

Post by Obaida » Tue Mar 25, 2008 11:28 am

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;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Mar 27, 2008 6:04 pm

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

Tahasin
New poster
Posts: 6
Joined: Tue Jun 27, 2006 7:19 am

10474 WA

Post by Tahasin » Thu Oct 30, 2008 5:04 pm

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
New poster
Posts: 17
Joined: Tue Dec 30, 2008 10:38 am

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

Post by toru » Sun Jan 11, 2009 6:18 pm

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
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

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

Post by newkid » Mon Jan 12, 2009 2:27 am

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;
}
:( :( :( :( :( :( :( :(
hmm..

devmehedee
New poster
Posts: 2
Joined: Sun Apr 17, 2011 11:52 am
Location: CSE BUET, Bangladesh.

Re: 10474 - Where is the Marble?

Post by devmehedee » Fri Apr 29, 2011 8:05 pm

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
Think FREE, Think OPEN SOURCE

Post Reply

Return to “Volume 104 (10400-10499)”