Discussion @ 1494. Monobilliards @ Timus Online Judge

Alexey What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [11] // Problem 1494. Monobilliards 2 Nov 2006 18:48

Samsonov Alex [USU] Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [9] // Problem 1494. Monobilliards 3 Nov 2006 18:13

What do you mean by "ALMOST O(n)"?

Alexey Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [8] // Problem 1494. Monobilliards 4 Nov 2006 11:19

I mean that I have a loop to read data. It is O(n).
But in it I have a loop for checking.
In most cases it is about some iterations,
but there are some tests that make my algo O(n^2).
How to make it faster?

svr Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [7] // Problem 1494. Monobilliards 4 Nov 2006 12:34

I think that next sketch is O(N)

Let x[1]...x[N]- revisor sequence

k- Current number of an element of x under consideration

NN- number of balls in billiard pocket now +last ball x[k]

xx[]- aray of balls now in billiard pocket for moment k + last ball x[k]

S-number of operations

//Begining

k=1 ;NN=x[1]; xx[]=[1..NN];//array assignment- x[1]- operations

S:=x[1];

// Loop

aa:

j:=0;

while (x[k+j]==xx[NN-j]) j++ //revisor takes seguental balls

//from Billiard pocket;S:=S+j;

k=k+j- next position

if (k==N+1) "«Not a proof». END

NN=NN-j; //number of balls in pocket after Session of taking; S:=S+1;

m1=xx[k1]- next ball after timeout

If (m1<=m) -"Cheater"//meet number smallet than taken

xx[NN+1..NN+m1-m]:=[m+1..m1];// new sequence in billiard pocket

//under ptevious rest S+=m1-m operations

NN:=NN+m1-m;//renew S=S+1;

goto aa

//Loop

The resume: S<=2*N -- O(N)

Alexey Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [5] // Problem 1494. Monobilliards 4 Nov 2006 16:06

I have such algo:
a[0..100000]. a[i] means minimal number that can be taken
after i not to be a cheater.
during reading datas i have to cerrect the massive.
but there are some tests that
I must correct more than one element. I takes me a loop.
So, TLE.

P. S. I don't understand your algo )
Can you mail me "_magistr.90@mail.ru" ?
We can speak Russian (or Ukrainian ;) )

UdSU: Ajtkulov, Kotegov, Saitov Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [4] // Problem 1494. Monobilliards 5 Nov 2006 11:16

It's just a stack modelling. You should suppose player not to be a cheater. Then he just puts balls into the pocket one by one: 1, 2, 3... until the last ball is the next ball to be checked. So, this ball should be removed. And so on. When the process is finished just check if the pocket is empty.

svr Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [3] // Problem 1494. Monobilliards 5 Nov 2006 12:13

Yes! And in my algoritnm xx[]- stac;
NN- it's capacity;

Alexey Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [2] // Problem 1494. Monobilliards 5 Nov 2006 15:12

ANW, TLE#14 (((

Olzhas2dy Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [1] // Problem 1494. Monobilliards 30 Jun 2007 16:05

For everyone who has TLE, use priority_queue. It is probably not the best solution, but it takes up only few lines.

Dusan Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) // Problem 1494. Monobilliards 13 May 2008 03:50

can you give me link where I can find algo or code for priority_queue?

Neizvestnii Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) // Problem 1494. Monobilliards 30 Jun 2007 18:28

to svr: I don't know 2 things in you algoritm:
->m1=xx[k1]- next ball after timeout
What is k1?
->If (m1<=m) -"Cheater"//meet number smallet than taken
What is m?

Please help me

Брэнд O(n^2) // Problem 1494. Monobilliards 21 Mar 2008 19:28

O(N^2) works! Time - 0.984 seconds)))

Edited by author 21.03.2008 19:29

Discussion of Problem 1494. Monobilliards