15290. Wakacje [AL_08_06]

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

Skrócony opis problemu:

Dla danych liczb $x$, $n$ ($x \le 10^4, n \le 100$) oraz $n$-elementowej tablicy wybrać z tablicy takie liczby, aby ich suma była $\ge x$ i przy tym była minimalna. Jeśli jest wiele takich podzbiorów danej tablicy to znaleźć najmniej liczny.

Rozwiązanie:

Można skorzystać z programowania dynamicznego. Tworzymy sobie tablicę $tab$ od 0 do $x$ i przypisujemy komórce 0 wartość 1, aby zaznaczyć, że umiemy "zbudować" z danych liczb wartość 0 (nie biorąc żadnej liczby). Pozostałe komórki mają wartość 0. Następnie dla każdej liczby $y_i$ idziemy od tyłu, od indeksu $x-1$ i jeśli napotkamy niezerową liczbę, to sprawdzamy wartość komórki o indeksie $x-1-j+y_i$, gdzie $j$ to ilość komórek, które przeszliśmy (na początku $j=0$). Jeśli jest ona większa o co najmniej 2 od komórki o indeksie $x-1-j$ to zamieniamy jej wartość na $tab[x-1-j]+1$. Innymi słowy, jeśli da się zbudować liczbę $x-1-j+y_i$ z mniejszej o przynajmniej 1 liczby elementów, to aktualizujemy wartość w $tab$ tej liczby.

Tak więc w $tab[i]$ znajduje się w danym momencie minimalna ilość elementów potrzebnych do zbudowania liczby $i$ (o wartości większej o 1, bo przypisaliśmy $tab[0]=1$, a 0 można zbudować z 0 elementów - wystarczy potem od całkowitego wyniku odjąć 1) lub 0 jeśli nie możemy w danej chwili zbudować liczby $i$. Zaczynamy natomiast od końca ($x-1$), aby mieć pewność, że nie wykorzystamy danej liczby 2 razy. Gdybyśmy bowiem zaczęli od początku to przy liczbie 5 mielibyśmy $tab[0]=1$, $tab[5]=2$, $tab[10]=3$, itd., a mamy tylko jedno 5.

Ostatnim szczegółem jest przypadek, gdy przekroczymy $x-1$. Wszystkie sumy, które są większe lub równe $x$ trzymamy pod indeksem $x$ i pamiętamy tylko jaka była najmniejsza liczba w tej komórce (powiedzmy w zmiennej $z$). $tab[x]$ aktualizujemy, jeśli nowa wartość będzie mniejsza od $z$ (bo to jest nasz priorytet) lub jeśli będzie jej równa i $tab[x]>tab[x-1-j+y_i]+1$.

Złożoność: $O(x \cdot n)$.

Przykład:
24 7
3 8 8 6 5 1 1
TODO ANIMACJA

Ostateczny algorytm:

int x, n, yi; // dane
int z = 1e9, i; // z to najmniejsza suma, większa od x
int tab[x+1]; // wypełnione zerami

tab[0] = 1;
while(n--)
{
    get(yi);
    for(i = x-1; i >= 0; --i)
        if(tab[i]) // jeśli da się zbudować liczbę i
            if(i+yi >= x && (i+yi < z || (i+yi == z && tab[i]+1 < tab[x]))) // jeśli i+yi przekracza x-1 i jest lepszym rozwiązaniem niż poprzednie
                z = i+yi, // zmień liczbę końcową
                tab[x] = tab[i]+1; // zmień ilość elementów potrzebnych do zbudowania tej liczby
            else if(i+yi < x && (!tab[i+yi] || tab[i+yi] > tab[i]+1)) // jeśli nie przekraczamy x-1 i mamy lepsze rozwiązanie niż poprzednie
                tab[i+yi] = tab[i]+1; // zmień liczbę elementów potrzebnych do zbudowania liczby i+yi
}
if(tab[x]) // jeśli da się zbudować liczbę x
    printf("%d %d\n", tab[x]-1, z);
else
    puts("NIE");

Optymalizacja:

Autorem tej optymalizacji jest narbej.

Możemy zauważyć, że nie musimy przechodzić całej tablicy $tab$ za każdym razem. Na początku wiemy przecież, że nie ma w niej elementów. Po dodaniu pierwszego elementu znów przejdziemy całą tablicę, żeby zaktualizować tylko 2 komórki. Jak to ominąć? Otóż możemy najpierw posortować niemalejąco nasze liczby z wejścia $y_i$, a następnie sprawdzać tylko tablicę od $s$ do 0, gdzie $s$ to suma wszystkich [posortowanych] $y_i$ z wejścia do danego momentu. Jak to działa? No więc zaczynając mamy $s=0$, jako że nie przetworzyliśmy żadnej liczby, więc dla najmniejszej liczby $a$ sprawdzamy tylko 0. Następnie dla drugiej najmniejszej liczby $b$ nie musimy sprawdzać przedziału $\left<x-1;a+1\right>$, bo wiemy, że nic tam nie ma. Sprawdzamy zatem przedział $\left<a;0\right>$, jako że po przetworzeniu pierwszej liczby $s=a$. Następnie zwiększamy $s$ o $b$ ($s=a+b$) i dla trzeciej liczby będziemy przetwarzać tylko przedział $\left<s;0\right>$.

W końcu nasze $s$ osiągnie $x-1$, więc będziemy musieli przeglądać całą tablicę. Jednak oszczędzimy zawsze kilka przejść.

Można również posunąć się o krok dalej i tablicować wszystkie komórki, w których są liczby większe od 0. Przy zmianie jakiejś komórki z 0 na 1 musielibyśmy wtedy dodawać indeks tej komórki np. do seta w czasie logarytmicznym, a następnie przechodzić go, aby zaczynać od komórek o największym indeksie. Złożoność będzie taka sama, jak w przypadku sortowania, a pominiemy największą możliwą ilość pustych komórek.

Złożoność: $O(x \cdot n + n \log n) = O((x + \log n)n)$.

Zaraz, zaraz! Przecież to większa złożoność niż poprzednia! Co to jest niby za optymalizacja z większą złożonością? Szczegół tkwi w rozmiarach $x$ i $n$. Jak widzimy na samej górze, $x$ jest znacznie większe od $n$. Sortowanie będzie nas zatem niewiele kosztować, a oszczędzimy na przejściach tablicy. W złożoności jest cały $x$, bo pesymistycznie i tak prędzej czy później $s$ osiągnie $x$. Okazuje się jednak, że ta optymalizacja daje lepszy czas. Nie jest to może optymalizacja na konkurs, ale w życiu gdy chcemy mieć najszybciej działający program musimy czasem wyjść poza samą złożoność.

Optymalizacja nr 2:

Autorem tej optymalizacji jest Mariusz Jakubowski.

Optymalizacja ta jest podobna do poprzedniej. Najpierw sortujemy liczby z wejścia, ale tym razem nierosnąco. Następnie każdą pozycję dodajemy nie do seta, tylko do listy albo tablicy (ja poniżej zastosowałem tablicę i nazwałem ją listą, bo mnie stać). Musimy jednak jakoś upewnić się, że każdą liczbę z wejścia weźmiemy pod uwagę tylko raz. Tak więc gdy dodamy nową liczbę do listy, to nie możemy jej brać pod uwagę w tej samej iteracji. Jak to rozwiązać? Ano dla tablicy możemy zapamiętać stary rozmiar i przeglądać tylko elementy do tego rozmiaru, a po przejściu całej pętli aktualizować ten rozmiar o ilość nowo-dodanych elementów. Dla listy z kolei możemy zapamiętać wskaźnik na jej koniec i jeśli go osiągniemy to wyjść z pętli i zaktualizować jej koniec.
Ale to nie koniec. Sortowanie również nam pomaga, bo zaczynamy od największych liczb, czyli od końca tablicy $tab$. No i musimy jeszcze zrobić tylko jedno - listę/tablicę przeglądać od końca. Dzięki tym 3 rzeczom mamy pewność, że każdy element weźmiemy pod uwagę tylko raz przy tworzeniu nowych elementów. Tylko sortowanie psuje nam lekko złożoność, ale w tej optymalizacji poruszamy się już po tablicy, a nie po secie, więc zamieniliśmy czas logarytmiczny na stały.

Złożoność:  $O(x \cdot n + n \log n) = O((x + \log n)n)$. Jak widać, asymptotyczna złożoność jest taka sama, jak w poprzedniej optymalizacji, ale przez zrezygnowanie z seta mamy kolejne przyspieszenie.

Ostateczny algorytm:

int main()
{
    int x, y, n, i, j, s, s2;
    int tab[10009], in[109], list[10009];

    tab[0] = 1;
    get(x, n);
    for(i = 0; i < n; ++i)
        get(in[i]);
    sort(in, in+n, greater<int>()); // sortuj nierosnąco
    y = 1e9; s = 1; list[0] = 0;
    for(j = 0; j < n; ++j) // dla każdego elementu
    {
        for(s2 = 0, i = s-1; i >= 0; --i) // przejdź wszystkie liczby, które da się utworzyć z poprzednich
            if(list[i]+in[j] >= x && (list[i]+in[j] < y || (list[i]+in[j] == y && tab[list[i]]+1 < tab[x])))
                y = list[i]+in[j],
                tab[x] = tab[list[i]]+1;
            else if(list[i]+in[j] < x && (!tab[list[i]+in[j]] || tab[list[i]+in[j]] > tab[list[i]]+1))
            {
                if(!tab[list[i]+in[j]]) // jeżeli da się stworzyć nową liczbę
                    list[s+s2++] = list[i]+in[j]; // dodaj ją do listy
                tab[list[i]+in[j]] = tab[list[i]]+1;
            }
        s += s2; // zaktualizuj rozmiar listy
    }
    if(tab[x])
        print(tab[x]-1, y);
    else
        puts("NIE");
}