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

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
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.
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

hello i am a new solver!!!!! I do not understand why i got OLE!!!!!!

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
Where's the "Any" key?

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:
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

}
}
}``````

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

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

}
``````
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:
Thanks a lot!!!!!
I got Ac..

ok i obey ur Advised!!!

lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 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
>>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

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

TLE...

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)
}
}
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
Contact:
Use a faster sorting algorithm. (qsort, mergesort etc)

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

10474 WA

I can't understand what's wrong with my program. I used quick sort and binary search.
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]);
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......

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
}
}
}
return 0;
}
``````

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

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

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

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