i have write NlogN algo -  TLE  21
then i rewrite it in N*sqrt(N) - TLE 21
maybe something wrong with this test?

Strange....
My solution which got AC in contest gets TLE 21 too.
Besides my solution is O(n log k)
Where k is number of "run" in the market.

The correct solution is O(N). Try to find it.

ln N is just 17
Less then 2 million iterations. O(n lg n) also should pass TLE.
Why my O(n lg n) solution passed during contest?

Edited by author 16.10.2007 03:39

maybe you are right and there is O(n) solution
but my NlogN and NsqrtN should pass any test with n <= 100000
so i think this file is empty
and i got TL when read as scanf("%d", &n);

Edited by author 14.10.2007 11:29

when i use vector<vector<int>> it was TL
but if use vector<myvector>> i got Ac 0.203
it is strange...

At the contest I was a bit lucky to make a solution O(n*m) where m is the number of groups and it passed... My first solution was n*log(n ) but it was TL :(

This problem can be solved using 1 array of integers and a few variables in O(n) time (one "for" loop, actually). Try to find it, it is more interesting than optimizing your obvious N*logN solutions.

I understand you, there is an O(N) solution. but i cant see it
can we talk about in ICQ (my icq is 410673122)

I have an O(n) solution but it works about 0.5 sec... Why?

Don't forget, that reading about 1MB of input also requires a lot of CPU time.

Now so fast, but AC with O(NlgN). Just used myvector as inner container and some optimization on function calls.

Really strange..

O(4N) is possible

I have Accepted for my solution, complexity O(n * log(n)) written in Java without any optimization with time 1.5 sec.

Mates! I finded O(N) solutions in my 16 years! So use your brain and find it too!

P.S. 0.093 sec, but 2 592 КБ memory...

Edited by author 22.10.2007 02:55

Maybe you mean solution using unintersectable sets? It's really fast and you don't have to use additional memory.

My solution O(N) took 0.421 and 7 969 КБ because I used dinamic structures with pointers to next nodes. :)

N*log(N) - 0.187 sec. Did not optimize anything, but stored amount for same-size coats.

O(N) - AC in 0.109 sec