Zadanie

Po maturite riešil mladý Vašino zapeklitý problém - raz sa prázdniny skončia a bude treba ísť do školy. Teraz bol problém ešte zložitejší, lebo si vyberal, kam pôjde študovať. Situácia závažná, nakoniec sa ale rozhodol, že MatFyz je najlepšie miesto na študovanie informatiky na svete.

Hodil si mincou, či bude bývať na internáte alebo si pohľadá nejaký podnájom. Keďže padla hlava, bude musieť byť ďalší rok sociálnejší a zabývať sa na internáte.

Keď Vašino pricestoval na intrák, najviac ho zaujal výťah vo výškovej budove. Všimol si, že niektoré poschodia sú vo výťahu špeciálne vyznačené. Hneď mu bolo jasné, že ide o nejaké mysteriózne poschodia. Keďže Vašino je len zmätený prvák, radšej by sa im vyhol. Zároveň má ale Vašino rád vozenie sa výťahom a tak chce zistiť, koľko najviac si vie užívať bezstarostnú jazdu, bez prechádzania cez takéto desivé poschodia. Inak povedané, koľko najviac poschodí po sebe sa vie viezť tak, aby neprešiel ani jedným mysterióznym poschodím.

Úloha

Výťah vie klesnúť najviac na poschodie číslo \(z\) (ako začiatočné) a ide hore až po poschodie číslo \(k\) (ako konečné). Mysteriózne poschodia sú označené číslami z množiny celých čisel na tomto intervale.

Vašou úlohou je určiť, aký dlhý je najdlhší úsek po ceste zo \(z\) do \(k\) je taký, že na ňom neprejdeme cez žiadne mysteriózne poschodia. (Dĺžka úseku je počítaná ako počet nemysterióznych poschodí, ktoré cesta obsahuje. Teda sa tam počítajú aj začiatočné a konečné poschodie.)

Formát vstupu

V prvom riadku sú dve hodnoty \(z\) a \(k\) oddelené medzerou (\(1 \leq z < k \leq 10^{12}\)) - spolu predstavujú interval, na ktorom premáva výťah.

V druhom riadku je práve jedno číslo \(p\), určujúce počet poschodí, ktoré sú mysteriózne.

V treťom, poslednom riadku, je \(p\) medzerou oddelených čísel, reprezentujúce mysteriózne poschodia, cez ktoré nechceme prejsť výťahom, ani tam nastúpiť či vystúpiť.

Hodnotenie

Premenná \(n\) reprezentuje celkový počet poschodí, teda \(n = k-z+1\), cez ktoré premáva výťah. Premenná \(p\) reprezentuje počet mysterióznych poschodí, ktorým sa treba vyvarovať. Platí, že ľubovolné tajné poschodie nie je menšie ako \(z\) ani väčšie ako \(k\). V nasledujúcej tabuľke uvádzame horné obmedzenia pre \(n\) a \(p\) v 4 sadách vstupov - za každú úspešne vyriešenú sadu vám testovač udelí 2 body.

Sada 1 2 3 4
\(1 \leq n \leq\) \(20\) \(1\,000\) \(10^{5}\) \(10^{12}\)
\(0 \leq p \leq\) \(20\) \(1\,000\) \(10^5\) \(10^6\)

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo - dĺžka najdlhšieho úseku cesty výťahom bez prechodu cez nejaké mysteriózne poschodie.

Príklady

Input:

2 11
2
4 9

Output:

4

Najdlhšie sa budeme viesť 4 poschodia a to od piateho po ôsme (vrátane).

Input:

1 4
1
1

Output:

3

Nastupujeme na druhom a ideme až na štvrté - dokopy tri poschodia.

Input:

40 533
5
95 71 533 49 233

Output:

299

Prechádzanie poschodiami od z do k (Počet bodov: 4/8)

Predpokladajme, že Vašino ide postupne, po jednom, od najnižšieho poschodia \(z\) po najvyššie \(k\). V tomto prípade, vždy keď príde na nejaké poschodie (dokopy \(n\)-krát), rozhoduje sa, či cez neho môže prejsť. Rozhodovanie znamená, že sa pozrie do poľa veľkosti \(p\), v ktorom sú uložené čísla mysterióznych poschodí, či sa tam dané poschodie nachádza. Toto overenie mu vždy trvá \(O(p)\) operácií. Ak zistí, že sa tam aktuálne poschodie nenachádza, vie, že dovtedajší súvislý úsek nemysterióznych poschodí môže zvýšiť o 1. Inak musí dĺžku znulovať. Z takto napočítaných úsekov si vyberie najdlhší. Časová zložitosť bude \(O(n) + n \cdot O(p)\), čo je \(O(n \cdot p)\). Pamäťová zložitosť je \(O(p)\), nakoľko si pamätáme pole mysterióznych poschodí.

Mysteriózne poschodia v množine (Počet bodov: 6/8)

Postupujeme tak isto ako v predchádzajúcom riešení, len namiesto ukladania mysterióznych poschodí do poľa si ich ukladáme do dátovej štruktúry množina. Totiž overenie, či sa v množine nachádza nejaký prvok je v programovacích jazykoch zvyčajne implementované ako veľmi rýchla operácia. Dátová štruktúra set v Pythone a std::unordered_set v C++ túto operáciu podporujú v \(O(1)\). Časová zložitosť teda bude len \(O(n \cdot 1) = O(n)\). Pamäťová zložitosť sa nezmenila.

z, k = map(int, input().split())
p = int(input())
p = set(map(int, input().split()))


t = 0
b = 0
for i in range(z, k+1):
    if i in p:
        t = 0
    else: t += 1
    b = max(b, t)

print(b)

Optimálne riešenie (Počet bodov: 8/8)

Poďme teraz vyriešiť druhý problém pôvodného riešenia, a to, že prechádzame cez všetky poschodia. Všimnime si, že počet mysterióznych poschodí je oveľa menší než celkový počet poschodí. Využime tento fakt v náš prospech.

Opäť môžeme ísť zdola nahor. Keďže nemysteriózne poschodia nám cestu nekazia, nemusíme sa o ne zaujímať a môžeme ich preskočiť. Aby sme prechádzali mysetriózne poschodia naozaj v poradí zdola nahor, vopred si ich usporiadame od najmenšieho po najväčšie. Dva prvky vedľa seba potom znamenajú možnú súvislú dĺžku jazdy výťahom.

Na zjednodušenie implementácie na úvod tohoto zoznamu pridáme \(z-1\) a na záver \(k+1\). Tieto čísla budú slúžiť ako zarážky, aby aj prípadné koncové úseky poschodí boli z oboch strán ohraničené mysterióznymi poschodiami. Uvedomme si, že aj keby jedno z týchto pridaných zarážkových poschodí bolo uvedené ako mysteriózne na vstupe, fungovanie programu nám to nepokazí.

Každý súvislý bezproblémový úsek je teraz ohraničený dvoma, v našom poli susednými, mysterióznymi poschodiami. Keďže chcem nájsť najdlhší úsek, porovnávame každé dve susedné mysterózne poschodia a zapisujeme si najväčší rozdiel, ktorý kedy nameriame. Odpoveď vypíšeme.

Rýchle triediace algoritmy ako napríklad quicksort alebo mergesort majú pre \(n\) prvkov časovú zložitosť \(O(n \log n)\). My samozrejme použijeme vstavané triediace algoritmy našich jazykov, ktoré majú rovnakú časovú zložitosť. Jedno prejdenie a porovnanie susedov trvá \(O(p)\), čo je zanedbateľné v porovnaní s náročnejšiou operáciou triedenia. Celková časová zložitosť je teda \(O(p \log p)\)\(n\) sa nám zmenilo na \(p\), avšak pribudol nám logaritmus (ale nezúfajte, vieme sa ho zbaviť!).

Pamäťová zložitosť stále zostáva \(O(p)\), lebo rovnako ako v prvom riešení si udržiavame mysteriózne poschodia v poli dĺžky \(p\).

Kód

def solve(z,k,poschodia):
    poschodia = [z - 1] + sorted(poschodia) + [k + 1]

    maximalny_rozdiel = 0
    for i in range(1, len(poschodia)):
        maximalny_rozdiel = max(poschodia[i] - poschodia[i - 1] - 1, maximalny_rozdiel)

    return maximalny_rozdiel


z,k = input().split()
x = input()
nums = input().split()
poschodia = [int(i) for i in nums]

print(solve(int(z), int(k), poschodia))

Riešenie v ideálnom svete (Počet bodov: 8/8)

Pre isté špeciálne prípady vstupov existujú aj rýchlejšie spôsoby usporiadavania prvkov ako v \(O(p \log p)\). Napríklad ak máme usporiadavať celé čísla v určenom rozsahu, môžeme použiť algoritmus bucket sort, ktorý to dokáže v čase \(O(p)\). Viac o bucket sorte si môžeš prečítať napríklad tu, na wiki. S jeho použitím vyriešime problém logaritmu a dostávame optimálnu časovú aj pamäťovú zložitosť \(O(p)\) (lepšia nemôže byť kvôli veľkosti vstupu).

Ak si použil bucket sort, veľmi pravdepodobne si ale zistil, že kód ti bežal pomalšie než s použitím vstavaného sortu. To je normálne (štandardná knižnica sa poráža ťažko) a stále od nás dostávaš extra pochvalu.

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ť.