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łą :)

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.

W SZE przekleiłem Dinica z zespołowej biblioteczki ACM-owej. Teoretycznie worst-case w tym zadaniu to O(n^4), ale na wszystkich testach mam 0.00s.

A w Pokryciach można było nie ogarnąć, jak przyspieszyć standardowy dynamik (sploty, FFT i takie tam) i optymalizować sześciana na wszystkie sposoby. Da się go wcisnąć pomimo odstraszających limitów. :)

Autora drugiego kodu dostającego dyszkę za Pokrycia proszę o opisanie optymalizacji użytej w rozwiązaniu. Wydaje się być warta przedstawienia szerszemu gronu.

Moje rozwiązanie dostało 9, mogę w skrócie napisać czym się różniło.

Załóżmy najpierw n = 2^m. Tak jak we wzorcówce wybieramy dwa wierzchołki, i możemy ograniczyć się do grafów w których te wierzchołki są "takie same". Łączymy je w grupę rozmiaru 2, i zapamiętujemy czy zdecydowaliśmy się dać między nimi krawędź czy nie. Wybieramy kolejne dwa, robimy to samo, i tak dalej. Potem wybieramy dwie grupki dwuwierzchołkowe, i podobnie stwierdzamy że muszą one wyglądać tak samo, w szczególności w obu musieliśmy podjąć tą samą decyzję o dodaniu krawędzi bądź nie. Postępując tak dalej ograniczymy się do grafów o bardzo prostej strukturze - nasz graf rozmiaru 2^m będzie składał się z dwóch identycznych grafów rozmiaru 2^(m-1), a pomiędzy tymi grafami albo wszędzie są krawędzie, albo nie ma żadnych. Łatwo zauważyć że takie grafy będą mieć minimalne pokrycie rozmiaru 2^m - 2^l dla pewnego l, przy czym parzystość liczby grafów o takim pokryciu będzie taka jak parzystość (m po l). Dla n = 2^m mamy więc trywialne rozwiązanie.

W ogólnym przypadku rozkładamy n na sumę potęg dwójki (niech będzie ich t) i ograniczamy się do grafów w których wierzchołḱi są w t grupkach takich jak opisałem wyżej. Wiemy że każda grupa ma kilka możliwych typów, generujemy wszystkie kombinacje, bierzemy te które wystąpiły nieparzystą liczbę razy, i dalej rozumujemy tak jak we wzorcówce - mamy pewne multizbiory, jeśli któryś tworzy zbiór to znamy rozwiązanie, a w przeciwnym przypadku rozgałęziamy się na dwa sposoby. Ja nie robię tego w formie dynamika, tylko równoważnie zamiatając "w przód" - wyciągam multizbiór który jeszcze nie jest zbiorem, wrzucam obie powstałe z niego możliwości do zbioru do rozpatrzenia, przy czym jeśli wrzucam coś drugi raz, to usuwam. Tak do momentu, gdy zostaną nam same zbiory.

To rozwiązanie działa przy ustalonym n, i "spycha" te multizbiory, aż zostaną same zbiory. Gdy przetwarzam większe n, to sprawdzam czy rozwiązałem już problem dla innego n będącego jego podzbiorem (w sensie potęg dwójki w rozkładzie) - jeśli tak, to używam tamtego rozwiązania jako punktu startowego, "doklejając" do każdego zbioru to czego brakuje (patrząc na bity w n które dokładam), i spycham znowu, od tego miejsca.

@Tomek: Bilard w O(n^3)? I do tego jeszcze taki, który wszedł :D? Ciekawe. Wiem o istnieniu 3 rozwiązań (swoje, Soko i z omówienia) i wszystkie trzy są istotnie różne i wszystkie działają w O(n). Jak chciałbyś opisać ideę, to chęnie przeczytam, ale bez wchodzenia w szczegóły, bo byłoby to to pewnie bolesne i dla Ciebie i dla czytających :P.

Ja dzieliłem sobie tor lotu piłki na ~12 przypadków, na których bieg zachowywał się tak jak bieg na jakiejś mniejszej krzywej modulo pionowe złączenie wewnętrzne i zewnętrze, gdzie trzeba było jeszcze dopisać proste ify. Czasy, w których zaczynały się dane odcinki toru brałem z bruta dla małych wartości n i zgadywałem zależności, które je dawały dla większych n.

W sumie wymagało to ode mnie a) napisania bruta (~1h), b) głupiego gapienia się w krzywą rzędu 5 i 6 z Wikipedii przez 3 bite godziny, c) kodzenia wszystkich przypadków, wyciągania zależności itd, oczywiście także co chwila spoglądania na krzywą (~5-6h) i wyszedł mi z tego chyba najbardziej absurdalny kod jaki w życiu napisałem.

Bilard robię tak:

1. Liczę dla każdego n, kiedy dojadę do każdego rogu. Przy czym liczę czas na 3 sposoby: zegarek włączony cały czas, zegarek włączony tylko po parzystych odbiciach od brzegu, zegarek włączony po nieparzystych odbiciach od brzegu.

2. Funkcja BorderHit, która dla danego n,k liczy czas do k-tego odbicia od brzegu. Znowu liczy czas na jeden z trzech sposobów. Ta funkcja działa w O(n).

3. Główna rekurencyjna funkcja, która rozwiązuje podane zadanie. Najpierw, używając obliczonych czasów dla rogów znajduję, wzdłuż którego z 16 segmentów długości połowy boku będę jechał w danym momencie. Przy czym czas przejazdu przez segment w środku liczę jako sumę dwóch czasów: po jednej stronie czas spędzam po parzystych przejazdach, po drugiej po nieparzystych.

Jeśli ten segment jest jednym z ośmiu na brzegu kwadratu, to wywołuję się rekurencyjnie.

Jeśli jest jednym z ośmiu w środku, które jadą pomiędzy dwoma mniejszymi kwadratami, to wtedy wyszukuję binarnie, ile razy przechodzę przez linię środkową, używając funkcji BorderHit. Czas spędzony po jednej stronie jest po parzystych przejazdach, a po drugiej stronie po nieparzystych. n wywołań funkcji O(n), czyli ten krok jest O(n^2).

Jak już się dowiem, ile razy przechodzę przez linię środkową, to wtedy wywołuję znowu całą funkcję rekurencyjnie po odpowiedniej stronie, odpowiednio poprawiając pozostały czas jazdy na taki, jaki byłby gdybym odbijał się tylko po tej stronie (znowu funkcja BorderHit).

Razem: O(n^3).

Pomogłem sobie tablicując najpierw wartości funkcji BorderHit dla n<=16, co kilkukrotnie przyspiesza. Przechodzi ostatni test w 1.24/2.00.

Odnośnie pokrycia, zacznę od wersji która przyszła mi do głowy dopiero dzisiaj :)

Nasza kluczowa tablica DP2 chce dla każdego początkowego multizbioru/ciągu n jedynek {1,1,1,...,1} i właściwego zbioru wag (np. {8,2,1}) przechować liczbę sposobów (mod 2) na ile jesteśmy w stanie przeredukować {1,1,1,...,1} w {8,2,1}. Dla ustalenia uwagi, jeśli nasze redukcje będą brać pierwszą parę równych wag z lewej, to każdy ciąg redukcji dla n jedynek sprowadza się do redukcji pierwszych n-1 jedynek aż dojdziemy do właściwego zbioru, dołożenia ostatniej jedynki i redukowania dalej. Możemy więc przeiterować po wszystkich zbiorach "nieparzyście wiele razy otrzymanych" z n-1 jedynek, dla każdego z nich dołożyć jedynkę i dopisać do DP2 wszystkie właściwe zbiory otrzymane z tego nowego multizbioru.

Ale wszystkie zbiory "nieparzyście otrzymane" z n-1 jedynek możemy wziąć z DP2[n-1] :) Dla każdego z nich (np. {8,2,1}), multizbiór po dołożeniu ostatniej jedynki ({8,2,1,1}) może "nieparzyście zredukować się" do co najwyżej log n zbiorów ({8,2,1}, {8,2}, {8,4}), co daje zgrubne O(n log n) na obliczenie rzędu DP2[n] z rzędu DP2[n-1]. Ale po przyjrzeniu się bitom [1], okazuje się że tak naprawdę jest to O(n), i wypełnienie całej tablicy DP2[n][n] zajmie O(n^2) czasu z małą stałą. Cały kod: http://pastebin.com/wtxhLesW

Na zapytania można odpowiadać w czasie log n jak w opracowaniu (i kodzie powyżej), albo [EDIT: zignorujcie, bez przygotowania też amortyzuje się do O(1)/zapytanie jeśli pytamy o wszystkie możliwe k dla zadanego N] całkiem zbić złożoność przygotowując odpowiedzi offline, korzystając z [1] - to daje całkowity czas O(n^2 + Q).

Moje zasubmitowane rozwiązanie ma przy ograniczeniach z zadania pesymistyczną złożoność o chyba jeden log więcej, ale pozwalało na obliczenie pojedynczego rzędu DP2 (włącznie z wykorzystywanymi rzędami) w czasie O(n log n). Korzystało z obserwacji przedstawionej przez Krzysztofa - jako startowe multizbiory dla n=13 nie rozpatrywałem 13 jedynek ({1,1,....1}), tylko zbiory {a_1, a_4, a_8}, gdzie a_8 jest pojedynczym wierzchołkiem, który możemy "nieparzyście otrzymać" z grupki ośmiu jedynek itd. Ponownie, wszystkie nieparzyście otrzymane zbiory ze wszystkich {a_1, a_4}, to dokładnie DP2[5]. Tym razem zamiast dokładania jednej jedynki, musimy rozpatrzeć wszystkie potencjalne a_8, stąd dodatkowy log.

Zdecydowanie jedno z moich ulubionych zadań :)

[1] Tylko co druga liczba ma na końcu jedynkę, tylko co czwarta ma dwie, itd.

Jak robi się grzyby po deszczu?
Omówienie oglądałem, ale... "no to teraz piszemy jakieś BST i już działa". To chyba była największa trudność tego zadania. Czy mógłby ktoś przybliżyć swoją ideę?

Dodam tylko od siebie, że zadanie SZE znałem ze szkoły. Jakby kogoś interesowały takie problemy to w różnych wariantach (rodzaj dostępnych maszyn; podzielność, zależność zadań; funkcja kosztu) są opisane w książce Scheduling Algorithms Bruckera.

A ja szukałem z ciekawości SZE w Scheduling Zoo (http://schedulingzoo.lip6.fr/), ale nie znalazłem :)