Informatyczny kącik olimpijski

Dwa zadania z Potyczek

W tym kąciku omówimy dwa zadania z Potyczek Algorytmicznych 2012. Pomimo krótkich rozwiązań, zadania te wymagały od zawodników niemałej dozy pomysłowości.

Treść zadania Korniki wygodnie nam będzie streścić w terminologii numizmatycznej:

Zadanie 1 (Kornik). na stole w jednym rzędzie leży $\text{[math]}$ monet o nominałach $\text{[math]}$ Dwóch graczy na przemian wykonuje ruchy. Ruch polega na zabraniu monety z lewego końca, z prawego końca lub z obu końców rzędu naraz. Wiedząc, że każdy z graczy gra tak, by zmaksymalizować sumę wartości zabranych przez siebie monet, należy wyznaczyć wynik gry (różnicę między zyskiem pierwszego i drugiego gracza).

Symulując wprost reguły gry, dostajemy algorytm działający w czasie $\text{[math]}$ Wypełniamy kwadratową tablicę, gdzie $\text{[math]}$ oznacza wynik gry dla ciągu monet na pozycjach o numerach $\text{[math]}$ (zatem $\text{[math]}$ jest odpowiedzią do zadania). Jeśli pominiemy warunki brzegowe, rekurencja będzie następująca:

display-math

(*)

Istnieje jednak efektywniejsze rozwiązanie. Załóżmy najpierw, że $\text{[math]}$ jest nieparzyste. Oznaczmy sumę nominałów monet na pozycjach nieparzystych oraz parzystych przez

display-math

Zauważmy, że pierwszy gracz ma strategię, która pozwala mu na zabranie wszystkich monet na pozycjach nieparzystych (niezależnie od ruchów drugiego gracza – w swoim pierwszym ruchu zabiera dwie monety, a w każdym kolejnym ruchu kopiuje ostatni ruch drugiego gracza). Gwarantuje mu to uzyskanie wyniku nie mniejszego niż $\text{[math]}$ Z kolei gracz drugi ma strategię, która pozwala mu na zabranie wszystkich monet na pozycjach parzystych (również kopiuje ruchy przeciwnika), co gwarantuje mu uzyskanie wyniku nie mniejszego niż $\text{[math]}$ Zatem obaj gracze uzyskają właśnie tyle, a wynikiem gry będzie $\text{[math]}$

Dla $\text{[math]}$ parzystego nie widać, jak to zrobić równie prosto. Zatem pozostaje nam skorzystać ze wzoru $\text{[math]}$ Ograniczymy się jednak do wyznaczenia wartości $\text{[math]}$ dla $\text{[math]}$ Zauważmy, że przy obliczaniu każdej z nich pierwszy wyraz pod maksimum jest również tej postaci, natomiast dwa pozostałe dotyczą fragmentów długości nieparzystej, z którymi umiemy już sobie łatwo radzić. Rzeczywiście, jeśli stablicujemy sumy prefiksowe ciągu z naprzemiennym znakiem, możemy obliczyć wartość gry dla dowolnego takiego fragmentu w czasie stałym. Ostatecznie otrzymujemy rozwiązanie o złożoności czasowej $\text{[math]}$

Zadanie 2 (Podatek). Dany jest graf nieskierowany $\text{[math]}$ reprezentujący sieć dróg pomiędzy miastami. Każda droga ma przypisaną stawkę podatku. Jadąc z miasta do miasta, musimy w każdym mieście pośrednim uiścić opłatę równą maksimum ze stawki podatku dla drogi, którą wjechaliśmy do miasta, i dla drogi, którą z miasta wyjedziemy. Dla miasta pierwszego i ostatniego rozważamy tylko jedną stawkę. Przykładowo, jadąc trasą $\text{[math]}$ jeśli przez $\text{[math]}$ oznaczymy stawkę podatku na drodze pomiędzy $\text{[math]}$ a $\text{[math]}$ zapłacimy

display-math

Należy podać minimalną opłatę przejazdu pomiędzy dwoma ustalonymi miastami.

Skorzystamy ze wzoru

display-math

Możemy wtedy zapisać dwukrotność opłaty, którą uiścimy w naszym przykładzie, jako

$2s1 +(s1 + s2 + s1− s2 ) +(s2 +s3 + s2− s3 )+ 2s3 = = 2(s + s + s) + 0 −s + s − s + s − s + s − 0 . 1 2 3 1 1 2 2 3 3$

Tworzymy teraz nowy graf

\text{[math]}

Dla każdego wierzchołka

\text{[math]}

z grafu

\text{[math]}

do którego wchodzą krawędzie o wagach

\text{[math]}

tworzymy w grafie

\text{[math]}

wierzchołki

\text{[math]}

\text{[math]}

\text{[math]}

oraz łączymy

\text{[math]}

\text{[math]}

krawędzią o wadze

\text{[math]}

Ponadto, dla każdej krawędzi o wadze

\text{[math]}

łączącej w

\text{[math]}

wierzchołki

\text{[math]}

\text{[math]}

dodajemy w

\text{[math]}

krawędź o wadze

\text{[math]}

pomiędzy wierzchołkami

\text{[math]}

\text{[math]}

Pozostaje zauważyć istnienie bijekcji pomiędzy ścieżkami z $\text{[math]}$ do $\text{[math]}$ w grafie $\text{[math]}$ a ścieżkami z $\text{[math]}$ do $\text{[math]}$ w grafie $\text{[math]}$ w której dwukrotność opłaty za ścieżkę w $\text{[math]}$ jest równa zwykłej wadze ścieżki w $\text{[math]}$ Graf $\text{[math]}$ ma $\text{[math]}$ wierzchołków i $\text{[math]}$ krawędzi, więc uruchomienie na nim algorytmu Dijkstry zajmie czas $\text{[math]}$