|
|
back to boardi 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 O(N*logN) AC 0.234 Brilliant problem! Solved in O(N) with 3 lines of creating chains and bit more lines for printing results. Fist tried to solve it as 1533 (Fat Hobbits), but it is much easier |
|
|