Ja potwierdzam.

Macie paczkę ode mnie:
http://students.mimuw.edu.pl/~wn341489/boh_tests.zip
Te z sufiksem pos mają dawać odpowiedź TAK, a te z sufiksem neg mają dawać odpowiedź NIE.
Testy wydają mi się w miarę dobre. Testy z odpowiedzią TAK mają tę własność, że gdyby zmniejszyć o początkowego healtha o 1, to byłaby NIE i testy z NIE na odwrót. Ponadto, jeżeli jest NIE, to powód tego nie powinien być trywialny. A o ile się nie mylę, to dla zupełnie losowych testów zazwyczaj ten powód jest w stylu "nie mogę zabić żadnego potwora" itp - tu tak nie powinno być.
Ktoś potwierdza?

Nie - tylko pak20.in, co nie przeczy mojej wypowiedzi xD

Nie odnotowuję tego problemu. Może to dlatego, że *.mimuw.* ma u mnie "pełne prawa", w tym ciasteczka, skrypty i 'wszystko' inne.

Natomiast jeśli już wypowiadam się w takim wątku to pozwolę sobie zasugerować aby na stronie głównej Potyczek nowości były numerowane od jeden (lub zera) a nie od n (gdzie n nie jest stałą). Przez to, że nowa wiadomość ma zawsze numer jeden, nie można tylko rzucić okiem i zobaczyć, że coś nowego się pojawiło. Trzeba zawsze patrzeć na tytuł/treść, co jest uciążliwe. Jeśli każda wiadomość będzie miała swój, stały numer to problem zniknie.

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.

Sprawdziłeś wszystkie moje 20 testów na sprawdzaczce ?? O_o

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

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

NVM, faktycznie na grafie pełnym nie trza.

Jeśli można pokusić się o uwagę odnośnie strony, to byłoby wygodne dla użytkownika, gdyby po "expand message" znikał jej status jako nowej - ciągły monit o nowych wiadomościach burzy spokój. ;)

Jest tak i nie należy się sugerować time limitem, który jest przy uruchomieniu próbnym.
Btw - Wojtek, mi też nie wchodzą wszystkie testy Marcina na sprawdzaczce.

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

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

IN:
2 5
6 19
4 6

OUT:
TAK
2 1

Ja mam natomiast ~4.3s... A to nie jest tak, że limit czasu na uruchomienie próbne jest ustawiony odgórnie (na całym serwerze) na 5 sekund?

U mnie podobny czas na sprawdzarce ~3.6s. Pozdr.