Czy ktoś (organizatorzy? xd) chciałby się podzielić rozwiązaniem do tego zadania?

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

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.