Algortym Gąsienicy

Motywacja algorytmu

Wyobraźmy sobie, że posiadamy budkę z lodami. Mamy też do dyspozycji analizę sprzedaży z ostatnich kilku lat, która pokazuje nam, ile lodów sprzedamy każdego dnia, zobacz Rysunek 1a.

Oczywiście liczba sprzedanych lodów każdego dnia nie może być ujemna, więc w tym zadaniu zakładamy, że wszystkie liczby są nieujemne. To założenie będzie bardzo przydatne w dalszej części lekcji.

Teraz zastanawiamy się ile najwięcej lodów możemy sprzedać. Utrzymanie budki każdego dnia może być nieopłacalne, gdyż musimy opłacić prąd, wodę, wynagrodzenie pracowników i inne koszty. Dodatkowo zwijanie budki i ponowne jej rozstawianie również sporo kosztuje.

Dlatego chcemy znaleźć najkrótszy, spójny okres, w którym sprzedamy co najmniej $M$ lodów, zobacz Rysunek 1b.

Dla uproszczenia przyjmijmy w tej lekcji, że $M=10$.

Rozwiązania brutalne

Na początku warto zastanowić się nad prostszymi sposobami rozwiązania tego zadania.

Pierwsze rozwiązanie

Możemy sprawdzić każdy możliwy przedział $[l,r]$, w którym $1 \le l \le r \le n$.

Dla każdego takiego przedziału liczymy jego sumę, jeśli wynosi co najmniej $10$ to aktualizujemy wynik uwzgledniająć nową długość $r-l+1$. Na końcu wybieramy najmniejszą taką długość.

To rozwiązanie jest poprawne, ale bardzo wolne. Dlaczego? Bo wszystkich przedziałów jest około $n^2$, a policzenie sumy w jednym z nich może wymagać przejrzenia nawet $n$ elementów. Daje to łącznie około $n^3$ operacji.

To zdecydowanie za dużo dla dużych danych.

Drugie rozwiązanie

Ustalmy lewy koniec $l$ na $6$ i zastanówmy się dla jakich końców $r$, suma przedziału $[6, r]$ jest mniejsza niż $10$, a dla jakich jest co najmniej $10$.

Ponieważ wszystkie liczby są nieujemne, to widzimy pewną monotoniczność. Najpierw występują same czerwone pola - dla tych końców suma jest zbyt mała. Następnie pojawia się pierwsze zielone pole - dla tego końca suma jest co najmniej $10$. Wszystkie kolejne pola są również zielone.

Dla początku $l=6$ interesuje nas zatem najbliższe zielone pole. To właśnie jest optymalny prawy koniec dla lewego końca $l=6$.

A zatem możemy przyspieszyć nasze rozwiązanie. Ustalamy lewy koniec $l$ a następnie przesuwamy prawy koniec $r$, zaczynając od $l$, aż znajdziemy pierwszy przedział, którego suma jest co najmniej $10$. Dla ustalonego $l$ wykonamy co najwyżej $n$ operacji.

Ponieważ musimy sprawdzić wszystkie możliwe lewe końce, to w sumie wykonamy około $n^2$ operacji.

To nadal za dużo, ale już coraz lepiej rozumiemy jak wygląda struktura rozwiązania.

Obserwacja

Zanim przejdziemy do właściwego algorytmu, zauważmy jedną ważną rzecz.

Dla każdego lewego końca, zaznaczmy optymalny prawy koniec - czyli najbliższy koniec, dla którego suma wynosi co najmniej $10$; zobacz Rysunek 3.

Na rysunku widać, że gdy lewy koniec przesuwa się w prawo, prawy koniec może przesunać się tylko w prawo. Czasami zostaje w tym samym miejscu, ale nigdy się nie cofa.

Obserwacja Jeśli znamy najlepszy prawy koniec dla lewego końca $l$, to dla lewego końca $l+1$ najlepszy prawy koniec — o ile istnieje — nigdy nie przesunie się w lewo. Może zostać w tym samym miejscu albo przesunąć się w prawo.

Intuicja jest prosta: jeśli przesuwamy lewy koniec w prawo, to z przedziału usuwamy jeden element. Przez to suma może się tylko zmniejszyć.

Właściwy algorytm

Przejdźmy teraz do właściwego algorytmu, czyli algorytmu gąsienicy, zwanego też metodą dwóch wskaźników.

W tym algorytmie będziemy utrzymywać dwa wskaźniki: lewy koniec $l$ i prawy koniec $r$. Dodatkowo utrzymujemy też zmmienną $\mathit{aktu\_suma}$, czyli sumę aktualnego przedziału.

Na początku ustawiamy lewy koniec $l=1$ i przesuwamy prawy koniec w prawo, aż suma wyniesie co najmniej $10$; zobacz Rysunek 4. Ponieważ w każdym kroku przesuamy prawy koniec o jeden w prawo, łatwo możemy aktualizowac sumę $\mathit{aktu\_suma}$.

Gdy przedział $[l,r]$ osiągnie sumę $10$, zapamiętujemy jego długość. Następnie zwiększamy lewy koniec do $l=2$; zobacz Rysunek 5. Zwiększając lewy koniec, musimy pamiętać o aktualizacji sumy $\mathit{aktu\_suma}$, bo z przedziału usuwamy jeden element.

Z poprzedniej obserwacji wiemy, że nowego prawego końca nie musimy szukać od początku. Możemy zacząć od miejsca, w którym zatrzymaliśmy się wcześniej; zobacz Rysunek 6.

Jesli suma przedziału $[l,r]$ spadnie poniżej $10$, to przesuwamy prawy koniec w prawo, aż suma znów osiągnie co najmniej $10$.

Zauważmy, że w tym algorytmie, oba wskaźniki poruszają się tylko w prawo. To będzie ważne w następnej części przy analizowaniu złożoności.

Złożoność

Teraz najważniejsze pytanie: dlaczego to rozwiązanie jest istotnie szybsze od dwóch poprzednich?

Spójrzmy osobno na oba wskaźniki. Lewy koniec $l$ przesuwa się w prawo co najwyżej $n$ razy. Prawy koniec $r$ zaczyna od $0$, nie przekracza $n$ i nigdy się nie cofa, więc również przesuwa się w prawo najwyżej $n$ razy.

Nawet jeśli dla jednego, konkretnego lewego końca, prawy koniec przesunie się wiele razy, to łącznie w całym algorytmie wykona najwyżej $n$ przesunięć.

A więc wszystkich przesunięć jest łącznie co najwyżej $2n$. Dlatego całe rozwiązanie działa w czasie $\mathcal{O}(n)$.

Typowe błędy

1. Pominięcie warunku $r<n$ w pętli $\mathit{while}$. Bez tego prawy koniec może wyjść poza ciąg.

2. Brak uwzględnienia zdegenerowanych przedziałów (czyli takich, że $r < l$), które mogą się pojawić w rozwiązaniu.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    long long M;

    cin >> n >> M;
    vector<int> lody(n+1, 0);
    for(int i = 1; i <= n; i++){
        cin >> lody[i];
    }

    int res = n+1;
    int l, r = 1;
    long long aktu_suma = lody[1];

    for(l = 1; l <= n; l++){

        if( r < l ){
            r = l;
            aktu_suma = lody[l];
        }

        while(r < n && aktu_suma < M){
            r++;
            aktu_suma += lody[r];
        }

        if( aktu_suma >= M ) res = min(res, r-l+1);
        aktu_suma -= lody[l];

    }

    if( res == n+1 ) cout << "-1\n";
    else             cout << res << "\n";

    return 0;
}