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

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?

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)

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 ;) )

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.

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

ANW, TLE#14 (((

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

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) works! Time - 0.984 seconds)))

Edited by author 21.03.2008 19:29

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