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)

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

Ehh te cholerne probabilistyczne rozwiązania.

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.

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.

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.

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).

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

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.

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

Ciekawe czy był test ubijający random_shuffle bez seedowania xD nie chce mi sie testować ale może ktoś został w ten sposób ubity i sie przyzna

@Marek Sommer, chciałbyś może powiedzieć coś więcej o konstrukcji tej sieci przepływowej?

@Franciszek Witt – ja miałem random_shuffle bez seedowania i przeszło

Załóżmy, że mamy k dzieci, a w i-tym z nich mamy 4 wartości [zero_i, jeden_i, dwa_i, trzy_i] z dynamika. Na początku wybieramy dla każdego z dzieci tę z czterech wartości, która jest największa. Czyli np. dla i-tego dziecka wybierzemy dwa_i, bo akurat dwa_i >= max(zero_i, jeden_i, trzy_i). W ten sposób dostaniemy pewną konfigurację, w której jest sumarycznie Z zer, J jedynek, D dwójek i T trójek. Co więcej, to jest optymalny wynik i nie da się uzyskać lepszego dla takiej konfiguracji liczb zer, jedynek, dwójek i trójek. Załóżmy teraz, że chcielibyśmy uzyskać konfigurację (Z', J', D', T') != (Z, J, D, T). To trzeba w niektórych dzieciach powybierać inne wartości, żeby to zrobić. No to robimy tak, że tworzymy 4 wierzchołki: W0, W1, W2 i W3, każdy odpowiadający jednej z czterech wartości. Tworzymy też źródło Ź i ujście U. No i jeśli załóżmy J' > J, to znaczy, że aktualnie mamy niedomiar jedynek, więc chcielibyśmy ich więcej. Zatem tworzymy krawędź z W1 do U o przepustowości J'-J. I analogicznie krawędź z W0 do U ma przepustowość max(0, Z' - Z), krawędź z W2 do U ma przepustowość max(0, D' - D), itd. Z kolei, jeśli J > J', to znaczy, że mamy nadmiar jedynek i chcemy się ich pozbyć. Więc tworzymy krawędź z Ź do W1 o przepustowości J-J'. I analogicznie z Ź do W3 tworzymy krawędź o przepustowości max(0, T - T'), itd. Wagi tych wszystkich krawędzi pomiędzy źródłem/ujściem a czymś to 0. Pozostaje jeszcze potworzyć krawędzie pomiędzy wierzchołkami W0, W1, W2 i W3. No to jeśli mieliśmy czwórkę [zero_i, jeden_i, dwa_i, trzy_i], w której załóżmy, że optymalną wartością było dwa_i, to możemy stworzyć przejściowy wierzchołek P_i i następujące krawędzie o przepustowości 1: A) Z W2 do P_i o wadze 0, B) z P_i do W0 o wadze zero_i-dwa_i, C) Z P_i do W1 o wadze jeden_i-dwa_i, D) Z P_i do W3 o wadze trzy_i-dwa_i. No i w takim grafie, jeśli znajdziemy maksymalny przepływ o maksymalnym koszcie, to koszt tego przepływu to będzie różnicą w kosztach pomiędzy optymalną wagą początkowej konfiguracji a optymalną wagą w konfiguracji docelowej. Problemem jest jeszcze to, że ten graf jest duży - ma 6+k wierzchołków oraz 4+4k krawędzi. To sprawia, że szukanie pojedynczej ścieżki powiększającej przepływ jest O(k), a takich ścieżek będziemy szukać potencjalnie aż O(k). Natomiast to co można zrobić, to podczas szukania pojedynczej ścieżki powiększającej udawać, że nie ma wierzchołków P_i, i np. zamiast ścieżki W2->P_i->W1 możemy zrobić bezpośrednią krawędź W2->W1 o wadze jeden_i-dwa_i. Wiemy, że dopóki szukamy tylko jednej ścieżki powiększającej, to z W2 do W1 przejdziemy co najwyżej raz, więc zamiast mieć O(k) krawędzi pomiędzy W2 i W1, to tworzymy tylko jedną krawędź - tę o największej wartości jeden_i-dwa_i. W ten sposób dostajemy graf, który ma 6 wierzchołków i O(6^2) krawędzi. I ten graf wystarcza do znalezienia jednej ścieżki powiększającej. Gdy taką ścieżkę znajdziemy, to musimy teraz zaktualizować krawędzie pomiędzy W2 i W1, bo największa wartość jeden_i-dwa_i mogła się zmienić (to robimy w O(log(k)) trzymając możliwe wagi na setach). No i tak szukamy pojedynczych ścieżek dopóki nie dojdziemy do pożądanej konfiguracji. I to była ogólna metoda jak w O(x * log(k) * O(6)) dojść z jednej konfiguracji do drugiej, gdzie x = |Z - Z'| + |J - J'| + |D - D'| + |T - T'|. To jest chyba w zasadzie to samo co opisał Wojtek, ale zamiast ręcznie rozważać przypadki, to się szuka ścieżek w grafie przepływowym.