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ć?

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

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

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

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.

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ół

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.

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

@Piotr niekoniecznie, u mnie brut który dfsował się po grafie wszystkich osiągalnych stanów zajmował 26 linijek kodu + wczytywanie danych. Co ciekawe, wykręcał całe 3 punkty.

Być może miało na celu nauczenie ludzi, że czasem lepiej napisać brute'a i popatrzeć na outy niż kminić dowód
EDIT: a czy wymyślenie rozwiązania bez wyraźnej wskazówki jaka jest odpowiedź jest trudne, to nie wiem bo nawet nie próbowałem

Zgadzam się, że zadanie było istotnie najtrudniejszym z dywizji C. Aczkolwiek 4B było dla mnie istotnie trudniejsze. Szczególnie biorąc pod uwagę, że to zadanie kodziło się parę minut, a 4B z godzinka przynajmniej

Swoją drogą moim zdaniem wymyślenie rozwiązania bez dowodu wydaje mi się dość dziwne. W sensie trochę nie wiem jaką ścieżką rozumowania można krążyć aby wpaść na te warunki co trzeba i jednocześnie nie być bardzo blisko pełnego dowodu. Chyba że ktoś pisał jakieś wykładniki i gapił się na outy i dopasowywał, to wtedy rzeczywiście można być zupełnie nieświadomym o co chodzi w zadaniu, a jednak dostać 10/10

Ja sprawdziłem ręcznym brute forcem na kartce, że w 4-wierzchołkowej gwieździe, jeśli ma się oba kolory, to można dojść do każdego stanu oprócz tego pechowego z innym kolorem w środku. Jeśli więc jest wierzchołek stopnia co najmniej 3, to można z niego rozrzucać dowolnymi kolorami we wszystkich kierunkach, i w ten sposób pokolorować całe drzewo. Na końcu, jeśli mamy zrobić ten pechowy stan, to znajdujemy odgałęzienie na którym mają być dwa wierzchołki pod rząd w tym samym kolorze, i na końcu zamieniamy wszystkie kolory na ścieżce ze środka gwiazdy do tego miejsca.

@Konrad Paluszek " 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"
To nie do końca tak (albo źle rozumiem opis:)).

Przy założeniach: wejście nie monochromatyczne, graf nie jest ścieżką:
1. Jeśli stanem końcowym jest drzewo - zebra, w ktorym każda krawędź łaczy różne kolory, takiego drzewa nie da się ułożyć, jeśli już nie jest stanem początkowym.
2. Każdy inny stan koncowy można uzyskać.

D1: Jeśli wykonałeś jakiś ruch, to skopiowałeś kolor wierzchołka na jego sąsiada. Ale nasz specjalny stan końcowy nie ma takiej krawędzi! Zebry nie uzyskamy ruchai z zadania.

D2. To w sumie już było opisane. Zajmijmy się naszym wierzchołkiem rzędu 3+ i jego wybranymi kolegami.
2
|
1 - 3
|
4
od każdego z wierzchołków mogą wychodzić dodatkowe krawędzie.
Sprowadźmy czarny kolor do wierzchołka 2, czerwony do 3 (dosć oczywiste, ze się da).
Teraz tą czwórkę mozemy wykorzystać do poprawnego wypełnienia całej pozostałej reszty drzewa:
Możemy 2 i 3 uzyc do wygenerowania dowolnego ciągu czerwonych i czarnych wierzchołków i "wysałć" je do poddrzew wychodzacych z 4 (a w sumie i ewentualnych z poddrzew podpietych pod 1). Wypełniliśmy je tym co trzeba, nie ruszamy wiecej.
Teraz przeniesiemy nasze oba kolory do 3 i 4 (też łątwo widać, że z dowolnej niemonochrometycznej konfiguracji kolorów wśrod 2,3,4 mozemy uzyskać dowolną konfigurecję kolorow wierzchołków 2,3,4(*)) i wepełnimy poddrzewa wychodzace z 2... a potem przeniesiemy czerowny i czarny do 2 i 4 i wypełnimy to, co wyrasta z wierzchołka 3.

Pozostaje nam teraz naprawić kolory wsrod 1,2,3,4. Jeśli w docelowym drzewie para identycznych kolorów, to oznacza, że albo wsród 2 3 4 są oba kolory, albo wszytkie 1,2,3,4 są tego samego koloru. W obu przypadkach wstawiamy (patrz (*)) odpowiednie kolory pod 2 3 4 i w obu przypadkach mamy skąd skopiowac odpowiedni kolor do wierzchołka 1.

Jeśli wsrod 1 2 3 4 nie ma pary identycznych kolorow, trzeba działać inaczej. 1 jest innego koloru niż 2 3 4. Za to w ktorejśc odnodze jest para, powiedzmy, że w odnodze 4

2
|
1 - 3
|
4 - 5 - 6 .... - k - (k+1)
(znów, od każdego wierzchołka mogą odchodzic całe poddrzewa, to nbieistotne).
k i k+1 sa identyczne. Skopiujmy k-1 na k, k-2 na k-1... 5 na 6.

Dla ustalenia uwagi, niech 1 ma byc czerwony, 2,3,4 maja byc czarne.
Mając rozne kolory w 2 i 3 wyemitujmy czarny do 5 i potem czerwony do 4.
nadpiszmy czarnym 2 1 3.
Skopiumy czarwony z 4 do 1, skopiujmy czerwony z 5 do 4.
Teraz pozostąło tylko naprawić ścieżkę. 6 kopiujemy na 5, 7 na 6... k+1 na k.
koniec:)

Dowód trochę skomplikowany przez te dwa przypadki, ale nie sa one istotne w testowaniu!
Implementacje idzie bardzo przyjemnie:
Sprawdzamy parę warunków o tym, czy drzewa sa równe i przypadki z monochromatycznoscią.

W głownej cześci (teraz przy założeniach wejście niemonochromatyczne i rozne od wejścia)
Przechodzimy listę krawędzi i szukamy pary o identycznym kolorze.
Przechodzimy wierzchołki i sprawdzamy kazdemu rząd.
Jeśli istnieje skrzyzowanie i nie ma pary jednokolorowej, wyswietlamy nie,
jeśli jest apra - tak. Jeśli ine ma skrzyowania, odpalamy osobną funkcję dla ścieżki (policz liczbę zmian kolorów, wyjście ma mieć mniej, lub tyle samo jeśli zaczyanją od tego samego koloru).

Uff, czyli nie tylko ja się zatrzymałem na dłużej przy tym zadaniu :) Ale jaka jest satysfakcja, gdy się wreszcie zobaczy, że tylko drzewa "na przemian kolorowe" są "zblokowane" i nie można zrobić dowolnego malowania.

Ja formalnie nie dowodziłem, za to założyłem że się da, po czym zweryfikowałem na testach i na odkrywaniu wyniku.
Mój algorytm wygląda tak (następny krok sprawdzam jeśli poprzednie nie rozstrzygnęły):
1. jeśli u = v to TAK (stan początkowy = końcowy)
2. jeśli ilość kolorów w u = 1 to NIE
3. jeśli nie istnieje para sąsiednich wierzchołków w jednym kolorze w v, to NIE
4. jeśli graf nie jest liniowy to TAK
5. jeśli ilość zmian kolorów w u jest mniejsza niż w v to NIE
6. jeśli jest większa to TAK
7. jeśli na początku linii mamy różne kolory w u i v to NIE
8. TAK

Jestem z siebie dumny bo wymyśliłem to samo co opisał Tomek w #25410 :)

Co do trudności to jak już się złapało za wierzchołek o stopniu co najmniej 3 to już te przypadki jakoś wychodziły (ja to tak zrobiłem, jedyny kod jaki napisałem do tego to wzo).

A jakie mieliście czasy? Mi weszło ledwo O(n log n) na multimapie (najwięcej: 10o OK 2.96s / 3.00s) :)
Po przerobieniu na O(n) (2 tablice z wierzchołkami połączonymi z danym, (jak był wierzchołek stopnia > 2, to krawędzie nie były potrzebne)) czasy dla dużych testów spadły koło siedmiokrotnie.