2. A sme doma… vzorové riešenie

2 11
2
4 9

4

1 4
1
1

3

40 533
5
95 71 533 49 233

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.