2. Romantické výhľady vzorové riešenie

2
20 16

1 0 1

4
1 5 3 4

0 1 2

4
2 0 1 6

2 3 0

Vyhliadky, náučný chodník a okruh, po ktorom može Kika s Aďom chodiť, až do vysilenia. Aj o tom bola táto úloha a my sa teraz pozrieme na nejaké jej riešenia.

Bruteforce

V prvom rade si však ujasnime jednu vec. Náučný chodník je síce okruh, ale aj tak si ho budeme reprezentovať ako obyčajné pole. Akurát, vždy, keď sa budeme pozerať na prvú (resp. poslednú) vyhliadku, tak za jej prvú ľavú (resp. pravú) susednú vyhliadku budeme považovať poslednú (resp. prvú) vyhliadku.

Aby sme sa však vyhli problémom s prvou a poslednou vyhliadkou, ich susedmi a ich indexami v našom poli, tak si jednoducho celé pole zapamätáme dvakrát za sebou (skopírujeme si danú postupnosť vyhliadok a vložíme ju za už zapamätanú postupnosť). Takže vo výsledku budeme mať hneď za posledným prvkom prvý.

Prvá myšlienka, ktorá nám môže napadnúť je vyskúšať všetky možnosti trojíc vyhliadok a zistiť, či pre ne platia Kikine podmienky.

Teda postupne si zvolíme jednotlivé výhliadky tak, že za prvú dosadíme postupne všetky možnosti, za tretiu tak isto a za prostrednú zvolime niektorú z vyhliadok medzi prvou a druhou. Pre túto trojicu musí platiť to, že dve krajné vyhliadky z tejto trojice majú súčet ich vzdialeností k prostrednej najmenší možný.

Môžeme teda ísť cez všetky takéto trojice a pamätať si, akú najlepšiu trojicu sme zatiaľ videli. Keďže sme si pole skopírovali, stačí nám prechádzať cez trojice indexov \((i, j, k)\) pre ktoré platí \(0\leq i \leq j \leq k < 2n\). Súčet vzdialeností k prostrednej je potom \(k - i\). Na konci vypíšeme skutočné indexy najlepšej nájdenej trojice. Všimnite si, že na to, aby sme z upravených pozícií vyhliadok dostali ich skutočné pozície, stačí nám zobrať zvyšok po vydelení \(n\).

Takže, čo sa týka zložitostí: jednorázovo kopírujeme vstupné \(n\)-prvkové pole a skúšame overovať všetky trojice, ktorých je rádovo \(n^3\). Z tohoto nám vyjde časová zložitosť \(O(n^3)\). Pamäťová bude \(O(n)\) pretože si pamätáme len jedno pole, ktoré má \(2n\) prvkov (ale 2 je konštanta, takže tú zanedbáme).

n = int(input())
s = [int(i) for i in input().split()]

spots = []
for i in range(2*n):
    spots.append(s[i%n])

highest = -1
index = -1

start = -1
stop = -1

done = False
for i in range(2 * n):
    for j in range(2 * n):
        for k in range(i+1, j):
            if j - i == 2 and spots[i] < spots[k] > spots[j]:
                highest = spots[k]
                index = k % n
                start = i % n
                stop = j % n

                done = True
                break
        if done:
            break
    if done:
        break

print(start, index, stop)

Niečo lepšie

Skúšanie všetkých trojíc nie je úplne optimálne. Ak by sme však vedeli povedať niečo viac o tých troch vyhliadkach, tak by nám to pomohlo. Vieme že prostredná z nich musí byť vyššia ako jej susedné. To je ale len jej vzťah k jej susedným vyhliadkam a nehovorí to nič o vzťahu k ostatným vyhliadkam. Čiže môže mať kľudne tretiu najmenšiu nadmorskú výšku a s jej susednými spĺňať Kikine podmienky, ale môže to byť kľudne aj najvyššie položená vyhliadka s jej susedmi. A od tohoto sa odrazíme.

Dôležité pozorovanie je, že výšky vyhliadok sú navzájom rôzne. A tým pádom, ak zoberieme najvyššiu vyhliadku, jej susedné vyhliadky (z každej strany) musia byť nutne nižšie. Takáto trojica má súčet rozdielu vzdialeností \(2\), a lepší súčet dosiahnuť nemôžme (zamyslite sa).

Takže nám stačí nájsť vyhliadku s najväčšou nadmorskou výškou a vziať jej susedov. Ako ju nájsť?

Ak by sme mali vyhliadky zoradené podľa výšky vzostupne, tak by to bola tá posledná. Ale ako potom nájdem jej najbližšie susedné vyhliadky, keď zmením ich poradie, tým že ich zoradím? Budem si jednoducho pamätať dve polia – jedno bude kópia druhého, ale bude zoradené podľa nadmorských výšok. Zoradiť ho môžeme pomocou nejakého triediaceho algoritmu alebo jednoducho využijeme funkciu sort, ktorá je už vo väčšine jazykov implementovaná.

Teraz najvyššiu výhliadku nájdeme v pôvodnom, nezoradenom poli a vezmeme jej susedov. Tu nemusíme nejak špeciálne riešiť prípad, že prostredná je prvá alebo posledná v poli a teda jej najbližší sused je na opačnom konci pola. Skrátka jednoducho pridáme podmienky, ktoré nám vrátia presných susedov na základe pozície najvyššej vyhliadky.

Časová zložitosť tohoto riešenia bude \(O(n \log n)\) – najzložitejšia časť v tomto riešení je triedenie, ktorého zložitosť je \(O(n \log n)\). Potom už len hľadáme pozíciu najvyššej vyhliadky v pôvodnom poli, čo bude v najhoršom prípade \(O(n)\), ale to je oproti \(O(n \log n)\) zanedbateľné. Pamäťová zložitosť
bude \(O(n)\), lebo si pamätáme iba 2 polia dĺžky \(n\).

n = int(input())
spots = [int(i) for i in input().split()]

spotsCopy = spots.copy()
spotsCopy.sort()

highestIdx = spots.index(spotsCopy[-1])

if highestIdx + 1 >= len(spots):
    print(highestIdx-1, highestIdx, 0)
elif highestIdx - 1 < 0:
    print(len(spots)-1, 0, 1)
else:
    print(highestIdx-1, highestIdx, highestIdx+1)

Optimálne riešenie

Keď sa lepšie pozrieme na predošlé riešenie, tak zistíme, že pri prechode poľa s nadmorskými výškami nemusíme iba hľadať pozíciu najvyššej vyhliadky, ale aj zisťovať, ktorá výhliadka je najvyššia. Vďaka tomu sa môžeme úplne zbaviť zoraďovania vyhliadok a zrýchliť naše riešenie.

Takže stačí nám raz prejsť pole zo vstupu a postupne hľadať najvyššiu vyhliadku. Budeme mať nejaké dve premenné, v ktorých si budeme v každom momente pamätať doteraz najvyššiu vyhliadku a jej pozíciu. Čiže pri prechode poľa, vždy keď nájdeme vyhliadku, ktorá je vyššie ako tá, ktorú si pamätáme ako doteraz najvyššiu, tak tie dve premenné prepíšeme. No a na konci budeme mať v premenných najvššiu vyhliadku aj s jej pozíciou.

Už nám stačí iba nájsť najbližšie susedné vyhliadky k najvyššej a vypísať ich.

Keďže algoritmus iba raz prejde \(n\)-prvkové pole, časová zložitosť bude \(O(n)\) a pamätáme si tiež len toto pole a konštatný počet premenných, takže pamäťová zložitosť bude \(O(n)\).

n = int(input())
spots = [int(i) for i in input().split()]

highest = max(spots)
index = spots.index(highest)

if index + 1 >= len(spots):
    print(index-1, index, 0)
elif index - 1 < 0:
    print(len(spots)-1, 0, 1)
else:
    print(index-1, index, index+1)