To ja mam chyba nk^2 log nk^2, z możliwym (chyba) syfnym zbiciem do nk log nk, ale zobaczymy czy poprawne :) (k to liczba pasów).

Tak w skrócie to chyba mam podobnie do tego co Krzysztof, tylko myślę o tym tak, że mam graf/dpka w którym stanem jest krotka (numer pola, numer pasa, mój numer pasa). No i teraz taki stan mi mówi, że jestem na pasie "mój numer pasa" w pozycji równoległej (po czasie t) do pola (numer pola, numer pasa), bo zauważam, że jak jadę jakimś pasem, to albo zmieniam pas od razu (czas zero), albo chcę trochę podjechać, a skoro chcę trochę podjechać to muszę jakieś nowe pole spotkać. Jak chcę trochę podjechać to znajduję pierwsze pole, które spotkam i tam przechodzę. No i Dijkstra po tym (stąd ten czas t). Podjechać tzn. albo jadę prędkością pasa, jeśli jest przede mną bezpośrednio samochodzik, albo z moją jeśli nie ma - to jest "do przodu, albo z prędkością pasa jeśli jest za mną, albo z prędkością zero jeśli nie ma - to jest "do tyłu".

Chyba się jednak tego nie da zbić :(

1) Czemu na testrunie można wgrywać tylko małe pliki? Chciałem go używać do POB, SKR, DES, FIO. Do żadnego nie mogłem, bo wszystkie plki wejściowe do tych zadań są za duże (a raczej limit maksymalny na ich wielkość jest beznadziejnie mały)... Co prawda da się to jakoś przeżyć generując w kodzie swoje wejście on the fly, ale jest to niewygodne, nie można tego używać na plikach z forum i zajmuje więcej czasu, a nie widzę sensownych powodów na tak niskie limity.
2) Testrun nie pokazuje zużytej pamięci... Jak w zasadzie całe SIO. Tu już może to jakiś większy problem, ale jednak inne sprawdzarki umieją i jest bashowa komenda, która wypluwa zużytą pamięć.
3) Kiedyś pokazywały się ładne punkty w tabelce "Problems", ale zniknęło :(

"to znaczy że ta przerwa już nam się nigdy nie przyda," - łoooo, racja! To by mi wiele uprościło!

IMO jeśli O(n^2) z jakimiś drobnymi optymalizacjami stałej wchodzi, to myślę że trochę porażka dawać takie zadanie. Limity sugerują że brut nie może zajmować jakoś dużo ponad TL, ale zakładałem że autorzy zadania opcili bruta low-level trickami przez tydzień, i nie zbili czasu dostatecznie, więc zdecydowali się zadanie dać, ale może nie jest to prawda.

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

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.

Ja mam to, co Tomek Czajka, tylko jak zapytanie nie było wliczone w jakiś dłuższy przedział niż o dlugosci 2k, to odpowiadam drzewkiem przedziałowym. Maxtesty z forum chodziły < 30s, ale test n = 3e5, q = n/2, każde zapytanie jest o 2 krótsze jakieś 55s lokalnie. @Igor Hańczaruk myślę, że coś zepsułeś z grupowaniem. Ewentualnie, masz mało wydajne pętle w części z brutem

Ja robię całość w O(n).

Wyprzedzanie lewą stroną jest prostsze do ogarnięcia. Patrzymy na pierwszą kolumnę samochodów na lewym pasie:
1. Jeśli jeszcze nie wyprzedziliśmy tej kolumny, to jedyna opcja to jechać za nią.
2. Jeśli już wyprzedziliśmy całą tą kolumnę, to możemy o niej zapomnieć na zawsze, bo ona już nas nigdy nie dogoni. Kasujemy tą kolumnę, patrzymy na kolejną i wracamy do punktu 1.

Po prawej stronie patrzymy na pierwszą przerwę. Załóżmy na chwilę, że możemy taranować samochody za tą przerwą, i policzmy czas wyprzedzania:
3. Jeśli mamy gorszy czas niż lewą stroną, to już wiadomo, że wyprzedzamy lewą.
4. Jeśli mamy lepszy czas niż lewą stroną, i nikogo nie musimy taranować, to wyprzedzamy prawą.
5. Jeśli mamy lepszy czas niż lewą stroną, ale jednak kogoś musimy staranować, to znaczy że ta przerwa już nam się nigdy nie przyda, bo niezależnie którą stroną wyprzedzimy, ta przerwa już będzie za nami. Więc kasujemy tą przerwę na zawsze, patrzymy na kolejną, i wracamy do punktu 3.

Moje rozwiązanie jest zrandomizowane, ale nie zdążyłem do końca policzyć jaka tak naprawdę jest jego złożoność.

Rozwiązanie opiera się o obserwację, że możemy wylosować pozycję jakiegoś piwota wewnątrz tablicy i dla niego
policzyć wszystkie stany DP na lewo i na prawo. Teraz jeżeli ten piwot jest pomiędzy dwoma blokami z optymalnego
rozwiązania w jakimś zapytaniu, to wtedy znajdziemy za jego pomocą odpowiedź dla tego zapytania. Po każdym
pivocie możemy więc przeiterować się po zapytaniach i zmaksować ich odpowiedzi.

Dopóki mamy czas, będziemy więc losowali piwoty i dla nich maxowali wyniki. Okazuje się, że uda sie nam w ten sposób
wylosować jakieś N/30 pivotów. Jeżeli teraz zauważymy, że każdy koniec bloku z optymalnego rozwiązania dla jakiegoś
zapytania ma 1/20 szans na bycie wylosowanym, to szansza porażki przy kilkuset blokach w rozwiązaniu jest już znikoma.

Są dwa problemy:
1) Krótkie przedziały - wtedy po prostu wykonujemy dla nich naiwne obliczenia

2) Długie zapytania, których rozwiazania są prawie całkowite wypełnione blokami - Tu jest nieco ciężej, ale oobersujemy
że jeżeli dla takiego zapytania wiemy, że jest mało komórek, których nie uwzglądnia w rozwiązaniu (niech tych komórek będzie x),
to możemy policzyć dla niego wynik za pomocą nieco zmodyfikowanego DP w czasie (Nx / k). Wydaje mi się, że to wystarcza
do osiągnięcia maksymalnej liczby punktów.

Warto zauważyć, że to rozwiązanie potrzebuje jedynie pamięci O(N)

@Tomek: nie wiem jakie dokładnie masz rozwiązanie (o dziwo nie domyśliłem się całego po Twoim opisie ;)), ale w moim kodzie nie ma zupełnie żadnej bezpośredniej interakcji pomiędzy lewym a prawym pasem. W swoim kodzie liczyłem dp[i] - najkrótszy czas, po którym jestem w stanie dojechać na i-te pole na środkowym pasie. Do następnego wolnego pola j na tym środkowym pasie albo dojeżdżam bezpośrednio (iff j=i+1) albo wymijam górą albo wymijam dołem. Na wymijanie górą i dołem mam dwa kompletnie różne kody z prawie zerową częścią wspólną logiki i oba to niezłe syfy. Aczkolwiek góra prostsza - w szczególności górę robię w O(n), a dół w O(n log n).

Obstawiam, że na >-90% to będą jakieś czary na EGF (exponential generating function), ale jakie to nie mam pojęcia (tzn. nie wzięcie kodu i przywalenie prostą konwolucją, ale jakieś faktyczne nietrywialne algebraiczne przekształcenia na nich).
Aczkolwiek przyznam, że już sam dynamik w O(n^2 log n) jest dość trudnym zadaniem... Więc może się podzielę zajawką. Zliczyć te drzewa w O(n^dużo) to nie tak trudno standardowym trikiem z fixowaniem centroidu, ale aby uzyskać n^2 log n, to trzeba wpaść na pomysł, aby fixować nie centroid, a tak jakby "centroid ważony zbiorem niezależnym" i wtedy w ogóle pozbywamy się w dynamiku wymiaru, który liczy nam rozmiar drzewa

Czy potyczki mogłyby trwać dwa tygodnie? Pierwszy tydzień z minimalnym obciążeniem - tylko grupa C wg podobnego harmonogramu jak teraz - z tą różnicą, że koniec byłby dzień wcześniej - tzn. w sobotę a nie w niedzielę. W niedzielę dzień przerwy i potem grupa A i B. Z rundy próbnej można w tym układzie zrezygnować.

Z jednej strony oznacza to więcej pracy dla organizatorów - z drugiej "zmarnowałoby" się mniej zadań. No i wielu zawodników po pierwszym tygodniu mogłoby mieć tyle samo punktów co ścisła czołówka - cóż za motywacja do dalszej wytężonej pracy! :)

Jakbyś był "patriotą" i został w kraju i poszedł na UW, a tam na ćwiczenia z algorytmów parametryzowanych, które prowadzę co 2 lata, to może byś usłyszał o gammoidach :P... O gammoidach w istocie słyszałem i wiedziałem, że są liniowo reprezentowalne (aczkolwiek czym jest owa reprezentacja, to musiałem googlać), ale nigdy w życiu bym się nie spodziewał, że to się może jakkolwiek przydać na contestach.

Czymś pewnie istotnie bardziej znanym będzie tzw. matroid transwersalny. Bez nazywania go po imieniu to tak naprawdę już dla jajec klepałem go na preOIu w liceum. Tzn. klasyczne zadanie o największym skojarzeniu w grafie dwudzielnym. Zamiast je robić ścieżkami powiększającymi, to można każdą jedynkę w macierzy sąsiedztwa zastąpić przez losową liczbę mod P i policzyć rząd tej macierzy, który będzie właśnie rozmiarem owego skojarzenia. Pewnie jest to coś, o czym sporo osób tutaj słyszało/było tego świadomym, a to jest tak naprawdę szczególny przypadek tego gammoidu i jego liniowej reprezentacji.

Ja mam bruta z kilkoma optymalizacjami pętli wewnętrznej, co liczył big testy z forum w 10-20sekund (przed optymalizacjami nawet >55sekund). Optymalizacje zrobilem tylko dla k>=5... Ciekawi mnie jakie było to oczekiwane przez autorów zadania rozwiązanie :)

Ktoś coś? Ja mam dynamik w O(n^2 log n), i miałem nadzieję go zopcić jakimś FFT/sqrt, ale coś nie wyszło...