Zadanie
Záhradník Adam mal veľmi úspešný rok. Zeleniny v jeho záhrade mu narástli do neuveriteľných rozmerov. Toto je síce pekné pri tekviciach, ktoré sa vďaka sezónnemu sviatku predajú veľmi rýchlo, ale pri istom type zeleniny to je problém. Napríklad taká repa, keď je veľká, ťažko sa zo zeme vyťahuje a Adam si na pomoc musel zavolať dedka, babku, sestru, mačku a myš. Takto sa im podarilo repu vytiahnuť, no majú ešte jeden väčší problém: masívny kaleráb, v zemi zakorenený tak pevne, že potrebujú ešte viac ľudí ako na repu. Na pomoc si teda zavolali susedov, kamarátov, známych a aj ich domáce zvieratá a za odmenu im sľúbili domáce sladkosti.
Susedia tak prišli do Adamovej záhrady v nejakom poradí. Toto poradie musí ostať rovnaké počas celého procesu organizácie a ťahania kalerábu. Samozrejme, pri kalerábe musí byť čo najsilnejší človek. Zlaté pravidlo ťahania kalerábov je, že za každým človekom so silou \(F\), musí byť človek, ktorý má silu presne \(F-1\). Zoberme si príklad, kde človek A, ktorý má silu 5 je pred človekom B. Človek B teda musí mať silu 4. Ak by bol človek B silnejší, človeka A potiahne moc silno a celý rad spadne. Ak by bol slabší, kaleráb sa im vytiahnuť nepodarí. Adam je skúsený záhradník, a vie mať akúkoľvek silu a vie sa postaviť kamkoľvek do radu. Adam má teda rad ľudí, z ktorých musí niektorých vypustiť, aby sa splnilo zlaté pravidlo ťahania kalerábov. Adam sa vie taktiež postaviť hocikde s hocijakou silou. Bude mať však ale dosť starostí s ťahaním a už potrebuje pomôcť s organizáciou. Pomôžete mu postaviť čo najdlhši rad, ktorý tieto pravidlá spĺňa?
Úloha
V záhrade je \(N\) ľudí, každý so silou \(F_i\) kde \(i\) je poradie, v ktorom prišiel daný človek. Vašou úlohou je vypustiť z radu niekoľko ľudí, a vsunúť do radu Adama tak, aby tento rad spĺňal zlaté pravidlo, a zároveň bol čo najdlhší. Stačí zistiť dĺžku najdlhšieho možného radu.
Formát vstupu
Na prvom riadku dostanete dve čísla: \(1 \leq N \leq 500\,000\) – počet ľudí v rade a \(1 \leq M \leq 50\,000\,000\) – najsilnejšieho človeka v rade. Na druhom riadku dostanete \(N\) čísel \(F_i\) oddelených medzerami – silu \(i\)-tého človeka v rade.
Formát výstupu
Na výstup vypíšte jedno číslo \(L\) – najväčšiu možnú dĺžku radu.
Príklad
Input:
10 12
1 3 5 7 9 2 4 8 12 10
Output:
4
Najlepšie riešenie je napríklad zobrať čísla 1, 2 a 4 z radu a postaviť Adama so silou 3 na správne miesto.
Input:
6 5
1 2 3 4 5 4
Output:
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):
= [0 for n in range(biggest+1)]
values_without_adam = [1 for n in range(biggest+1)]
values_with_adam
for ind, n in enumerate(nums):
= n-1
one_lower = n-2
two_lower
= values_without_adam[one_lower]
without_one = values_without_adam[two_lower]
without_two = values_with_adam[one_lower]
with_one
= without_one + 1
values_without_adam[n] = max(with_one + 1, without_two + 2)
values_with_adam[n]
return max(values_with_adam + values_without_adam)
= list(map(int, input().split()))
n_people, biggest = sol(list(map(int, input().split())), biggest)
answer print(answer)
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
long long n, m;
>> n >> m;
cin ++;
m
int without_adam[m];
int with_adam[m];
for (int i = 0; i < m; i++) {
[i] = 0;
without_adam[i] = 1;
with_adam}
int sol = 1;
long long current;
for (int i = 0; i < n; i++) {
>> current;
cin
[current] = without_adam[current-1]+1;
without_adam[current+1] = without_adam[current-1] + 2;
with_adam[current] = with_adam[current-1] + 1;
with_adam
= max({sol, without_adam[current], with_adam[current+1], with_adam[current]});
sol }
<< sol << endl;
cout return 0;
}
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.