20684. Czary Tadeusza [CZRTAD]

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

Skrócony opis problemu:

Dla danego ciągu liczb $a$ o długości $n$ wyznacz najmniejszą taką liczbę $x$, że z podanego ciągu można zrobić ciąg rosnący odejmując lub dodając do każdego wyrazu ciągu maksymalnie $x$.

Rozwiązanie:

Wyjściem w zadaniu jest 1 liczba. Musimy ją zminimalizować.W takich zadaniach sprawdza się wyszukiwanie binarne po wyniku.

A więc na początku ustawiamy sobie przedział, w którym będziemy szukać naszego wyniku. Maksymalne wartości wyrazów ciągu wynoszą w zadaniu $10^9$, więc przyjmiemy początek przedziału jako $l = 0$, a koniec właśnie jako $r = 10^9$. Następnie obliczamy środek przedziału $m$ i sprawdzamy czy da się dla niego osiągnąć ciąg rosnący odejmując i dodając maksymalnie $m$ do elementów ciągu. Jeśli się da, to znaczy, że możemy ustawić $r = m$, bo interesuje nas najmniejsza wartość, dla której się da (więc skoro dla $m$ się da, to ignorujemy wartości większe od $m$). Jeśli jednak się nie da, to ustawiamy $l = m+1$, bo nie interesują nas wartości, dla których się nie da (a więc $l$ też nie). Powtarzamy te operacje aż $l = r$.

Ale żeby ów algorytm był wystarczająco efektywny, musielibyśmy umieć szybko sprawdzić czy dla danego $m$ ciąg może być modyfikowany na rosnący. No i okazuje się, że da się to zrobić liniowo, czyli przechodząc każdy element tylko raz. Gdy chcemy jedynie sprawdzić czy możemy stworzyć ciąg rosnący dla konkretnej (nie niewiadomej) liczby, to możemy wykorzystać myślenie zachłanne.

A zatem, idąc od lewej, minimalizujemy jak się da wartość kolejnych wyrazów ciągu. Tak więc pierwszy element od razu pomniejszamy o $m$ i ustawiamy zmienną $last = a_0-m$ (numerując wyrazy od 0). Od kolejnego też odejmujemy $m$? Ano niekoniecznie. Może się bowiem okazać, że po zmniejszeniu $a_i$ będzie on mniejszy lub równy poprzedniemu (czyli zmiennej $last$). To jednak nie problem - jeśli dany element jest większy od $last$, ale po odjęciu od niego $m$ jest mniejszy lub równy $last$ to po prostu ustawiamy jego wartość na najmniejszą możliwą, czyli $last + 1$. A więc robimy wtedy $last++$. Możliwe jest jednak, że dany element $a_i$ będzie większy od $last$. Co możemy wtedy zrobić? Ano możemy przecież do niego dodać $m$. A zatem, sprawdzamy ile będzie wynosiło $a_i + m$. Jeśli będzie większe od $a_{i-1}$, to po prostu zwiększamy $last$ o 1, jak poprzednio - chcemy bowiem mieć jak najmniejszy element $last$, więc dodamy tylko tyle do $a_i$, żeby przekroczył $last$. Jeśli jednak $a_i + m$ będzie nadal mniejsze lub równe $last$, to znaczy, że nie da rady zmodyfikować ciągu $a$, żeby był rosnący dla tak małego $m$.

A zatem, podsumowując:

• od pierwszego elementu odejmujemy $m$
• jeżeli po odjęciu od $a_i$ liczby $m$ będzie ona większa od $last$ to odejmujemy właśnie tyle, bo jest to najwięcej na ile możemy sobie pozwolić
• jeżeli po odjęciu od $a_i$ liczby $m$ będzie ona mniejsza lub równa $last$ to znaczy, że za dużo odjęliśmy, więc ustawiamy $last = last+1$
• jeżeli $a_i \le a_{i-1}$ i po dodaniu $m$ otrzymamy liczbę większą niż $a_{i-1}$ to ustawiamy znów $last = last+1$
• jeżeli $a_i \le a_{i-1}$ i po dodaniu $m$ liczba ta będzie nadal mniejsza lub równa $a_{i-1}$ to kończymy pętlę z rezultatem negatywnym - nie udało się uzyskać ciągu rosnącego dla tak małego $m$

Złożoność: $O\left(n \cdot \log_2 x\right)$, bo dla każdego $m$ wykonujemy pesymistycznie około $n$ operacji (jeśli nie przerwiemy pętli). A takich $m$ będzie $log_2 x$, bo na początku mamy przedział o długości $x$, potem $\frac{x}{2}$, potem $\frac{x}{4}$, itd. Tak więc nasza złożoność zależy od maksymalnego wyniku, jaki możemy osiągnąć. Przyjąłem, że jest to $10^9$.

Algorytm:

int main()
{
        int n, l = 1, r = 1000000000, m, ok, last, tab[10000009];

        get(n, tab);
        while(l < r)
        {
                m = l+r>>1; ok = 1; last = *tab-m;
                for(int i = 1; i < n; ++i) //
                {
                        if(tab[i]-m > last)
                                last = tab[i]-m;
                        else if(tab[i] > last || tab[i]+m > last)
                                ++last;
                        else
                        {
                                ok = 0;
                                break;
                        }
                }
                if(ok)
                        r = m;
                else
                        l = m+1;
        }
        print(a);
}

Optymalizacja:
A co jeśli maksymalny wynik z testów jest mniejszy niż miliard? Moglibyśmy wtedy zmniejszyć $x$ w logarytmie. Ale jak to sprawdzić? Ano znów wyszukiwaniem binarnym. Spróbujmy zgłosić program, w którym $r = 5 \cdot 10^8$, czyli równy połowie poprzedniego przedziału. Jeśli dostaniemy AC to znaczy, że możemy dalej zmniejszać $r$. Jeśli WA, to znaczy, że musimy go zwiększyć. Tym sposobem dojdziemy do minimalnej wartości $r$, która da nam AC.