4. Ťahanie Kalerábu vzorové riešenie

10 12
1 3 5 7 9 2 4 8 12 10

4

6 5
1 2 3 4 5 4

6

Pomalý bruteforce

Tento príklad vieme spraviť celkom jednoducho v exponenciálnom čase. Pôjdeme od začiatku cez všetky čísla, a po každom čísle sa rozvetvíme na dve možnosti: s použitím Adama a bez použitia. Ak Adama použijeme, dáme mu silu o jedna väčšiu, ako je naše aktuálne číslo, a v tejto vetve ho už použiť nemôžeme. Takto vieme prejsť všetky možnosti použitia Adama a stačí si nám zapamätať najdlhšiu takúto vetvu. Takéto riešenie bude mať časovú zložitosť \(O(2^N)\), pretože na každom čísle musíme prejsť cez dve vetvy. Dajú sa tu rôzne veci zoptimalizovať, avšak zložitosť bude stále \(O(2^N)\), a takéto riešenie bude teda veľmi pomalé.

Lepší bruteforce

Čo ak by sme si pre každého človeka v rade pamätali dve čísla? Prvé číslo bude vyjadrovať, koľko ľudí je za ním takých, že spolu tvoria reťaz, ktorá spĺňa naše pravidlá. Toto číslo si označíme písmenom \(A\). Druhé číslo bude vyjadrovať to isté, až na to, že v nejakom momente je v tomto rade aj Adam. Toto číslo označíme ako \(B\). Budeme takto prechádzať cez všetkých ľudí. Pre každého nového človeka nájdeme posledného človeka v rade, ktorý je o jedna slabší a človeka, ktorý je o dva slabší. Novému človeku nastavíme číslo \(A\) na silu človeka o 1 slabšieho plus jedna, pretože sa pridal do radu. Číslo \(B\) je troška komplikovanejšie.

Číslo \(B\) má dve možnosti: buď to môže byť číslo \(B\) človeka o jedna slabšieho plus jedna alebo to môže byť číslo \(A\) človeka o dva slabšieho plus dva. Druhá možnosť vyjadruje možnosť, kde sme Adama doteraz nepoužili a až teraz sme ho vsunuli do radu. Takto prejdeme cez všetkých ľudí a riešenie je najväčšie číslo s použitím Adama, pretože to vyjadruje Adam vždy predĺži rad o jedna. Samozrejme sa môže stať, že v rade nie je človek o jedna alebo o dva slabší. V takom prípade je tento človek začiatkom reťaze a začne teda od nuly.

Toto riešenie má kvadratickú časovú zložitosť v závislosti od počtu ľudí, pretože pri pridaní každého človeka musíme v najhoršom prípade prejsť všetkých predchádzajúcich ľudí, teda je časová zložitosť \(O(N \cdot N) = O(N^2)\) teda kvadratická. Pamäťová zložitosť je lineárna od počtu ľudí (\(O(N)\)), keďže si pre každého človeka pamätáme dve čísla.

Optimálne riešenie

Od lepšieho bruteforcu k optimálnemu riešeniu je už len jeden krok. Namiesto toho, aby sme si pamätali tieto údaje pre každého človeka, budeme si tieto údaje pamätať pre každú možnú silu človeka. Teraz namiesto toho, aby sme prehľadávali posledného človeka s nejakou silou, stačí nám použiť hľadanú silu ako index poľa, ktorú vieme nájsť v konštantnom čase. Polia vieme na začiatku naplniť nasledovne: pole reprezentujúce rad bez Adama naplníme nulami, pretože Adama sme nepoužili a človek, ktorý hľadá takúto silu bude prvý v tomto rade. Pole reprezentujúce čísla \(B\) naplníme jednotkami, pretože v tomto prípade použijeme Adama hneď na začiatku.

Prečo nám netreba max()

Môže sa nám stať, že v rade stoja dvaja alebo viacerí ľudia s rovnakou silou. Keď vyrátame prvého takého človeka, jednoducho uložíme čísla do poľa. Ak nájdeme ďalšieho človeka s takouto silou, vieme, že teraz pracujeme s číslami, ktoré sú rovnaké alebo lepšie, ako keď sme túto silu rátali naposledy, pretože teraz pracujeme s nadmnožinou čísel s akou sme pracovali minule. Táto optimalizácia nebola potrebná na dosiahnutie plného počtu bodov, avšak je to zaujímavé pozorovanie, ktoré môže byť pre vás v budúcnosti užitočné.

def sol(nums, biggest):
    values_without_adam = [0 for n in range(biggest+1)]
    values_with_adam = [1 for n in range(biggest+1)]

    for ind, n in enumerate(nums):
        one_lower = n-1
        two_lower = n-2

        without_one = values_without_adam[one_lower]
        without_two = values_without_adam[two_lower]
        with_one = values_with_adam[one_lower]

        values_without_adam[n] = without_one + 1
        values_with_adam[n] = max(with_one + 1, without_two + 2)

    return max(values_with_adam + values_without_adam)


n_people, biggest = list(map(int, input().split()))
answer = sol(list(map(int, input().split())), biggest)
print(answer)

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    long long n, m;
    cin >> n >> m;
    m++;

    int without_adam[m];
    int with_adam[m];


    for (int i = 0; i < m; i++) {
        without_adam[i] = 0;
        with_adam[i] = 1;
    }

    int sol = 1;
    long long current;

    for (int i = 0; i < n; i++) {
        cin >> current;

        without_adam[current] = without_adam[current-1]+1;
        with_adam[current+1] = without_adam[current-1] + 2;
        with_adam[current] = with_adam[current-1] + 1;

        sol = max({sol, without_adam[current], with_adam[current+1], with_adam[current]});
    }

    cout << sol << endl;
    return 0;
}