@Maciek: Czyli jednak słabe testy. Dzięki

93

@Michał Włodarczyk

7 2
1 5 4
7 12 2
13 14 1
10 14 3
10 11 1
10 11 1
13 14 1

out:
NIE

Twój kod wypisuje TAK

To jest dlatego, że mi się udało rozwiązać to zadanie. Zawsze jest na PA tak, że jak piszę heurę, to testy są bardzo mocne i dużo punktów mi ubija. Mimo, że heura myli się 2-5 razy na 1k losowych testów, to w każdej grupie jest coś, żeby ją załatwić.

Jeśli natomiast uda mi się rozwiązać zadanie, to oczywiście testy będą na tyle słabe, żeby heurystyki innych zawodników miały szansę wyrównać mój wynik :P

Ty masz szansę się dostać do finału. W zeszłym roku ja źle rozpatrywałem przypadek z wiodącymi 0 na wejściu w zadaniu 2A FIB i to mnie kosztowało awans, gdyż w każdej grupie pojawił się taki przypadek i 0/10. Takie jest życie - poczekaj do ostatecznych wyników z rozpaczaniem.

Ja wysłałem (oprócz dobrego rozwiązania) także heurę opisaną przez Adama (ale idącą od początku) i ona dostaje 0 punktów (w każdej grupie uwala ją test e). Byłem dość zadowolony, że rozwiązanie, które przechodzi wszystkie testy z forum oprócz mojego dostaje 0 ;)

Zadaje rzeczywiście wydaje się heurogenne...

109

W omówieniu SZE jest mowa o algorytmie Edmondsa-Karpa do liczenia przepływu, O(n^5).

Lepiej zastosować algorytm przedprzepływowy (push-relabel), O(n^3). Jest ładnie opisany w książce Wprowadzenie do Algorytmów Cormena, i równie prosty w implementacji jak Edmonds-Karp.

CNF-SAT zrobiłem tak:

Wartościowanie zmiennych traktuję jako n-literowe słowo, gdzie literami są wszystkie możliwe literały (x1, ~x1, x2, ~x2, itd), czyli pierwsza litera to x1 albo ~x1, itd.

Trzeba zliczyć słowa, które nie zawierają żadnego z podanych podsłów.

Tworzę więc po prostu automat skończony szukający tych podsłów, algorytmem Aho-Corasick.

I teraz dla każdej pary (liczba przetworzonych liter, wierzchołek automatu) liczę dynamicznie liczbę możliwych sufiksów. Takich osiągalnych stanów jest tylko O(n), bo dla każdego wierzchołka automatu oprócz korzenia jest tylko jedna możliwa pozycja.

---

W bilardzie Hilberta zrobiłem algorytm O(n^3) zamiast ładnego O(n) jak w omówieniu. Ale zmieścił się w czasie, dobrze, że zoptymalizowałem trochę stałą :)

Ja mam maksa za to http://pastebin.com/7WbpL5r1 (n^3) co wydaje się śmieszne w porównaniu z wzorcówką. Nie wiem, czy to działa, czy słabe testy, może komuś się nudzi bez nowych zadań i spróbuje udowodnić poprawność?

96

Prosta heura przechodzi oficjalne testy ;)

Ja niestety nie zdążyłem się zorientować, że naklepałem heurę, ale po odwróceniu przedziałów na wejściu akurat by przeszła. Pewnie sporo osób będzie mieć maksy za coś takiego:

http://pastebin.com/crqNjGhu

To jest przeglądanie przedziałów od lewej do prawej i wykonywanie zachłannie tych zadań, które najwcześniej trzeba zacząć robić, żeby mieć szansę zdążyć je zrobić (priorytet po k_i-c_i).
(ale trzeba odwrotnie: przeglądać od końca i wtedy nieszczęśliwie jest accept)

@Świstak sam koniec ścieżki (ten punkt to był (0, 1), a nie (1, 0), jak mój program wypluwał). On nie jest w ogóle wykorzystywany w rekurencji, a ponieważ (0, 1) wygląda podobnie do (1, 0), to nie zauważyłem tego sprawdzając ręcznie ścieżki dla 1 i 2

90

103
@Mariusz: Btw, co niby jest przypadkiem brzegowymw bilardzie? Ja przynajmniej robiłem jakąś gunworekurencję i jakbym nie rozpatrzył jakiegokolwiek przypadku, to bym miał prawie wszystko źle, bo by pewnie wiele punktów z krzywej wyższego rzędu się sprowadzało do tego z mniejszej. Ale z drugiej strony potwierdzałeś testy Marka, więc pewnie coś innego masz na myśli (może małe n?).