Page **2** of **4**

### 10474: Marbels (TLE Help Plesae)

Posted: **Wed Mar 10, 2004 8:08 am**

by **Jewel of DIU**

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

Posted: **Wed Mar 10, 2004 10:05 am**

by **alu_mathics**

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.

### Wrong Approach?

Posted: **Wed Mar 10, 2004 10:23 am**

by **sohel**

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.

Posted: **Wed Mar 10, 2004 11:36 am**

by **Jewel of DIU**

I have now got WA

.

Please Give me some Input and Output. So that i can find my code's bug.

Posted: **Wed Mar 10, 2004 8:03 pm**

by **alu_mathics**

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

### Thanks

Posted: **Sat Mar 13, 2004 5:30 pm**

by **Jewel of DIU**

Thank you Shohel bhai & Aftab Bhai for your help. I have now got AC.

Thank u very very very much.

### p10474 WA

Posted: **Thu Mar 18, 2004 11:53 am**

by **WR**

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!

Posted: **Thu Mar 18, 2004 3:19 pm**

by **Dominik Michniewski**

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

Posted: **Thu Mar 18, 2004 4:01 pm**

by **WR**

Thanks DM,

I wanted to know that for quite some time, but always forgot

to ask.

As to the problem, I'll try with counting sort.

bye

added 22.3.04

Accepted using counting sort!

Posted: **Mon Apr 05, 2004 9:53 pm**

by **kiha**

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

Posted: **Wed Jun 23, 2004 11:05 am**

by **miras**

Dear Kiha

Sth is wrong with you BS

( try to rewrite it )

BTW i think that it is why u get WA...

### 10474

Posted: **Sun Jun 12, 2005 8:27 am**

by **Salman**

got TLE on 10474

How can I improve????

[code]

code removed after AC

[/code]

Posted: **Sun Jun 12, 2005 3:08 pm**

by **sidky**

change the whole approach. the solution can be retrived in constant time.

Posted: **Tue Jun 14, 2005 10:50 pm**

by **Mohammad Mahmudur Rahman**

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.

### O(1) explanation

Posted: **Wed Jun 15, 2005 12:43 pm**

by **Sedefcho**

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.