## 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

Red Scorpion
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.

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:
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.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Hehehe..
Thanks, Kmhasan.
I Got AC in less than 1 S.

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:
suctg wrote:Please help me by posting your code
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.

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.

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:
Ok.

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:
Mr suctg:
You should not request for OJ Acc code.
You can solve it by O(n).You can not sort it but use bitwise method.In one loop to maximum is sufficient for it.You can use adress of input value instead of sort.I think it is more::
I think you can realize what i want to say.

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:
Ohho suctg you should not misunderstand me.You wrote "I have already done it anyway" actually i missed it.Now it's ok

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:
It is quite unfortunate that I have to post this useless message. I wish someday I

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:
Ok i think it's enough.Now we should stop our debug.Actually it is misunderestand within our communication.Thanks tomal and also suctg.

razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Location: SUST,BANGLADESH
Contact:
Hi,
I thought it was really an easy problem. But I am getting RTE.The problem statement said,
Be assured, none of the input numbers are greater than 10000 and none of them are negative.
What does it mean? is the maximum size of the number array 10000?
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.

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:
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.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

### OLE: Why ???

No idea why I am getting OLE !
Can anyone help ?plz
Suman.

Joybo
New poster
Posts: 4
Joined: Tue Sep 23, 2003 12:05 pm

### 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=left-1; 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,i-1);
quick(j+1,right);
}
}

int serach(int key){
int low=0,high=N-1,mid;
while(low<=high){
mid=(low+high)/2;
if(ar[mid]==key) return mid;
if(ar[mid]<key) low=mid+1;
else high=mid-1;
}
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,N-1);

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]

wyanez
New poster
Posts: 8
Joined: Thu Nov 20, 2003 7:19 pm
The problem can be in the search, these using "binary search" and this return the position of the element if it finds it in the center and not in the first occurrence.

Test this input:
3 1
2
2
2
2
0 0

Test using linear search, good luck!

Whinii F.
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.
JongMan @ Yonsei