ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1579. Coat Transportation

Alias (Alexander Prudaev) TLE 21 NlogN, NsqrtN [21] // Problem 1579. Coat Transportation 13 Oct 2007 23:42
i have write NlogN algo -  TLE  21
then i rewrite it in N*sqrt(N) - TLE 21
maybe something wrong with this test?
Lomir Re: TLE 21 NlogN, NsqrtN [13] // Problem 1579. Coat Transportation 14 Oct 2007 00:18
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.
Samsonov Alex [USU] Re: TLE 21 NlogN, NsqrtN [11] // Problem 1579. Coat Transportation 14 Oct 2007 00:28
The correct solution is O(N). Try to find it.
Lomir Re: TLE 21 NlogN, NsqrtN [10] // Problem 1579. Coat Transportation 14 Oct 2007 01:00
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
Alias (Alexander Prudaev) Re: TLE 21 NlogN, NsqrtN [9] // Problem 1579. Coat Transportation 14 Oct 2007 11:18
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
Alias (Alexander Prudaev) Now AC 0.203 [8] // Problem 1579. Coat Transportation 14 Oct 2007 12:02
when i use vector<vector<int>> it was TL
but if use vector<myvector>> i got Ac 0.203
it is strange...
Todor Tsonkov Re: Now AC 0.203 [7] // Problem 1579. Coat Transportation 14 Oct 2007 19:11
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 :(
Samsonov Alex [USU] Re: Now AC 0.203 [6] // Problem 1579. Coat Transportation 14 Oct 2007 19:14
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.
Alias (Alexander Prudaev) Re: Now AC 0.203 [5] // Problem 1579. Coat Transportation 14 Oct 2007 22:30
I understand you, there is an O(N) solution. but i cant see it
can we talk about in ICQ (my icq is 410673122)
AlexF [USTU Frogs] Re: Now AC 0.203 [4] // Problem 1579. Coat Transportation 15 Oct 2007 13:11
I have an O(n) solution but it works about 0.5 sec... Why?
Samsonov Alex [USU] Re: Now AC 0.203 [3] // Problem 1579. Coat Transportation 15 Oct 2007 15:11
Don't forget, that reading about 1MB of input also requires a lot of CPU time.
Lomir Re: Now AC 0.203 [2] // Problem 1579. Coat Transportation 16 Oct 2007 03:39
Now so fast, but AC with O(NlgN). Just used myvector as inner container and some optimization on function calls.

Really strange..
And IV Re: Now AC 0.203 [1] // Problem 1579. Coat Transportation 17 Oct 2007 01:26
O(4N) is possible
[SPbSU ITMO] Dennis Yolkin Re: Now AC 0.203 // Problem 1579. Coat Transportation 22 Oct 2007 02:41
I have Accepted for my solution, complexity O(n * log(n)) written in Java without any optimization with time 1.5 sec.
Vladimir Yakovlev (USU) New tests had been added immediately after contest (-) // Problem 1579. Coat Transportation 15 Oct 2007 13:45
Thunder Re: TLE 21 NlogN, NsqrtN [6] // Problem 1579. Coat Transportation 22 Oct 2007 02:50
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
Denis Re: TLE 21 NlogN, NsqrtN [5] // Problem 1579. Coat Transportation 24 Oct 2007 01:16
Maybe you mean solution using unintersectable sets? It's really fast and you don't have to use additional memory.
Carbon No subject [4] // Problem 1579. Coat Transportation 30 Apr 2008 18:02
My solution O(N) took 0.421 and 7 969 КБ because I used dinamic structures with pointers to next nodes. :)
Denis Koshman Re: No subject [3] // Problem 1579. Coat Transportation 22 Jul 2008 12:55
N*log(N) - 0.187 sec. Did not optimize anything, but stored amount for same-size coats.
Denis Koshman Re: No subject [2] // Problem 1579. Coat Transportation 22 Jul 2008 13:12
O(N) - AC in 0.109 sec
Hanzbrow (TNU) KCC NlogN AC [1] // Problem 1579. Coat Transportation 31 Oct 2009 13:59
O(N*logN) AC 0.234
Kolyanich Re: NlogN AC // Problem 1579. Coat Transportation 5 Jul 2011 13:04
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