Ania, Tomek - bardzo dziękuję :)
Czy nie ma jednak prostszego rozwiązania? Zadanie jest z grupy B, więc teoretycznie rozwiązanie nie powinno być tak skomplikowane?
A swoją drogą - ciekawa rzecz: bezwładność umysłowa - jakoś zafiksowałem się na tym, że z równości minimalnego pokrycia z maksymalnym skojarzeniem w grafach dwudzielnych można miło skorzystać tylko w jedną stronę - od maksymalnego skojarzenia do minimalnego pokrycia.

"Jednak jak ktoś miałby dodawać te więcej języków to oni" To nie za bardzo prawda. SIO2 jest open source, więc jeśli komuś będzie wystarczająco bardzo zależało to może samodzielnie spróbować dodać taką funkcjonalność. Na technicznych leżałoby tylko ewentualne wdrożenie tego do sio2 potyczkowego.

Ogólny szkielet rozwiązania jest identyczny, jak w zadaniu [ELE] (rozwiązanie opisałem w innym wątku).

Odcinamy kolejne liście. Każdy węzeł zawiera listę projektów agregujących dane z całego odcinanego poddrzewa.

W każdym projekcie istotne dla nas są trzy atrybuty: liczbą zamkniętych części, suma kwadratów wartości w zamkniętych częściach, suma wartości w niezamkniętej części. Różnica jest taka, że każdy wierzchołek musi agregować projekty być może z wielu różnych odcinanych fragmentów - dlatego przy odcinaniu kolejnego węzła robimy iloczyn kartezjański projektów: z odcinanego wierzchołka oraz jego sąsiada (posiadającego być może zagregowane projekty z innych odciętych części) - to powoduje wykładniczy wzrost wielkości list projektów.
Oczywiście każdą taką parę projektów możemy połączyć na dwa sposoby: zamykając otwarty fragment lub łącząc go z kolejnym wierzchołkiem.

Ponieważ listy projektów gwałtownie rosną, po każdym kroku oczyszczamy listy z projektów gorszych od innych projektów na liście. Okazuje się, że takich projektów do usunięcia jest bardzo dużo, co jest efektem losowych danych. Z tego też względu całość działa całkiem szybko. Złożoność to O(n * n * X), bo dla każdego z 'n' węzłów przechowujemy co najmniej 'n' projektów (dla różnej liczby obszarów), natomiast X we wzorze oznacza, że dla każdej liczby obszarów możemy mieć wiele nieporównywalnych projektów, jednak właśnie to X dla losowych testów jest względnie małe.

Zgadzam się, że zadanie próbne było dziwnie trudne i pewnie odstraszające dla początkujących.

Ja Wam powiem jaka jest brutalna prawda co do innych języków programowania na PA. Może się trochę pomylę, ale na moje oko 95% osób startujących regularnie w konkursach używa C++, 4% Javy, a reszta Pythona czy jakichś innych wymysłów. W szczególności główni organizatorzy merytoryczni są "konkursowymi zawodowcami" i im używanie czegoś innego niż C++ do zadanek w ogóle nie przychodzi do głowy. Dlatego nie forsują jakoś szczególnie innych języków. Aczkolwiek tak naprawdę to nie od nich zależy, więc tak naprawdę ten wstęp jest mało relewantny. Wszystko zależy od technicznych, bo to oni zajmują się ogarnianiem funkcjonalności SIO. Na ile są oni leniami zbijającymi bąki, a na ile bardzo ciężko pracującymi ludźmi - nie mam pojęcia. Jednak jak ktoś miałby dodawać te więcej języków to oni, a co zrobić aby ich do tego zmotywować też nie wiem :). Potyczki rzeczywiście mają jakąś ciekawą własność popularyzatorską, dzięki której zgarniają ludzi z szerszego spektrum, dla których C++ nie jest głównym językiem, bo z competitive programming mają aktualnie wspólne PA raz na rok, a w pracy se tam programują w czymś innym i nawet jak widać tacy zawodowcy jak Tomek po jakimś czasie od zaprzestania regularnego uczestniczenia chętnie by zobaczyli więcej języków. Jednak właśnie to, że PA jest chyba jedynym znanym mi konkursem gdzie ludzie proszą o więcej języków sprawia, że ich dodawanie nie leży wśród priorytetów technicznych.

Wydaje mi się, że marzec - kwiecień jest dużo lepszym terminem. Wiosenna aura sprzyja potyczkowaniu się ;)

Dziękuję za opis! W miarę się zgadza z tym co myślałem. Poległem niestety na szczegółach implementacyjnych, które są ćwiczeniem dla czytelników xd Ale już jestem przynajmniej utwierdzony, że trzeba w te przypadki brnąć aż się uda.

Największą trudnością było chyba dla mnie to, że niektóre programy mają półbloki, a niektóre programy nie mają. I jeśli jakiś program nie ma półbloku to czasem trzeba go rozważyć jako początek a czasami trzeba rozważyć jako środek i trzeba uważać, żeby nie rozważyć jako oba jednocześnie. Podobnie ostatnie fragmenty programów mogą działać jak zwykłe środkowe bloki o ile nie są faktycznie ostatnimi, bo wtedy muszą być wzięte w całości. Z tego powodu jest mało intuicyjne, że "Prefiks i sufiks wybieramy dopiero w ostatnim kroku poprawiania", bo niektóre elementy mogą działać zarówno jako środkowy blok jak i początek lub koniec. Więc wybierając zachłannie taki blok na początku poprawiania, może się okazać na koniec poprawiania, że najlepszy początek/koniec jaki możemy dobrać jest zabroniony, bo jest w konflikcie z tym środkowym blokiem co był wzięty zachłannie na początku.

Przy danym przeplocie możemy prześledzić, jaką ścieżkę "przebyła" ostateczna wartość. (Ostateczna wartość pochodzi z jakiegoś zapisu, wcześniej z odpowiadającego mu wczytania, znowu zapisu itd. aż okaże się, że pochodzi z jednej konkretnej początkowej zmiennej). Pozwala to na napisanie prostego dynamika w O(iloczyn_długości_programów * n), który otrzymuje 2 punkty.

Do lepszych rozwiązań należy po pierwsze pozbyć się obfuskacji kodu: każdy program można doprowadzić do postaci ciągu bloków "W c1 Z c2 Z", gdzie c1 jest zmianą wartości o dowolną liczbę całkowitą, a c2 jest zmianą o nieujemną liczbę całkowitą. Dodatkowo programy mogą zawierać przed pierwszym blokiem fragment "c1 Z c2 Z" — nazwijmy go półblokiem. Mając tę postać, wróćmy do pomysłu ze ścieżką. Ta gdzieś się zaczyna i gdzieś się kończy. Najpierw dla uproszczenia, mnożąc złożoność przez O(n^2), przeiterujmy wszystkie takie możliwości. Pojawia się tu przypadek brzegowy: prefiks i sufiks mogą zawierać ten sam blok lub półblok, a ścieżka nie zawiera nic innego. Trywialnie ten przypadek rozpatrzyć, więc załóżmy, że prefiks i sufiks są rozłączne. Najpierw zachłannie, poza wybranym prefiksem i sufiksem, weźmy do potencjalnej ścieżki wszystkie fragmenty "W c1 Z" dla ujemnych c1. Może tak szczęśliwie się złożyć, że z wybranych fragmentów da się zbudować poprawną ścieżkę i nie musimy robić nic więcej. Istnieje tylko jeden powód, dla którego może się nie dać zbudować takiej ścieżki — dokładnie jeden program, nazwijmy go problematycznym programem, ma za dużo przedziałów; dokładniej, co najmniej połowę (plus minus jeden ze względu na pozycję prefiksu i sufiksu). To, o ile przedziałów jest za dużo w problematycznym programie, nazwiemy jego bilansem. Będziemy teraz zachłannie poprawiać nasz wybór, robiąc w pętli najtańszy z następujących kroków:
— Dodanie nowego przedziału "W c1 Z" poza problematycznym programem.
— Usunięcie jednego przedziału z problematycznego programu.
— Złączenie dwóch kolejnych przedziałów w problematycznym programie w jeden poprzez dodanie do ścieżki wszystkich instrukcji pomiędzy nimi.
Każdy krok poprawia bilans o jeden. Zwracam też uwagę, że dwa ostatnie kroki mogą się przeplatać: można usunąć przedział powstały przez złączenie przedziałów, podobnie można połączyć dwa przedziały, które stały się kolejne poprzez wyrzucenie jakiegoś przedziału pomiędzy nimi. Da się udowodnić, że w ten sposób otrzymamy optymalne rozwiązanie. Rozwiązanie ma złożoność O(n^3 log n) i dostaje ono 4 punkty na zawodach.

Okazuje się też, że da się wybrać stałą liczbę potencjalnych kandydatów na prefiksy i otrzymać złożoność O(n^2 log n) wraz z piątym punktem. Niestety, z sufiksami nie jest tak łatwo: może być wśród nich dowolnie wiele nieporównywalnych, więc musimy sobie poradzić z nimi inaczej. W rozwiązaniu wzorcowym nie korzystamy z powyższej nietrywialnej obserwacji o stałej liczbie możliwych prefiksów.

Głównym pomysłem prowadzącym do rozwiązania wzorcowego jest odwrócenie kolejności zachłannego poprawiania oraz ostatecznego wyboru prefiksu i sufiksu. Znajdźmy najpierw kandydatów na problematyczny program. Okazuje się, że muszą oni zawierać co najmniej połowę fragmentów "W c1 Z" z ujemnymi c1. Wynika z tego, że jeśli jest co najmniej jeden ujemny fragment, to jest co najwyżej dwóch kandydatów na problematyczny program. Przypadek, w którym nie ma żadnych ujemnych fragmentów, można rozwiązać bardzo prosto, gdyż optymalna ścieżka ma wtedy jedną z następujących postaci:
— Cały jeden program.
— Prefiks jednego programu i sufiks innego programu.
— Prefiks i sufiks jednego programu oraz jeden fragment "W c1 Z" z innego programu.
Od teraz mamy x <= 2 kandydatów na problematyczny program. Przeiterujmy (x + 1)^2 możliwości na to, gdzie znajduje się sufiks i gdzie znajduje się prefiks — albo wybieramy jednego spośród x kandydatów, albo stwierdzamy, że jest w innym programie, nie ustalając dokładnie, który to program. Okazuje się, że na podstawie tych informacji możemy już odzyskać jedyny problematyczny program oraz jego bilans. Możemy więc zacząć zachłanne poprawianie. Prefiks i sufiks wybieramy dopiero w ostatnim kroku poprawiania. Wybór ten może dodatkowo poprawić bilans, na przykład jeśli jako sufiks dodamy cały nowy blok "W c1 Z c2 Z"; może go też nie poprawić, jeśli dodamy samo "c2 Z" do już wybranego przedziału "W c1 Z" (który wtedy stanie się sufiksem ścieżki). Przy zachłannym poprawianiu, trzykrotnie — kolejno przy bilansach 2, 1 i 0 — próbujemy uzupełnić rozwiązanie najlepszymi prefiksami/sufiksami, które doprowadzają bilans do zera. Oczywiście cały czas musimy uważać, żeby jako prefiks i sufiks nie wybrać tego samego programu składającego się z tylko jednego bloku, ale to już są szczegóły implementacyjne. Ostatecznie otrzymujemy złożoność O(n log n) i 10 punktów za zadanie.

Dowody oraz szczegóły, które pominąłem, zostawiam jako ćwiczenie dla czytelników ;)

Mi się pomysł dogrywek nie podoba. Rundy i tak się już nachodzą i warto robić jak najwcześniej zadania, by nie mieć zaległości podczas następnej rundy. Jeśli zadania z pierwszej rundy będziesz robił jeszcze w środę, to jesteś w bardzo słabej sytuacji.

To bardziej jak sesja poprawkowa podczas gdy trwa już następna sesja. Efekt będzie taki, że nie zrobisz nowych zadań na czas.

Innym tematem jest wydłużenie konkursu, skoro jest za mało czasu. Może warto mieć 9 dni (od piątku do następnej niedzieli), z czego poniedziałek-czwartek są luźniejsze.

Na moje prywatne zapytanie otrzymałem odpowiedź, że będą zamawiane dopiero po finale.

Czy ktoś ma doświadczenie i wie kiedy mniej więcej przychodzą koszulki?

Widzę, że dogrywki nie mają szans - wszyscy są w trybie C : )

Może warto ograniczyć liczbę odsłon wyników w C do globalnej puli "liczba zadan + 1". W ten sposób trochę jednak by testowano C przed wysłaniem, a nie kompiluje się więc wysyłam. Albo przy drugim odsłonięciu dostajesz -1 pkt, w stylu bomby przy acm'owych zasadach.

Wydaje mi się że kobiety w zadaniach są wbrew pozorom nadreprezentowane. Była w jednym zadaniu Algolina, a łącznie bohaterów było ze 20, co oznacza że 5% bohaterów z historyjek to kobiety. Mogę się założyć, że kobiet biorących udział w Potyczkach jest mniej niż 5%.

W dywizji „C” też można punkty tracić. W zakończonej właśnie edycji cała pierwsza setka rankingu „B+C” zgarnęła komplet punktów za „C”, ale już sto pierwszy stracił dwa punkty na „Cukierkach”, a za miejscem 269, tj. ostatnim dającym koszulkę, komplet za „C” staje się rzadkością. Szczególnie zadanie z cukierkami przysparzało trudności, ale nie tylko ono. Tak że to nie jest tak, że „w tym roku na koszulkę wystarczyło za B dostać 12 punktów”, bo punkty za „C” wcale nie były za darmo.