1054. Róże przed domami [ROZ]

Zadanie:
https://pl.spoj.com/problems/ROZ

Skrócony opis problemu:

Mamy $n$ trójek liczb naturalnych i naszym zadaniem jest wybrać taką drogę od pierwszej do ostatniej trójki, żeby suma liczb, przez które przejdziemy była najmniejsza, ale przy warunku, że jeśli weźmiemy w którymś kroku 2-gą liczbę, to w następnym możemy wziąć tylko 1-szą lub 3-cią.

Np. dla $n=5$ i trójek:

8 9 9

0 9 9

3 9 4

8 4 1

8 4 1

Najkrótsza droga to 9-0-4-4-1. Jeśli jest więcej dróg, to nieważne, którą wybierzemy, bo wypisać musimy tylko sumę. Wynik w tym przypadku to zatem 18.

Rozwiązanie naiwne:

Możemy wyznaczyć wszystkie drogi i wybrać tę o najmniejszej sumie.

Złożoność: $O(2^n)$, bo mamy $3 \cdot 2^n$ dróg.

Rozwiązanie sprytniejsze:

Można potraktować nasze trójki jako graf ważony, nieskierowany. Każda z $3n$ liczb jest wierzchołkiem, a krawędziami są pary wierzchołków między kolejnymi trójkami, wyłączywszy liczby znajdujące się pod sobą. Krawędzi będzie zatem 24 - są 4 pary trójek, a w każdej każda z 3 liczb ma krawędź z 2 nienaprzeciwległymi - $4 \cdot 3 \cdot 2 = 24$. W ogólności ilość krawędzi to $(n-1) \cdot 6 = 6n-6$. Ilość krawędzi nie będzie jednak istotna - piszę to tylko jako ciekawostkę oraz by ponownie pokazać czym jest krawędź. Krawędzie, jak już wspominałem, mają wagi. Wagą krawędzi jest suma liczb będących jej końcami. Skoro już mamy nasz graf ważony to możemy przedefiniować nasze zadanie. Chcemy znaleźć najkrótszą ścieżkę między dowolnym wierzchołkiem pierwszej trójki a dowolnym wierzchołkiem ostatniej trójki. Wystarczy więc, że policzymy $3 \cdot 3 = 9$ najkrótszych ścieżek i wybierzemy z niej najkrótszą. Możemy to zrobić korzystając z algorytmu Dijkstry (lub Bellmana-Forda).

Złożoność: $O(n \log n)$. Złożoność może również wynosić $O(n^2)$. Wszystko zależy jaki kontener zaimplementujemy w algorytmie Dijkstry. Dla tablicy otrzymamy złożoność $O(n^2)$, dla kolejki priorytetowej opartej na kopcu: $O(m \log n)$, gdzie $m$ to liczba krawędzi (pokazałem wcześniej, że $m=6n-6$, więc $O(m \log n) = O(n \log n)$), albo na kopcu Fibonacciego: $O(n \log n)$.

Rozwiązanie najsprytniejsze:

Możemy trzymać sobie 3 zmienne, w których będą stare wartości i 3, w których będą nowe. No więc powiedzmy, że w zmiennych $x$, $y$ i $z$ są 3 pierwsze wartości. A więc dla powyższych danych: $x=8, y=9, z=9$. Dostajemy nową trójkę: $a=0, b=9, c=9$ i rozpatrujemy sobie najpierw $a$ zakładając, że je wybieramy na pewno. No więc skoro mamy $a$, bo możemy wybrać tylko $y$ lub $z$. Obie są równe 9, więc wynik to w obu wypadkach 0+9=9. Teraz zajmijmy się $b$. Mamy do wyboru $x$ i $z$. W tym wypadku wybieramy mniejszą liczbę, a więc 8. Wynik dla $b$ to zatem 8+9=17. No i $c$. Taka sama sytuacja: $x+9=8+9=17$. Gdybyśmy mieli tylko te 2 trójki, to wybieramy najmniejszą spośród: {9, 17, 17}. Pójdźmy jednak dalej. $a=3, b=9, c=4, x=9, y=17, z=17$. Zwróćmy uwagę, że zamieniliśmy stare wartości na sumy, które otrzymaliśmy. No i ponownie: dla $a$ wybieramy $\min{y=17,z=17}=17$, dla $b$ 9, dla $c$ 9. $a=8, b=4, c=1, x=3+17=20, y=9+9=18, z=4+9=13$. Dla $a$ 13, dla $b$ 13, dla $c$ 18. $a=8, b=4, c=1, x=8+13=21, y=4+13=17, z=1+19=19$. Dla $a$ 17, dla $b$ 19, dla $c$ 17. Ostatecznie więc: $x=8+17=25, y=4+19=23, z=1+17=18$. Wynik ostateczny, to: $\min{25,23,18}=18$.

Złożoność: $O(n)$, bo przechodzimy $n$ trójek i wykonujemy stałą ilość operacji, dla każdej z nich.

Ostateczny algorytm:

int main()
{
    int n, a, b, c, x, y, z;
    int d, e, f; // zmienne tymczasowe

    get(n, x, y, z);
    while(--n) // --n, a nie n--, bo wczytaliśmy pierwszą trójkę poza pętlą
    {
            get(a, b, c);
            d = a+min(y, z); e = b+min(x, z); f = c+min(x, y);
            x = d; y = e; z = f; // aktualizuj x, y, z
    }
    print(min(x, y, z));
}