Dwa wskaźniki to monotoniczność w przebraniu.

Większość wyjaśnień techniki dwóch wskaźników uczy cię wzorca. Lewy wskaźnik tutaj, prawy tam, przesuń jeden, gdy zachodzi jakiś warunek. Zapamiętaj szablon i go stosuj.

To działa, dopóki zadanie nie zmieni się nieznacznie i nie jesteś w stanie stwierdzić, czy dwa wskaźniki się tu sprawdzą. Wtedy zaczynasz zgadywać.

Oto podstawowa idea, którą pomija większość wyjaśnień: technika dwóch wskaźników działa wtedy, gdy istotna właściwość okna jest monotoniczna względem ruchu wskaźników. Przesunięcie prawego wskaźnika do przodu może tylko zwiększyć tę właściwość. Przesunięcie lewego wskaźnika do przodu może ją tylko zmniejszyć. To dokładnie ten sam warunek, który sprawia, że wyszukiwanie binarne jest poprawne. Gdy to zobaczysz, pytanie „dwa wskaźniki czy wyszukiwanie binarne?” przestaje być rzutem monetą.

Co monotoniczność właściwie tutaj oznacza

Weźmy klasyczny przykład: znajdź dwa indeksy i < j w posortowanej tablicy takie, że a[i] + a[j] = target.

Umieść jeden wskaźnik na lewym końcu, a drugi na prawym. Suma wynosi a[l] + a[r]. Jeśli przesuniesz r w lewo, suma maleje. Jeśli przesuniesz l w prawo, suma rośnie. Suma jest monotoniczna względem ruchu obu wskaźników. Dlatego w każdym kroku możesz robić postęp: jeśli suma jest za duża, przesuń r w lewo; jeśli za mała, przesuń l w prawo.

int l = 0, r = n - 1;
while (l < r) {
    int s = a[l] + a[r];
    if (s == target) { /* found */ break; }
    else if (s < target) l++;
    else r--;
}

Kod ma pięć linijek. Powód, dla którego działa, mieści się w jednym zdaniu: suma jest monotoniczna względem l i monotoniczna względem r.

Okno przesuwne to ta sama idea

Najdłuższy podciąg z co najwyżej K różnymi znakami. To dwa wskaźniki na napisie, często nazywane oknem przesuwnym. Właściwością jest tutaj liczba różnych znaków w [l, r]. Gdy r rośnie, liczba ta może tylko zostać taka sama lub wzrosnąć. Gdy l rośnie, może ona tylko zostać taka sama lub zmaleć. Monotoniczna w obu kierunkach.

int l = 0, best = 0;
map<char, int> cnt;
for (int r = 0; r < n; r++) {
    cnt[s[r]]++;
    while ((int)cnt.size() > k) {
        cnt[s[l]]--;
        if (cnt[s[l]] == 0) cnt.erase(s[l]);
        l++;
    }
    best = max(best, r - l + 1);
}

Ta sama struktura. Pętla while przesuwa l, dopóki właściwość nie zostanie przywrócona. Jest to poprawne, ponieważ zwiększanie l może tylko zmniejszyć liczbę różnych znaków — nie może jej pogorszyć.

Najmniejszy podciąg o sumie co najmniej S

Właściwością jest tutaj suma okna [l, r]. Monotoniczna względem r (przesunięcie w prawo dodaje dodatni element, przy założeniu że wszystkie elementy są dodatnie), monotoniczna względem l (przesunięcie w lewo usuwa element). Algorytm: rozszerzaj r, dopóki suma nie osiągnie S, a następnie zmniejszaj l tak daleko, jak to możliwe, dopóki suma pozostaje powyżej S, zapisując długość okna.

Zwróć uwagę na założenie: wszystkie elementy dodatnie. Właśnie stąd bierze się monotoniczność. Jeśli elementy mogą być ujemne, zmniejszanie l może obniżyć sumę, a właściwość przestaje być monotoniczna. Dwa wskaźniki dałyby wtedy błędne odpowiedzi, i to bez żadnych komunikatów o błędzie. Wrócę jeszcze do tego.

Kiedy technika cicho się psuje

To jest ta część, która daje się uczniom we znaki. Dwa wskaźniki nie „wysypują się”, gdy założenie monotoniczności zostaje naruszone. Po prostu dają błędne odpowiedzi, a jeśli twoje testy są słabe, nawet tego nie zauważysz.

Załóżmy, że masz tablicę z ujemnymi elementami i szukasz najkrótszego podciągu o sumie co najmniej S. Zmniejszanie l może obniżyć sumę poniżej S. Ale twoja pętla while o tym nie wie — po prostu sprawdza warunek i się zatrzymuje. Wynik wygląda wiarygodnie, a jest błędny.

Pytanie, które trzeba sobie zadać przed napisaniem rozwiązania z dwoma wskaźnikami: jaka jest właściwość mojego okna i czy jest ona rzeczywiście monotoniczna przy ruchu każdego wskaźnika? Zapisz to jawnie. Jeśli nie potrafisz określić właściwości monotonicznej, nie możesz zweryfikować, czy algorytm jest poprawny.

Gdy potrafisz nazwać właściwość monotoniczną, ruch wskaźników pisze się sam.

Dwa wskaźniki kontra wyszukiwanie binarne

Obie techniki wymagają monotoniczności. Różnica polega na koszcie. Wyszukiwanie binarne na funkcji f(x) wymaga obliczenia f(x) dla pojedynczego punktu w O(log n) rundach — jeśli obliczenie f jest tanie (O(1) lub O(log n)), wyszukiwanie binarne sprawdza się dobrze. Dwa wskaźniki amortyzują pracę inaczej: każdy wskaźnik przesuwa się łącznie o co najwyżej n kroków, więc łączna złożoność wynosi O(n), niezależnie od tego, co robisz w każdym kroku, o ile jest to O(1).

Jeśli twoja właściwość jest monotoniczna i możesz ją utrzymywać przyrostowo w miarę wzrostu lub kurczenia się okna, dwa wskaźniki dają ci O(n). Jeśli utrzymywanie przyrostowe jest kosztowne, ale obliczenie jej od zera w ustalonym punkcie jest szybkie, wyszukiwanie binarne jest czystszym rozwiązaniem. Często działają obie metody; dwa wskaźniki zwykle mają mniejszą stałą.

Wzorzec dwóch wskaźników to nie sztuczka do zapamiętania. To konsekwencja jednej właściwości. Znajdź tę właściwość, sprawdź, czy jest monotoniczna, a reszta kodu wynika z tego bezpośrednio.

Rozwiąż teraz te zadania

Trzy zadania, które polecam zaraz po lekturze tego artykułu. Każde z nich zmusza cię do nazwania właściwości monotonicznej, zanim kod zadziała:

• Codeforces 676C — Vasya and String. Zarówno dwa wskaźniki, jak i wyszukiwanie binarne po odpowiedzi są tu poprawne. Zdecyduj, które piszesz, i powiedz dlaczego — ta decyzja to cały ten artykuł w miniaturze.
• CSES 1660 — Subarray Sums I. Wszystkie elementy dodatnie. Czyste okno przesuwne; określ właściwość, a potem ją zaimplementuj.
• CSES 1661 — Subarray Sums II. Ta sama treść, ale dozwolone są liczby ujemne — a monotoniczność znika. Zauważ dokładnie, w którym miejscu rozumowanie z dwoma wskaźnikami się załamuje, a potem rozwiąż to w inny sposób.