Page 3 of 4
Posted: 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 ) & 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
hello i am a new solver!!!!! I do not understand why i got OLE!!!!!!

Thanks in Advance Posted: Thu Oct 27, 2005 7:26 pm

Posted: 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

}
}
}``````

Posted: 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

}
``````
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
Thanks a lot!!!!!
I got Ac.. Posted: Sat Aug 11, 2007 3:29 pm

Code: Select all

``````changed

thanks mmonish.
``````
[/size]

Posted: 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[r]=temp;

return i+1;
}

Posted: 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";
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
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,y,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;
}``````

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

### 10474 WA

Posted: Thu Oct 30, 2008 5:04 pm
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,b;
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);
}

``````

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

Posted: 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)
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;
}
``````        ### Re: 10474 - Where is the Marble? WA !!!!! DAMN......

Posted: 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)
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        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). 