ok boomer

Z przyjemnością potwierdzam :)

Nie wiem jak Ci się udało stworzyć taką paczkę, ale mój zupełnie niedziałający program ją całą przeszedł. Polecam na niej nie polegać

Ja tak samo losowo wymieszałem, w razie czego kryptograficznym generatorem liczb pseudo-losowych bo nigdy nie wiadomo czy organizatorzy czegoś nie kombinują.

Mnie wyszło 18 przypadków na naprawianie parzystości i każdy wydawał się ważny... Szkoda, że klepałem aż do północy (ostatni submit 2 min przed końcem) z czego ostatnia godzina to niepotrzebne żyłowanie, bo się okazuje że mój komp to ziemniak i chodzi z 8 razy wolniej od systemu (w końcu miałem < 1s czas, a myślałem że będzie ciasno). Podziwiam probabilistyczne rozwiązanie, bo by mi wiele czasu zaoszczędziło i jeszcze się nie spotkałem z takim zastosowaniem w dp optymalizacyjnym.

No nawet fajny pomysł z tym probabilem. Ja mam deterministyczne O(n log n), ale to jest ból, pot, umieranie, krew i łzy i w zasadzie to nawet nie mam przekonującego mnie dowodu, że działa, więc nie za bardzo chcę wchodzić w detale, ale skrótowo mogę opisać.
Gdyby nie było dwójek (izomorficzne do tego gdyby szukane ścieżki w zadaniu miały mieć długość 3, a nie 4), to wtedy mogę dla każdego kolejnego k wyznaczać najlepsze rozwiązanie zawierające dokładnie k jedynek i k trójek. Kluczowa obserwacja taka, że rozwiązanie dla k oraz k+1 różnią się stałą liczbą elementów (albo zamieniamy 0->1 i 0->3 albo 1->3, 0->1, 0->1 albo 3->1, 0->3, 0->3) i mając odpowiednie sety da się to utrzymywać.
Jak wchodzą nam dwójki, to trochę umieranie z tymi kejsami. Ogólnie to tak jakby startowo każdemu typowi daję lepszą z opcji 0 i 2 i chcę rosnąc z liczbami 1 i 3 jak w poprzednim rozwiązaniu. Analogicznie jak w kejsie bez dwójek wyznaczam każde najlepsze rozwiązanie dla tych coraz większych wartości k olewając warunek, że dwójek ma być parzyście. Jeżeli przypadkiem dla ustalonego k liczba dwójek wśród tych elementów co są 0 lub 2, jest parzysta, to jestem happy i uznaję to za kandydata na odpowiedź. Jak nie, to wtedy próbuję to naprawić jakimiś zmianami. I znowu okazuje się, że wystarczy rozważyć zmianę tylko stałej liczby elementów, ale tym razem wychodzą nie 3 przypadki, a 10... Aczkolwiek dowodu nie mam. A, i tych operacji na setach wykonuję serio dużo. Przez co O(n log n) dla n<=200000 zajęło mi ... 7.65s

Dla ciekawskich kod: https://ideone.com/UxSZ4L Chyba napisany w miarę ok, aczkolwiek brzydota rozwiązania powoduje brzydotę kodu

Mi się wydaję, że mam ładne O(n*log(n)). Kluczem jest obserwacja, że dla zadanej parzystości dwójek, wykres wartości pamiętanych dla kolejnych różnic jedynek i trójek jest prawie wypukły. Jak mamy dwa takie wykresy, to można je łączyć liniowo (tzn. max-plus konwolucja idzie liniowo wtedy).

Ja zrobiłem w O(n * log(n)) deterministycznie. Mam podobny dp, że dla każdego poddrzewa liczę 4 wartości dla każdej długości ścieżki od 0 do 3. Natomiast łączenie robię w taki sposób, że iteruję się po każdej możliwej konfiguracji (liczba jedynek, liczba trójek, parzystość dwójek), gdzie |liczba jedynek - liczba trójek| <= 1. Znajduję optymalny wynik dla każdej z tych konfiguracji. Taki wynik można znaleźć przy pomocy max-cost max-flowa na grafie w którym są 4 główne wierzchołki (oprócz źródła i ujścia). Przepustowości krawędzi wymuszają liczności zdefiniowane przez konfigurację, a każda czwórka wartości z poddrzewa definiuje pewne koszty przejścia między tymi wierzchołkami. No i da się szukać w tym grafie ścieżek powiększających w czasie O(log(n)) i przechodzić szybko pomiędzy konfiguracjami znajdując O(różnica między konfiguracjami) ścieżek powiększających.

Bardzo fajne rozwiązanie probabilistyczne, ale chętnie bym poznał deterministyczne.

BTW Mi dla stałej 200 dało 5/10, na szczęście zrobiłem wersję 1200 i 1600, oba dały 10/10.

Umiemy rozwiązać w O(n*log(n)), które nie jest specjalnie ładne, dlatego chcieliśmy oczekiwać od was właśnie takiego rozwiązania, które wydaje nam się dużo ciekawsze.

Ehh te cholerne probabilistyczne rozwiązania.

Ja robiłem tak samo ze stałą 1250. Tutaj jest blog na cf z analizą probabilistyczną dlaczego to działa: https://codeforces.com/blog/entry/50036

Dp po poddrzewach, maxymalny wynik taki, że w całym poddrzewie wszystkie ścieżki są dokończone poza być może jedną ścieżką zwisającą długości k (drugi parametr dpka), jak robię przejścia to chcę pamiętać optymalny wynik dla każdego prefiksu, parzystości liczby dwójek oraz różnicy liczb jedynek i trójek, tak po prostu byłoby n^2, to rozpatruję dzieci w losowej kolejności i praktycznie na pewno rozwiązanie optymalne wymieszałem tak, że różnica jedynek i trójek nie przekroczy stałej rzędu pierwiastka (w moim rozwie 700), więc dp liczę tylko dla bilansu nie przekraczającego co do modułu 700 dostając złożoność n * sqrt(n)

Jak się tak stanie, to odpowiem to samo co fanatyk wędkarstwa na wieść o tym, że Zbysio spadł z rowerka

Potwierdzam