Dodanie std::min(..., 5000) spowodowało że się wykręca w max 1,5s :/

Gratuluję autorom tegorocznych potyczek, mogę zupełnie szczerze napisać że zadania z serii B były MEGA fajne (na serię A nie starczyło czasu, ale patrząc po trudności serii B domyślam się że tam była już zupełna masakra). Podzielę się jednak jednym spostrzezeniem. Biorę udział w potyczkach już od wielu lat, i zauważyłam że tegoroczne zadania z serii B spokojnie trafiłyby do serii A jeszcze trzy czy cztery lata temu, i tendencja jest taka że robi się coraz trudniej, czego kulminacją jest ten rok i chyba poprzedni. Rozumiem że aby obniżyć średnią trudność zadania została w tym roku dodana seria C, dla bardziej początkujących zawodników. W efekcie zadania były albo bardzo łatwe, albo właśnie kozackie :), znalazłam max. jedno-dwa zadania o trudności umiarkowanej. Nie jest to żaden zarzut, a poprostu spostrzeżenie. Mi podobają się potyczki zarówno w wersji sprzed 4-5 lat , jak i tegoroczne. Dziękuję organizatorom i autorom zadań za fajny konkurs i *wiele* godzin przyjemnej rozkminy.

Też mam takie wrażenie, ale to oczywiście wynika z tego, że jak już się wpadło na to jak powinien wyglądać ciąg w [A], to implementacja była bardzo prosta. Chociaż trzeba przyznać, że zakaz dzielenia się testami był bardzo dużą podpowiedzią, że rozwiązanie jest proste.

Różnica jest zatem taka, że w [A] (moim zdaniem) trudniej było wpaść na to *co* trzeba zrobić, a w [B] *jak* to należy (dobrze) zrobić.

Ja zrobiłem tak:

1. Jeśli suma wszystkich a_i < 0 to nie ma rozwiązania.

2. Jeśli ta suma = 0, to jest tylko jedna możliwość sieci - tam gdzie jest przepływ zerowy nie trzeba robić połączenia.

3. Jeśli suma > 0, to można wybrać miejsca gdzie zmniejszymy a_i tak aby zmaksymalizować odcinki o przepływie zerowym i aby suma całkowita była 0.

4. Przepływ na odcinku między i a i+1 możemy regulować w zakresie od suma a_{1..i} do suma a_{i+1..n}, jeśli w tym przedziale nie ma zera to na pewno nie uda się tu zrobić przerwy w sieci.

5. Reasumując szukamy takiego ciągu dla 1..n niemalejącego od 0 do suma który by przechodził przez maksymalną ilość punktów gdzie możemy zrobić przerwę.

6. Algorytm Dijkstry na grafie wszystkich możliwych wykresów ciągów dał się dobrze zoptymalizować. Przebiegałem od 1..n pamiętając na multisecie ile razy ciąg zaliczył miejsca zerowego przepływu na danym poziomie 0...suma. Jeśli zaliczyłem nowe miejsce, to kasuję 1 następny większy element.

7. Liczba n minus ilość elementów multiseta daje odpowiedź. Koszt O(n log n).

Ups, teraz zobaczyłem, że w treści było m*n<10^7, nie n, m<10^7 🙃

Nie wydaje się wam że zadanie Punkty rankingowe [A] było prostsze niż Mieszanie kolorów [B]? Oczywiście po zauważeniu że k=n dla RAN :)

Zadania bardzo ciekawe, super konkurs :)

Ja mam rozwiązanie O(n^2)

Robiłem programowanie dynamiczne, w dp[i] trzymam ilość sposobów utworzenia poprawnego ciągu dającego sumę i (tablica ma rozmiar 5000). Ciąg na wejściu sortuję niemalejąco. Możemy zauważyć, że jeżeli da się utworzyć poprawny ciąg o sumie a[i]-1 lub większej, to można dodać do niego element a[i] i ciąg nadal będzie poprawny. Zatem robię coś podobnego do problemu plecakowego, dla kolejnych elementów a[i] przechodzę pętlą for (int j=5000; j>=a[i]-1; j--) i wykonuję dp[j+a[i]] += dp[j]; oczywiście wszystko moduluję. Zostaje jeszcze jedna obserwacja - j+a[i] może być większe od 5000. Warto zauważyć, że wtedy opłaca się zwiększyć dp[5000], ponieważ na wejściu mamy liczby do 5000, więc każdy poprawny ciąg dający sumę 5000 lub większą da się przedłużyć. Wystarczy zatem zmienić dp[j+a[i]] += dp[j]; na dp[min(5000, j+a[i])] += dp[j]; (oczywiście wszystko modulujemy). Na koniec sumujemy wszystkie wartości dp[i] dla i = 1, ... , 5000

Na swoje pocieszenie dodam że wzorcówka (outy w testach) też wykorzystywała tą gęstą drabinkę binarną i dała 87 dla testu 10d, gdzie moje rozwiązanie dało 86.

Zauważ że wszystkie sumy powyżej 5000 są sumowane przy dodawaniu kolejnego pudełka więc nie ma sensu ich rozróżniać zatem wystarczy zliczać tylko początkowe 5000 a powyżej w jeden worek.

Ja na trochę niższym poziomie, bo dopiero od września robię zadania algorytmiczne tak na poważnie,
więc głównie rozwiązywałem zadania z [C] i muszę przyznać - były bardzo ciekawe, trzeba było sporo pomyśleć,
Najbardziej podobało mi się [DAG] ( Nie mówiąc już o momencie gdy wyświetliło się '10' ) :)

Wynik 60 (+- 1) można uzyskać analizując zapis k w systemie trójkowym:

k = 3 * x + r

Dla r = 0 lub 2

1 => 2 3
2 => 3 4
3 => 4 A

A = -1 dla r = 0 oraz A = n dla r = 2

Dla r = 1

1 => 2 4
2 => 3 4
3 => 4 n

No tak, nie pomyślałem że te -1 w przypadku drugiej drabinki binarnej można wykorzystać i nie tworzyć dodatkowych węzłów :)

Jak rozwiązać optymalnie zadanie Cukierki?

Ja zrobiłem to dość prosto - do mapy t[możliwa_końcowa_suma_cukierków]=ilość_rozwiązań; dodawałem kolejno opakowania od najmniejszego. Niestety dla przypadków typu:

5000
1 2 3 4 5 6 7 .... 4999 5000

nie kończyło się to w rozsądnym czasie, przez co nie przechodziło dwóch ostatnich grup testów (8/10). Wygląda że się robiło O(n^3 log n).

Binarnie można do 60 wierzchołków zjechać.

1 => 2 3
2 => 3 A
3 => 4 5
4 => 5 B
5 => 6 7
6 => 7 C

przy czym A, B, C to albo -1 (jeśli kolejna cyfra binarnego rozwinięcia k jest 0) albo n (jeśli ta cyfra to 1)