20179. Jasio włamywacz po raz kolejny [AL_17_04]

Zadanie:
https://spoj.com/ALGOLIGA/problems/AL_17_04
https://pl.spoj.com/problems/AL_17_04

Skrócony opis problemu:

Mając $n$ liczb, które sumują się do $x$ należy sprawdzić czy da się wybrać takie, żeby zsumowały się do $\frac{x}{2}$.

Rozwiązanie naiwne:

Naiwne rozwiązanie to sprawdzenie wszystkich możliwości. W tym przypadku byłoby to sprawdzenie dla każdego podzbioru liczb czy sumuje się do $\frac{x}{2}$.

Złożoność: $O\left(2^n \cdot n\right)$, gdyż musielibyśmy sprawdzić wszystkie podzbiory o wielkościach od 1 do $n-1$, a jest ich $2^{n-1}$. Musielibyśmy także obliczyć sumę każdego z nich, co dałoby nam pesymistycznie $n-1$ operacji.

Rozwiązanie sprytne:

Możemy skorzystać z programowania dynamicznego. Zróbmy sobie zatem tablicę $dp$ o wielkości równej $\frac{x}{2}+1$. Dla $i$-tego elementu będziemy trzymali w nim 1, jeśli udało się nam go otrzymać z sumowania części z dotychczasowych liczb lub 0, w przeciwnym wypadku. Na początku więc wszystkie komórki mają 0, oprócz tej o indeksie 0, gdyż 0 możemy otrzymać nie sumując żadnych liczb. A zatem na weźmy na początku jedną liczbę - 7 - i ustawmy $dp[7] = 1$. Powiedzmy, że kolejna liczba to 3. Nie wystarczy jednak ustawić $dp[3] = 1$, gdyż możemy od tego momentu utworzyć również 7+3=10. Musimy więc przechodzić tablicę od końca i dla każdej komórki $i$, której wartość wynosi 1 musimy ustawiać $dp[i+3] = 1$, chyba że $i+3$ przekroczy $\frac{x}{2}$ - sumy większe od połowy $x$ nas bowiem nie obchodzą. A dlaczego mamy przechodzić od końca ową tablicę? Ano dlatego, że gdybyśmy przechodzili ją od początku to bralibyśmy daną liczbę pod uwagę kilka razy zamiast jednego razu. Np. najpierw zaktualizowalibyśmy $dp[0+3] = 1$, a następnie dla komórki o indeksie 3 zrobilibyśmy to samo, jako że jej wartość jest równa 1. Idąc od końca zmieniamy wartości tylko tych komórek, które już przeszliśmy i do których nie wrócimy.

Powtórzę jeszcze raz co nam daje owa tablica. Komórka o indeksie $i$ pokazuje nam czy da się stworzyć liczbę $i$ sumując przetworzone do tej pory liczby. Chcemy przetworzyć następną liczbę - $y$. Idziemy więc od końca tablicy i sprawdzamy czy któraś komórka ma wartość 1. Jeśli tak (przyjmijmy, że stanęliśmy na komórce $j$), to znaczy, że możemy uzyskać $j$, a więc możemy również uzyskać $y+j$. Oznaczamy więc $dp[y+j] = 1$ i idziemy dalej. Na końcu dojdziemy do 0 i robimy $dp[0+y] = 1$, gdyż możemy uzyskać także $y$ nie sumując jej z żadną liczbą. Pracę kończymy gdy przetworzymy wszystkie liczby z wejścia lub gdy osiągniemy $\frac{x}{2}$ (a więc gdy $dp\left[\frac{x}{2}\right] = 1$).

Optymalizacje:

Żeby nie komplikować, nie wspomniałem, że na początku wejścia jest jeszcze liczba $t$ oznaczająca liczbę przypadków w danym teście. Tak więc dla każdego testu trzeba by zerować tablicę $dp$. Można jednak zastosować sztuczkę, by nie tracić czasu na zerowanie tej tablicy. Wystarczy każdemu testowi przypisać kolejną liczbę naturalną: 1, 2, ... $t$. Będzie ona zastępowała nam w danym teście jedynkę, którą oznaczaliśmy czy daną liczbę da się otrzymać sumując część liczb z wejścia. Tak więc na początku testu nr 3 oznaczymy $dp[0] = 3$, a pozostałe, mniejsze od 3 wartości będziemy traktować jako zera. Tak więc dla testu nr 5 uda nam się otrzymać $\frac{x}{2}$ jeśli po przejściu wszystkich liczb $dp\left[\frac{x}{2}\right] = 5$.

Kolejnymi optymalizacjami jest wypisywanie od razu NIE jeśli suma wszystkich liczb jest nieparzysta lub gdy największa liczba przekracza połowę sumy wszystkich liczb.

Złożoność: $O\left(n \cdot \frac{x}{2}\right)$, gdyż dla każdej z $n$ liczb przechodzimy dokładnie $\frac{x}{2}$ komórek. Ograniczenie na $x$ w zadaniu to $10^5$, a na $n$ to $1000$, więc możemy oszacować złożoność jako $O\left(n^2 \sqrt n\right)$.

Algorytm:

int main()
{
        int t, n, i, j, sum, partsum, dp[50009], in[1009];
        
        get(t);
        while(t--)
        {
                get(n);
                partsum = sum = 0; dp[0] = t+1;
                for(i = 0; i < n; ++i)
                        get(in[i]),
                        sum += in[i];
                if(sum&1) // jeśli suma jest nieparzysta, to oczywiście od razu wypisujemy NIE
                {
                        puts("NIE");
                        continue;
                }
                sum >>= 1; // dzielimy sumę przez 2, żeby nie pisać ciągle sum/2
                for(i = 0; i < n; ++i)
                {
                        for(j = partsum > sum ? sum : partsum; j >= 0; --j) // dla każdej liczby od końca tablicy lub sumy wszystkich dotychczasowych liczb (jeśli ta suma jest mniejsza od końca tablicy)
                                if(dp[j] == t+1 && j+in[i] <= sum) // jeśli daną liczbę j da się utworzyć i jeśli powiększając tę liczbę o in[i] nie wyjdziemy poza tablicę
                                        dp[j+in[i]] = t+1; // oznaczamy, że możemy utworzyć również j+in[i]
                        if(dp[sum] == t+1) // jeśli da się utworzyć x/2 to kończymy, bo po co sprawdzać dalsze liczby
                                break;
                        partsum += in[i]; // zwiększamy dotychczasową sumę
                }
                puts(dp[sum] == t+1 ? "TAK" : "NIE");
        }
}