10474 - Where is the Marble?

Red Scorpion · Post by **Red Scorpion** » Mon Apr 14, 2003 12:06 pm

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 · Post by **kmhasan** » Mon Apr 14, 2003 12:25 pm

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 · Post by **Red Scorpion** » Tue Apr 15, 2003 6:29 am

Hehehe..
Thanks, Kmhasan.
I Got AC in less than 1 S.

kmhasan · Post by **kmhasan** » Tue Apr 15, 2003 7:18 pm

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 · Post by **kmhasan** » Wed Apr 16, 2003 3:56 am

Ok.

erfan · Post by **erfan** » Thu Apr 17, 2003 2:28 pm

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 · Post by **erfan** » Sat Apr 19, 2003 7:49 am

Ohho suctg you should not misunderstand me.You wrote "I have already done it anyway" actually i missed it.Now it's ok

kmhasan · Post by **kmhasan** » Sat Apr 19, 2003 6:35 pm

It is quite unfortunate that I have to post this useless message. I wish someday I

erfan · Post by **erfan** » Sun Apr 20, 2003 10:29 am

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 · Post by **razibcse** » Sun Apr 20, 2003 8:52 pm

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?

kmhasan · Post by **kmhasan** » Mon Apr 21, 2003 4:30 am

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 · Post by **sumankar** » Thu Oct 30, 2003 12:09 pm

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

Joybo · Post by **Joybo** » Tue Nov 04, 2003 3:29 pm

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 · Post by **wyanez** » Mon Nov 24, 2003 7:57 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. · Post by **Whinii F.** » Tue Nov 25, 2003 9:29 pm

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.

OJ Board

10474 - Where is the Marble?

10474 - Where is the Marble?

OLE: Why ???

10474 wa~who can help me