Codeforces 1809F

link do zadania: https://codeforces.com/contest/1809/problem/F

Treść

$N$ miast (oznaczonych ${1, 2, \dots, n}$) znajduje się na pewnym okręgu w tej kolejności. Z miasta $i$ możemy przedostać się do $(i+1)$-wszego (gdzie dla $n$ jako kolejne przyjmujemy miasto $1$).

Niech $f(i)$ oznacza minimalny koszt podróży wokół okręgu, jeśli zaczynamy w mieście $i$. Dla każdego $i$ chcemy znaleźć wartość $f(i)$.

Poruszanie się wymaga paliwa, a nasz pojazd ma $k$-litrowy zbiornik (więcej nie zmieścimy w danej jednostce czasu). W mieście $i$ koszt $1 l$ paliwa wynosi $b_i$ (zauważ, że $b_i$ przyjmuje bardzo specyficzne wartości). Wiemy też, że odległość z miasta $i$ do kolejnego wynosi $a_i$.

Limity

W liczbach całkowitych:

• $1 \leq t \leq 10^{4}$ (liczba przypadków testowych)
• $3 \leq n \leq 2 \cdot 10^{5}$ (liczba miast)
• $1 \leq k \leq 10^{9}$ (maksymalna pojemność zbiornika)
• $1 \leq a_i \leq k$ (odległość do następnego miasta)
• $1 \leq b_i \leq 2$ (koszt paliwa w mieście)
• $\sum n \leq 2 \cdot 10^{5}$

Rozwiązanie

Pierwszym typowym w takich zadaniach pomysłem jest “rozwinięcie” okrągu w prostą. Tworzymy dwie kopie każdego miasta, czyli $i$ oraz $i+n$ odpowiadają temu samemu miastu. Wtedy każda podróż po okręgu może być reprezentowana jako przedział $[l, l+n-1]$.

Brute force

Symulujemy proces podróży dla każdego $i$. Możemy zastosować podobny trick jak w zadaniu CF 1238G Adilbek and the Watering System. W każdym momencie czasu trzymamy najlepsze $k$ litrów paliwa, które mogliśmy kupić. Będziemy dodawać nowe i wyrzucać to najdroższe. Przy przejściu z miasta $i$ do kolejnego dokonujemy zakupu najtańszych $a_i$ paliwa, które zapamiętaliśmy.

Warto dodać, że w takim rozwiązaniu możemy pominąć założenie o $b_i \in \{1, 2\}$. Możemy użyć mapy (potrzebujemy $\textit{min}$ oraz $\textit{max}$, można też użyć dwustronnej kolejki priorytetowej), wtedy dla każdego początku $l$ złożoność czasowa wyniesie $\mathcal{O}(n \cdot log_{2}(n))$. Zatem ostatecznie mamy $\mathcal{O}(n^{2} \cdot log_{2}(n))$.

Brute force, ale sprytniejszy

Spróbujmy wykorzystać dodatkowe założenie, które ominęliśmy w poprzednim podejściu.

Po pierwsze, zauważmy, że $\textit{koszt podróży} \geq \sum_{i=1}^{n} a_i$. Zatem możemy od razu dodać taką wartość do wyniku, a koszty $b_i$ zmniejszyć o $1$, uzyskując odpowiednio $\{0, 1\}$. Czyli teraz płacimy tylko w miastach o pierwotnym koszcie $2$ (dalej nazywanych typem $1$), a w pozostałych (typ $0$) paliwo dostajemy za darmo.

Kiedy coś jest darmowe, oczywistym jest, że chcemy to wykorzystać. W miastach typu $0$ będziemy brać maksymalnie dużo paliwa. W miastach typu $1$ weźmiemy zupełne minimum - tylko tyle, aby dojechać do następnego. (Nie chcemy przecież sytuacji, gdzie zostało nam jakieś paliwo, za które musieliśmy zapłacić, gdy w nowym mieście możemy je mieć za darmo.)

Stąd pomysł, żeby dla każdego miasta wyznaczyć ostatnie miasto typu $0$, które pojawia się przed nim. W nim kupimy minimum z tego, ile będziemy potrzebować na dalszą podróż i $k$ (wliczyliśmy to do wyniku na samym początku). Teraz “łańcuch” ($1$ $\cdot$ miasto typu $0$, $x$ $\cdot$ miasto typu $1$) miast będzie zużywał to paliwo, w pewnym momencie się ono wyczerpie (lub będzie go niewystarczająco) i dokonamy normalnego zakupu.

Wszystko możemy zrobić dla pojedynczego $l$ w $\mathcal{O}(n)$, powtarzamy $n$ razy, stąd $\mathcal{O}(n^2)$.

Wzorcówka

Zamiast brutalnie symulować proces dla każdego miasta, zauważmy, że duży fragment podróży jest wspólny dla początków w $i$ oraz w $i+1$.

Zatem spróbujmy wykorzystać zwykłe policzenie wyniku dla $l=1$ i “indukcyjnie” zamieniać go w wynik dla $l=2, 3, \dots, n$ w czasie $\mathcal{O}(\textit{szybko})$.

Intuicyjne jest utrzymywanie przedziału $[l, r]$ i przesuwanie obu końców o $1$ w prawo. Takie przesunięcie może utworzyć nowy łańcuch lub przeciąć stary.

Ogólnie, miasto $i$ ma dwa różne możliwe koszty: $c_{0, i}$ (z wpływem poprzedzającego go miasta typu $0$) oraz $c_{1, i}$ (bez tego wpływu).

Zauważmy, że dodanie miasta na koniec (przedłużanie istniejącego łańcucha lub tworzenie nowego) jest proste. Wystarczy sprawdzić, czy początek łańcucha znajduje się w obecnym przedziale. Pozostaje rozwiązać problem aktualizowania łańcucha, który przecinamy poprzez przesunięcie $l$.

Ale i to jest proste i szybkie, ponieważ sumarycznie miast w łańcuchach jest $\mathcal{O}(n)$. Możemy robić “two-pointers”, gdzie zamieniamy wyniki miast z $c_{0, i}$ na $c_{1, i}$ na prefiksie utrzymywanego przedziału.

Zatem końcowa złożoność to amortyzowane $\mathcal{O}(n)$.

moje rozwiązanie: https://codeforces.com/contest/1809/submission/356610808

Alternatywne rozwiązanie (An Son Nguyen)

Spróbujmy w inny sposób zoptymalizować brutalne rozwiązanie. Weźmy dowolny indeks o najmniejszym $b_i$ i ustawmy go jako “punkt startowy”. Zauważmy, że każdą optymalną podróż od indeksu $i$ po całym okręgu możemy robić na 2 segmenty: od indeksu $i$ z pustym zbiornikiem do punktu startowego z pustym zbiornikiem, oraz od punktu startowego z pustym zbiornikiem do $i$ z pustym zbiornikiem. Jest tak, gdyż zawsze będzie nam się opłacało kupować jak najwięcej litrów w miejscach o minimalnym $b_i$. Koszt przejścia drugiego segmentu dla każdego indeksu będziemy obliczać wcześniej omawianym algorytmem zachłannym, zaczynając od punktu startowego i poruszając się zgodnie ze skierowaniem krawędzi. Koszt pierwszych segmentów będziemy zaś liczyć “od końca”, poruszając się od punktu startowego w kierunku przeciwnym do skierowania krawdędzi. Wystarczy nam do tego proste programowanie dynamiczne z gąsienicą.

Ponownie, końcowa złożoność to amortyzowane $\mathcal{O}(n)$.

kod Ana Sona: https://codeforces.com/contest/1809/submission/273910141

Refleksja nad zadaniem

Warto zastanowić się, jak rozwiązać zadanie przy innych ograniczeniach, przykładowo dla $k=\infty$ i dowolnych $b_i \in \mathbb{Z}_{+}$. Również ciekawa jest mocniejsza wersja oryginalnego zadania dla dowolnych $b_i \in \mathbb{Z}$.