Czy ktoś byłby tak miły i opisał rozwiązanie do zadania Kuglarz?

Omówienie zostało zamieszczone na https://www.facebook.com/potyczki .

Czy wzorcówka zakłada algorytm Prima z użyciem kopca Fibonacciego?

NVM, faktycznie na grafie pełnym nie trza.

Kurczę, jakoś nie wpadłem na to że algorytm Prima łatwo da O(n^2) i z przyzwyczajenia wklepałem Kruskala ( O(n^2 log n) ). Ciekawe czy coś uwali (i czy dużo :P)

// edycja: nie uwaliło nic :D

Nieco inne podejście, algebraiczne nieco.
http://pastebin.com/B0vTLEMz
Startuję z pustą 'bazą', w pętli biorę najtańsze nieużyte połączenie i sprawdzam, czy jest liniowo niezależne od bazy. Jeśli jest, dorzucam do bazy. Przerywam, gdy baza liczy n "wektorów".
Wektor trzymany jest jako odcinek. W bazie każdy odcinek zaczyna się w innym punkcie. Dostając nowy odcinek, jeśli zaczyna się w tym samy miejscu co odcinek bazy, redukuję go zastępując różnicą. Jeśli zbije się do zera, był liniowo zależny. Pesymistycznie będą musiał sprawdzić wszytkie n^2/2 wektorów a redukcja może potrwać nawet O(n) (złośliwy przypadek, podany już na forum https://www.dropbox.com/s/c3njiipmwfu12cr/kug.tar.gz). Więc O(n^3).
Do tego heurystyka modyfikująca bazę doklejając lub skracając bazowe odcinki, tak, aby średnio ucinały połowę. To daje O(n^2 log (n)) przy założeniu, ze dane zrobiły dobrze heurystytce.
Sekundowe testy przechodziły <0.21, najgorszy trzysekundowy w 0.96.
Co ciekawe, bez heurystyki najgorszy wynik to 1.15s. W warunkach domowych spreparowany przeciwko temu algorytmowi przypadek liczył się 7 razy dłużej niż losowe (forumowe) duże testy.

Edit: W sumie to Kruskal z kiepskim sprawdzaniem, czy klastry są połączone.

@Bartłomiej Szczygieł I działało Ci to? Bo też zrobiłem podobnie, że bralem eliminacją Gaussa n najtańszych liniowo niezależnych wektorów, ale nie przechodziło większych testów:/ A wybieranie najtańszej bazy w Z_2 klepałem na studiach na sprawdzarkę więc jest duże prawdopodobieństwo, że nie mam błędu w algorytmie..

Tak, działa poniżej 1/3 limitów.
Też myślałem o wrzuceniu tego w macierz i schodkowaniu, ale uznałem, że będzie to za wolne. Jeśli mam "zeschodkowaną" macierz zredukowanie nowego wektora trwać może nawet O(n^2). Sprowadzenie rozwiązanej części do macierzy jednostkowej też nie pomaga, bo pozostała cześć nadal może być wypełniona:
1 0 0 0 1 0 1 0 1 0 1 0 1
0 1 0 0 0 1 0 0 1 1 0 0 1
0 0 1 0 0 0 1 1 0 0 1 1 0
0 0 0 1 0 0 1 0 0 1 0 1 0
Dostajemy kolejny wektor, tzn belkę postaci 011111000000. Wiemy, że (w tym wypadku) należy odjąć od niego wektor bazowy 2,3,i 4, średnio O(k) k wektorów w bazie. Co może oznaczać nawet O((n-k)k) operacji na elementach macierzy.

W wersji którą napisałem baza utrzymywana jest zawsze w takiej samej postaci jak wektory, które dostajemy, czyli jedynki tworzą spójny obszar i opisujemy je tylko dwoma liczbami.
Schodkowa postać macierzy wygląda w ten sposób, że mam tablicę konce[i], której elementy, jeśli nie zerowe, mówią, że w bazie mam wektor wypełniony jedynkami od i do konce[i] włącznie (schodkowa postać oznacza m.in , że w jednym 'i' zaczyna się tylko jeden wektor).
Redukcja nowego wektora do postaci schodkowej zajmuje tu pesymistycznie O(n), czyli znacznie lepiej niż w wersji macierzowej. Jeśli wszystkie elementy bazy są postaci i--i to redukcja nowej belki o długości k (średnio n) rzeczywiście trwa k ruchów. Jednak średnio jest lepiej, bo jednym jednym ruchem zmniejszamy nową belkę o więcej niż jedno oczko.
Heurystyka stara się tak modyfikować bazę, aby elementy bazy wyglądały tak: i--((i+n)/2), tym samym dowolna redukcja zajmowała O(log n). Wyniki czasowe sugerują, że dla losowych danych taki efekt i złożoność uzyskujemy też bez niej.

Mnie też nie udało się wpaść na rozwiązanie z grafem :)

Szukam najtańszej bazy przestrzeni Z_2^n, tak jak wyżej piszecie. Pierwszy brut to Gauss, O(n^5). Potem zacząłem trzymać zbiór wektorów taki, że żadne dwa nie zaczynają się w jednym punkcie - to daje chyba O(n^3), w każdym razie przechodzi już testy (chociaż ja miałem taki test, że działało u mnie w 4s). Ale można zrobić jeszcze tak, że również żadne dwa nie kończą się w jednym punkcie. Wtedy można pokazać, że nowy wektor jest liniowo zależny od tego "kanonicznego zbioru wektorów" tylko wtedy, jeśli jest sumą kilku rozłącznych elementów tego zbioru (tzn. np. [3,7] = [3,5] + [6,6] + [7,7]). A to można sprawdzać w O(1) jak się zrobi prostą strukturę, której wyliczenie zajmuje O(n), więc można ją przeliczać po każdym wstawieniu wektora. Łącznie mamy O(sort + n^2) ;)

TL;DR: przekombinowałem

Inna interpretacja, która sprowadza się do MST z użyciem Prima:

(1) Zauważamy, że do rozwiązania należy najtańszy z przedziałów postaci [1,x]. Dodajemy go do rozwiązania.

(2) Zauważamy, że znając [1,x] poznanie [1,y] jest równoważne poznaniu:
(a) [y+1,x] dla y<x, bo [1,y]^[y+1,x] = [1,x]
(b) [x+1,y] dla y>x bo [1,x]^[x+1,y] = [1,y]

Jeśli któryś z przedziałów [1,y] jest tańszy niż równoważny mu przedział, to ustawiamy równoważnemu cenę równą cenie [1,y].

(3) Rozwiązujemy problem dla kubków od 2 do N wracając do punktu (1).