10474  Where is the Marble?
Moderator: Board moderators

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
10474  Where is the Marble?
I got AC for this problem in 2.107 S. I saw the others got AC in less than 1 second. Could someone tell me how to make this problem faster ?
First I sort the marbles using quicksort, and search that with binary search.
The judge solution was inspired by Couting Sort. The problem can be solved without sorting. Try to find out how many numbers are there which are smaller than a particular number.
Enough for a hint, I believe.
Enough for a hint, I believe.
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
Please do not ask people to post code that is already accepted by the UVA OJ. It makes no sense actually. Here we'd like to share our ideas publicly, but not our codes. You can always ask for code in a private message, though.suctg wrote:Please help me by posting your code
I wouldn't have intervened in this matter. It's only that this particular problem is one of the easiest at UVA; beginners should get a chance to think before they get a chance to look at a sample solution. And I'm also a bit worried to see that this is not the only problem you have asked for code publicly.
No hard feelings, mate.
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/
It is quite unfortunate that I have to post this useless message. I wish someday I
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/
Hi,
I thought it was really an easy problem. But I am getting RTE.The problem statement said,
I made this upto 900000, but same result...
Can you say what I should do?
I thought it was really an easy problem. But I am getting RTE.The problem statement said,
What does it mean? is the maximum size of the number array 10000?Be assured, none of the input numbers are greater than 10000 and none of them are negative.
I made this upto 900000, but same result...
Can you say what I should do?
Wisdom is know what to do next; virtue is doing it.
It means 0<=N<=10000 AND 0<=Q<=10000 AND all the numbers (be it a number on the marble or a query number) are between 1 and 10000. When N=0 and Q=0 the input ends, and you must ignore that test case.
I had a simple input validator to check the generated input for the problem. So I am quite sure that it goes along with the problem statement. Even then, if you find that there are inconsistency please let me know.
I had a simple input validator to check the generated input for the problem. So I am quite sure that it goes along with the problem statement. Even then, if you find that there are inconsistency please let me know.
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/
OLE: Why ???
No idea why I am getting OLE !
Can anyone help ?plz
Suman.
Can anyone help ?plz
Suman.
10474 wa~who can help me
It seems very easy, but I don't know what the bug in my program.
Who can tell me the bug or some notes?
[c]
#include <stdio.h>
#define MAXSIZE 10000
int N,Q,ar[MAXSIZE];
void quick(int left,int right){
int s,t,i,j,m;
if(left<right){
s=ar[(left+right)/2];
i=left1; j=right+1;
while(1){
while(ar[++i]<s);
while(ar[j]>s);
if(i>=j) break;
t=ar; ar=ar[j]; ar[j]=t;
}
quick(left,i1);
quick(j+1,right);
}
}
int serach(int key){
int low=0,high=N1,mid;
while(low<=high){
mid=(low+high)/2;
if(ar[mid]==key) return mid;
if(ar[mid]<key) low=mid+1;
else high=mid1;
}
return 1;
}
void main(void){
int times,i,j;
int tempn,temp;
for(times=1;;times++){
scanf("%d%d",&N,&Q);
if(!N && !Q) break;
printf("CASE# %d:\n",times);
for(i=0;i<N;i++) scanf("%d",&ar);
quick(0,N1);
for(j=0;j<Q;j++){
scanf("%d",&tempn);
if(N!=0) temp=serach(tempn);
if(temp==1) printf("%d not found\n",tempn);
else printf("%d found at %d\n",tempn,temp+1);
}
}
}
[/c]
Who can tell me the bug or some notes?
[c]
#include <stdio.h>
#define MAXSIZE 10000
int N,Q,ar[MAXSIZE];
void quick(int left,int right){
int s,t,i,j,m;
if(left<right){
s=ar[(left+right)/2];
i=left1; j=right+1;
while(1){
while(ar[++i]<s);
while(ar[j]>s);
if(i>=j) break;
t=ar; ar=ar[j]; ar[j]=t;
}
quick(left,i1);
quick(j+1,right);
}
}
int serach(int key){
int low=0,high=N1,mid;
while(low<=high){
mid=(low+high)/2;
if(ar[mid]==key) return mid;
if(ar[mid]<key) low=mid+1;
else high=mid1;
}
return 1;
}
void main(void){
int times,i,j;
int tempn,temp;
for(times=1;;times++){
scanf("%d%d",&N,&Q);
if(!N && !Q) break;
printf("CASE# %d:\n",times);
for(i=0;i<N;i++) scanf("%d",&ar);
quick(0,N1);
for(j=0;j<Q;j++){
scanf("%d",&tempn);
if(N!=0) temp=serach(tempn);
if(temp==1) printf("%d not found\n",tempn);
else printf("%d found at %d\n",tempn,temp+1);
}
}
}
[/c]

 Experienced poster
 Posts: 151
 Joined: Wed Aug 21, 2002 12:07 am
 Location: Seoul, Korea
 Contact:
I myself didn't solve this one but you can find "first" expected key when there are duplicates too. This one is covered in "Programming Pearls", a book of collection of issues from CACM.
So for your binary search you have a loop invariant, for each turn, the index I you are looking for, suffices the following:
L <= I <= R.
Now suppose you're looking for the first index I'. Then have a loop invariant condition like this:
L < I <= R. So you're finding the key in the range (L, R].
If you test an element M:
if Expected_Key <= M, then R = M
if M < Expected_Key, then L = M
You will see this will preserve the invariant condition. So when L+1 = R, the search ends.
Keep in mind you need to give different initial values for this binary search. Why? Give it a try to figure out..
ps) and for this problem, there is no need for a searching.
So for your binary search you have a loop invariant, for each turn, the index I you are looking for, suffices the following:
L <= I <= R.
Now suppose you're looking for the first index I'. Then have a loop invariant condition like this:
L < I <= R. So you're finding the key in the range (L, R].
If you test an element M:
if Expected_Key <= M, then R = M
if M < Expected_Key, then L = M
You will see this will preserve the invariant condition. So when L+1 = R, the search ends.
Keep in mind you need to give different initial values for this binary search. Why? Give it a try to figure out..
ps) and for this problem, there is no need for a searching.
JongMan @ Yonsei