Dziękuję organizatorom za przygotowanie zadań. Naprawdę świetnie się z nimi bawiłem. Dziękuję również całej społeczności z forum, która tak licznie wrzucała testy, które niejednokrotnie ratowały mi skórę :]

@Tomasz Bogusławski Nie zaprosiliście do wzięcia udziału, to się obraziły :)

Dołączam się do prośby. Znam poza mną jeszcze jednego kolegę, którego żona obraziła się podobnie jak moja mniej więcej w 4 rundzie...

Ja również dziękuję organizatorom. Podziwiam za wymyślenie tylu ciekawych zadań. Dla mnie poziom trudności zadań jest bardzo wysoki, ale w końcu o to chodzi, żeby zmierzyć się z czymś nowym i trudnym, a nie powielać stare sztuczki.

Też się dołączam, bardzo ładne zadania, a rozwiązanie zadania Fiołki jest wręcz genialne. Nie wiem, jak co roku dajecie radę wymyślać tyle fajnych i trudnych zadań, ale gratulacje :)

80 z groszami, [but] były proste, więc każdy +10, na [dcc] trochę osób mogło strcić punkty walczących o koszulki, największą nie wiadomą jest ile punktów będzie za kwadratowe rozwiązanie [des] na które można było łatwo wpaść.

Co do 1) to wydaje mi się, że sensownym rozwiązaniem może być możliwość wrzucania generatorki, jeśli duże pliki są z jakiegoś powodu problemem. 2) i 3) gorąca popieram, bardzo przydatne są te funkcje.

+1 na większe pliki na testrun. Jak już chciałem coś sprawdzić, to się okazało, że nie mogłem, z powodu 5MB pliku wejściowego (jest 50KiB dozwolone...)

W obronie bruta:

Jeśli dobrze policzyć złożoność obliczeniową, biorąc pod uwagę, że losowy dostęp do pamięci wielkości M na dwuwymiarowym układzie scalonym zajmuje czas O(M^0.5) [*], to rozwiązanie dziel i rządź również zajmuje O(nk log n + qk n^0.5) = O(n^2) dla q = n, k = n^0.5.

Natomiast rozwiązanie Jacka jest lepsze, nadal wychodzi O(n^(5/3)).

[*] https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

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

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

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

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.

Jak czepiamy się literówek, to w zadaniu [SKR] pierwsza linia sekcji "Wyjście" to "Na wyjściu powinno znaleźć się t wierszy.", gdzie oczywiście chodziło o "q wierszy". W treści literka t oznacza moment rozpoczęcia spaceru w danym zapytaniu i się zmienia.

Ad 1&2 - zdecydowanie popieram!

Ad 3 - jestem 'świeżakiem' i nie wiem o co w takiej tabelce chodziło, ale być może ma to związek z inną rzeczą której brakuje. Chodzi mi o coś a'la statystyki per zadanie. To znaczy: dla każdego zadania ile było zgłoszeń (ostatecznie ocenionych), a następnie jaki był rozkład punktów. To byłaby jakaś forma oceny trudności zadania. W wersji minimum chodziłoby o ranking per zadanie (bo wtedy każdy sobie takie coś sam wyliczy).

A zupełnie nikomu nie potrzebnym (ale bardzo fajnym!) bajerem byłby wykres pokazujący intensywność zgłoszeń, czyli liczba zgłoszeń w czasie.