Nie no... to ja mam O(q n)... zupełnie inny algorytm.

Wojtek, wyszukałeś w internecie, znałeś, sam wymyśliłeś, czy coś brałeś i Ci się przyśniły te gammoidy?

Ciekawi mnie że porównywaliście z brutem - mi się wydaje że sam brut byłby mocno upierdliwy i przeraźliwie wolny (sprawdzanie wszystkich ciągów operacji kolorowań?), czy może istnieje jakiś prostszy, bardziej rozsądny brut?

A zadanie zdecydowanie było o wiele trudniejsze niż jakiekolwiek inne z dywizji C - żadne inne w tej dywizji nie zatrzymało mnie na dłużej niż 20 minut, tego nie wymyśliłem po pół dnia po czym odpuściłem sobie resztę rundy :P

Ja mam brute-force O(n^2). Liczę na to, że wejdzie, bo działało w 39.5 sekundy.

W ogóle czy tylko dla mnie to zadanie było mocno trudne jak na C? Według mnie wymyślenie rozwiązania z dowodem było trudniejsze niż rozkminienie 1B-4B razem wziętych.

Ja po prostu znalazłem algorytm, który to robi, ale to jest całkiem niezła przypadkologia.
Idzie to mniej więcej tak:
1) Jeżeli mamy graf gwiazdę (jeden wierzchołek stopnia n-1 i n-1 liści) to możemy otrzymać prosto dowolną konfigurację inną niż dwukolorowanie.
2) Jeżeli mamy wierzchołek stopnia >= 3 i w dwóch jego sąsiadach mamy dwa różne kolory, to przy ich pomocy możemy dobrze pomalować wszystkie pozostałe poddrzewa idąc od liści w górę
3) Potem możemy przenieść te dwa kolory do innych sąsiadów i pomalować dwa ostatnie poddrzewa
4) Zostaje nam gwiazda dookoła tego wierzchołka do poprawienia. Jeżeli docelowa konfiguracja na tej gwieździe to nie jest dwukolorowanie to możemy to zrobić.
5) W przeciwnym wypadku znajdujemy najbliżej znajdującą się parę sąsiadów tego samego koloru i ograniczamy się do naszej gwiazdy + ścieżki do tej pary
6) To też da się dowolnie pokolorować "przepychając" tę sąsiednią parę w górę, poprawiając gwiazdę, a potem cofając tę parę z powrotem na dół

Pewnie ktoś chciałby się dowiedzieć, więc napiszę. Słowa klucz to "liniowa reprezentacja gammoidu" xd.
Tzn. robimy coś takiego. Bierzemy sobie liczbę pierwszą P i dla każdej krawędzi losujemy liczbę od 1 do P-1. Następnie dla każdego wierzchołka v i dla każdego źródła 1<=z<=k wyznaczamy sumę iloczynów wartości na krawędziach po wszystkich ścieżkach od z do v (łatwo policzyć dynamikiem po DAGu). Dla każdego v otrzymujemy zatem wektor długości k (tzn te k wartości dla kolejnych źródeł). Kluczowe stwierdzenie jest takie, że przepływ wierzchołkowy ze źródeł do zbioru wierzchołków to rząd macierzy wektorów odpowiadających wierzchołkom z tego zbioru (łatwo się o tym przekonać w jedną stronę, bo jak istnieje małe cięcie wierzchołkowe, to łatwo widać, że ten rząd nie może być większy niż to cięcie, a w drugą nie wiem, ale są papery co tak twierdzą).
No to to jest klucz zadania, a zabawy z wektorami opisywać nie będę, bo obstawiam, że to ta pierwsza część zadania była bardziej zaporowa :P. Udało mi się osiągnąć O(mk+nk^3), ale to balansuje na granicy TL (wcześniej miałem O(mk+nk^2 log n + nk^3), ale na szczęście część z nk^2 log n udało mi się przyspieszyć do nk^2)

Ja dowodziłem tak: bierzemy trzy niewspółścieżkowe liście, na jednym będziemy "przechowywać" czarny, na drugim czerwony, a trzeci będzie "buforem". Teraz możemy obgryzać pozostałe liście poprawnie je kolorując (zawsze "przyciągając" tam odpowiedni kolor z liścia), aż zostanie nam drzewo gdzie jest jeden wierzchołek o stopniu 3 + długie ścieżki. Teraz możemy obgryzać skracając te ścieżki, aż zostanie gwiazda na 4 wierzchołkach. Kolorowanie da się dokończyć, chyba że kolory docelowe na tych 4 wierzchołkach są niefortunne (środek w jednym kolorze, ramiona w drugim), i właśnie w tej sytuacji używamy faktu, że (1) reszta grafu jest już pokolorowana poprawnie, i (2) istnieje krawędź o końcach w tym samym kolorze. Używamy tej krawędzi żeby na chwilę "odsunąć" ciąg poprawnych kolorów o 1 krok od środka gwiazdy (tej która nam została do pokolorowaina), pokolorować gwiazdę poprawnie, i potem "przesunąć" te poprawne kolory spowrotem.

Algorytm do tego wymyśliłem jeżdżąc takimi autostradami w praktyce. Najważniejsze to jechać środkiem! Jeśli trafimy na samochody przed nami, to patrzymy czy szybciej się je ominie z lewej, czy z prawej.

https://krzysiek.how/drzewa-czerwono-czarne-potyczki/ :)

Chciałem serdecznie podziękować organizatorom konkursu. W szczególności chciałem podziękować autorowi zadania drzewa czerwono-czarne, za zadanie które sprawiło mi dużo przyjemności. Gratuluję zwycięzcom oraz osobom z końca rankingu, którzy jak widziałem nie rezygnowali i do ostatniej rundy wysyłali swoje rozwiązania.

Ach! I choć wiem, że autorzy powiedzą że to przypadek... to nie mogę pozbyć się wrażenia że wiem o którym Karolu mowa w zadaniu Autostrady.

No też tak zrobiłem, dlatego pytam, czy da się porządnie xD

porównanie z brutem dla 10k testów to najlepszy dowód

Zakładam, że większość miała tak: jeśli graf nie jest ścieżką, to a) jeśli na początku wszystkie są w jednym kolorze, to nie da się nic innego uzyskać, b) jeśli na początku każda krawędź łączy wierzchołki różnych kolorów, to nie da się zrobić tak, żeby wszystkie zmieniły kolor c) poza tym wszystko się da
Jak to najprościej udowodnić?

Mam nadzieję że 86-89 wystarczy. :)