Обсуждение @ 1579. Транспортировка шуб @ Timus Online Judge

Alias (Alexander Prudaev) TLE 21 NlogN, NsqrtN [21] // Задача 1579. Транспортировка шуб 13 окт 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] // Задача 1579. Транспортировка шуб 14 окт 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] // Задача 1579. Транспортировка шуб 14 окт 2007 00:28

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

Lomir Re: TLE 21 NlogN, NsqrtN [10] // Задача 1579. Транспортировка шуб 14 окт 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] // Задача 1579. Транспортировка шуб 14 окт 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] // Задача 1579. Транспортировка шуб 14 окт 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] // Задача 1579. Транспортировка шуб 14 окт 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] // Задача 1579. Транспортировка шуб 14 окт 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] // Задача 1579. Транспортировка шуб 14 окт 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] // Задача 1579. Транспортировка шуб 15 окт 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] // Задача 1579. Транспортировка шуб 15 окт 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] // Задача 1579. Транспортировка шуб 16 окт 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] // Задача 1579. Транспортировка шуб 17 окт 2007 01:26

O(4N) is possible

[SPbSU ITMO] Dennis Yolkin Re: Now AC 0.203 // Задача 1579. Транспортировка шуб 22 окт 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 (-) // Задача 1579. Транспортировка шуб 15 окт 2007 13:45

Thunder Re: TLE 21 NlogN, NsqrtN [6] // Задача 1579. Транспортировка шуб 22 окт 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] // Задача 1579. Транспортировка шуб 24 окт 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] // Задача 1579. Транспортировка шуб 30 апр 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] // Задача 1579. Транспортировка шуб 22 июл 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] // Задача 1579. Транспортировка шуб 22 июл 2008 13:12

O(N) - AC in 0.109 sec

Hanzbrow (TNU) KCC NlogN AC [1] // Задача 1579. Транспортировка шуб 31 окт 2009 13:59

O(N*logN) AC 0.234

Kolyanich Re: NlogN AC // Задача 1579. Транспортировка шуб 5 июл 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

Обсуждение задачи 1579. Транспортировка шуб