10474  Where is the Marble?
Moderator: Board moderators

 New poster
 Posts: 32
 Joined: Thu Jul 31, 2003 6:21 am
 Location: Daffodil Univ, Bangladesh
 Contact:
10474: Marbels (TLE Help Plesae)
I tried to solve the problem but got TLE.
Here is my search algorithm
[c]
 CUT AFTER AC 
(I HAVE USE COUNTING SORT)
[/c]
Help me Please to improve my time. :
Here is my search algorithm
[c]
 CUT AFTER AC 
(I HAVE USE COUNTING SORT)
[/c]
Help me Please to improve my time. :
Last edited by Jewel of DIU on Sat Mar 20, 2004 10:50 am, edited 1 time in total.
Hate WA
Visit phpBB!
Visit phpBB!
 alu_mathics
 Learning poster
 Posts: 55
 Joined: Sat Jan 24, 2004 9:30 pm
 Location: Chittagong
 Contact:
I also got TLE using searching.Then i use memorization and got AC.
Count the occurence of each number using array(size of 10000 and initially all 0).Then try to figure out your desire answer from this array.
And remember its a problem of TOMAL bhai.So what looks easy actually
it is not.He really makes us to think deeper and also optimal.
Count the occurence of each number using array(size of 10000 and initially all 0).Then try to figure out your desire answer from this array.
And remember its a problem of TOMAL bhai.So what looks easy actually
it is not.He really makes us to think deeper and also optimal.
Last edited by alu_mathics on Wed Mar 10, 2004 10:32 am, edited 1 time in total.
cuii e
Wrong Approach?
Using linear search , O(N) will certainly get TLE.
In the real time contest ( At Daffadil ) we tried to solve it using binary search but still could not pass the time limit ( of 1 second ) .
You have to use counting sort to solve this problem.
If you are not familiar with counting sort then:
maintain a array which counts the frequecny of each number.
use another array that maintains the cumulative frequency....
then do whatever is required.
Hope it helps.
In the real time contest ( At Daffadil ) we tried to solve it using binary search but still could not pass the time limit ( of 1 second ) .
You have to use counting sort to solve this problem.
If you are not familiar with counting sort then:
maintain a array which counts the frequecny of each number.
use another array that maintains the cumulative frequency....
then do whatever is required.
Hope it helps.

 New poster
 Posts: 32
 Joined: Thu Jul 31, 2003 6:21 am
 Location: Daffodil Univ, Bangladesh
 Contact:
I have now got WA .
Please Give me some Input and Output. So that i can find my code's bug.
Please Give me some Input and Output. So that i can find my code's bug.
Hate WA
Visit phpBB!
Visit phpBB!
 alu_mathics
 Learning poster
 Posts: 55
 Joined: Sat Jan 24, 2004 9:30 pm
 Location: Chittagong
 Contact:
input:
10 5
1
1
3
5
7
1
3
9
120
1
1
3
120
7
1234
10 12
1111
1111
1111
5
5
5
10
11
12
10
1111
5
10
11
12
1111
134
567
246
24
12
435
output:
CASE# 1:
1 found at 1
3 found at 5
120 found at 10
7 found at 8
1234 not found
CASE# 2:
1111 found at 8
5 found at 1
10 found at 4
11 found at 6
12 found at 7
1111 found at 8
134 not found
567 not found
246 not found
24 not found
12 found at 7
435 not found
//mind it no value will be greater than 10000
10 5
1
1
3
5
7
1
3
9
120
1
1
3
120
7
1234
10 12
1111
1111
1111
5
5
5
10
11
12
10
1111
5
10
11
12
1111
134
567
246
24
12
435
output:
CASE# 1:
1 found at 1
3 found at 5
120 found at 10
7 found at 8
1234 not found
CASE# 2:
1111 found at 8
5 found at 1
10 found at 4
11 found at 6
12 found at 7
1111 found at 8
134 not found
567 not found
246 not found
24 not found
12 found at 7
435 not found
//mind it no value will be greater than 10000
cuii e

 New poster
 Posts: 32
 Joined: Thu Jul 31, 2003 6:21 am
 Location: Daffodil Univ, Bangladesh
 Contact:
Thanks
Thank you Shohel bhai & Aftab Bhai for your help. I have now got AC.
Thank u very very very much.
Thank u very very very much.
Hate WA
Visit phpBB!
Visit phpBB!
p10474 WA
I know there's a more effective solution and sorting's not necessary, but anyway...
Using quicksort and binary search my program received a WA in
about 0,1 seconds (forgot the exact timing, less than 0,2 s in any case).
My question is: When does the OJ return a WA? Immediately after getting a wrong result or only after evaluating all sample input?
Thank you
Oh, by the way, some test data would be welcome. There's no difference between my output and alu_mathics' output!
Using quicksort and binary search my program received a WA in
about 0,1 seconds (forgot the exact timing, less than 0,2 s in any case).
My question is: When does the OJ return a WA? Immediately after getting a wrong result or only after evaluating all sample input?
Thank you
Oh, by the way, some test data would be welcome. There's no difference between my output and alu_mathics' output!

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
If your program not exceed time limit t finish first, and after that comparing your output witth judge output is done. Depends of result of comparing apropriate message is given to you
So if you got WA in less than 0.2 sec, than you'va been sure, that your program run trough all cases, but got wrong results to output ...
Best regards
DM
PS. When I try to solve this problem (on contest time) I have the same problem  I got WA or TLE,l depending on algorithm I use. But at end I manage wirth described below algorithm (with counting) and got Acc
So if you got WA in less than 0.2 sec, than you'va been sure, that your program run trough all cases, but got wrong results to output ...
Best regards
DM
PS. When I try to solve this problem (on contest time) I have the same problem  I got WA or TLE,l depending on algorithm I use. But at end I manage wirth described below algorithm (with counting) and got Acc
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
I have WA, but I don't understand why ...
I used quicksort & binary search. I knew there exists a quicker algorithm using counting sort , but I would like to know why this gives me WA:
[pascal]
program miazio;
type mia = array [1..10000] of longint;
var
t:mia;
i, j, k, l:longint;
le, e, lz, z, kejs:longint;
poz, lewy, srodek, prawy:longint;
begin
kejs:=0;
while not eof do
begin
readln (le, lz);
if (le = 0) and (lz = 0) then exit;
inc (kejs);
writeln ('CASE# ', kejs, ':');
for i:=1 to le do
readln (t );
qsort (t);
for z:=1 to lz do
begin
readln (l);
lewy:=1;
prawy:=le;
repeat
srodek:=(lewy + prawy) div 2;
if t [srodek] <> l then
if t [srodek] < l then
lewy:=srodek else
prawy:=srodek;
until (t [srodek] = l) or (lewy >= prawy) or ((lewy = prawy  1) and (lewy = srodek));
if (lewy = srodek) and (lewy = prawy  1) then inc (srodek);
if t [srodek] <> l then
writeln (l, ' not found') else
begin
while (t [srodek  1] = l) and (srodek > 1) do
dec (srodek);
writeln (l, ' found at ', srodek);
end;
end;
end;
end.
[/pascal]
I deleted procedure quicksort, which must be right as I cut if from Free Pascal's sample qsort.pp
I used quicksort & binary search. I knew there exists a quicker algorithm using counting sort , but I would like to know why this gives me WA:
[pascal]
program miazio;
type mia = array [1..10000] of longint;
var
t:mia;
i, j, k, l:longint;
le, e, lz, z, kejs:longint;
poz, lewy, srodek, prawy:longint;
begin
kejs:=0;
while not eof do
begin
readln (le, lz);
if (le = 0) and (lz = 0) then exit;
inc (kejs);
writeln ('CASE# ', kejs, ':');
for i:=1 to le do
readln (t );
qsort (t);
for z:=1 to lz do
begin
readln (l);
lewy:=1;
prawy:=le;
repeat
srodek:=(lewy + prawy) div 2;
if t [srodek] <> l then
if t [srodek] < l then
lewy:=srodek else
prawy:=srodek;
until (t [srodek] = l) or (lewy >= prawy) or ((lewy = prawy  1) and (lewy = srodek));
if (lewy = srodek) and (lewy = prawy  1) then inc (srodek);
if t [srodek] <> l then
writeln (l, ' not found') else
begin
while (t [srodek  1] = l) and (srodek > 1) do
dec (srodek);
writeln (l, ' found at ', srodek);
end;
end;
end;
end.
[/pascal]
I deleted procedure quicksort, which must be right as I cut if from Free Pascal's sample qsort.pp
kiha

 Experienced poster
 Posts: 154
 Joined: Sat Apr 17, 2004 9:34 am
 Location: EEE, BUET
to Salman 
You can get it within time limit using binary search, too. But you must use a faster (n log n) sorting algorithm.
to Sidky 
Will you explain what is the O(1) method? I can see a O(n) solution using counting sort & AFAIK the judge solution for this problem is based on this method, too. But O(1) seems to be too much for me.
You can get it within time limit using binary search, too. But you must use a faster (n log n) sorting algorithm.
to Sidky 
Will you explain what is the O(1) method? I can see a O(n) solution using counting sort & AFAIK the judge solution for this problem is based on this method, too. But O(1) seems to be too much for me.
You should never take more than you give in the circle of life.
O(1) explanation
Mohammad Mahmudur Rahman,
I suggest you read the previous posts about this problem.
What is meant by O(1) is that you can give the answer
for each Query Number in a given TEST in a O(1) time.
What I call a TEST is (A) plus (B), where:
(A) is the SET of the N numbers which are given
(B) is the SET of the Q numbers ( the SET of the query numbers )
So how it goes ?
(1) you read the N numbers which are given
(2) you do some preprocessing
(3) you start reading the Q query numbers and each time a query
number comes from the input you can give the answer for that
query number in O(1) time
The key phrase in this problem is that the numbers given are
in the interval [1,10000]. Which allows a memoization approach
to be used ( that memoization is done in the preprocessing
phase  see (2) above ).
No binary search is needed, no sorting, no complex data
structures. Two arrays of 10000 elements each will be enough.
I suggest you read the previous posts about this problem.
What is meant by O(1) is that you can give the answer
for each Query Number in a given TEST in a O(1) time.
What I call a TEST is (A) plus (B), where:
(A) is the SET of the N numbers which are given
(B) is the SET of the Q numbers ( the SET of the query numbers )
So how it goes ?
(1) you read the N numbers which are given
(2) you do some preprocessing
(3) you start reading the Q query numbers and each time a query
number comes from the input you can give the answer for that
query number in O(1) time
The key phrase in this problem is that the numbers given are
in the interval [1,10000]. Which allows a memoization approach
to be used ( that memoization is done in the preprocessing
phase  see (2) above ).
No binary search is needed, no sorting, no complex data
structures. Two arrays of 10000 elements each will be enough.