3. Znovu začíname vzorové riešenie

3
+ peter
- alica
0 bob

OK
alica
peter
bob

1
- peter

FAIL

V tejto úlohe sme na vstupe dostali popis terajšej výsledkovky a bolo našou úlohou zistiť, či mohla táto výsledkovka vzniknúť z nejakých výsledkov predošlého kola a ak áno, mali sme jednu takúto predošlú výsledkovku (riešenie úlohy) vypísať.

Kedy to nejde?

Uvažujme najprv taký vstup, v ktorom nie sú nuloví riešitelia. Poďme skúsiť nájsť nejaké kritériá, ktoré musí spĺňať terajšia výsledkovka, ak mala vzniknúť z nejakej predošlej:

• Prvý riešiteľ musí byť plusový. Ak by bol mínusový, znamenalo by to, že ho od minulého kola niekto predbehol … tento riešiteľ by teda musel byť v terajšej výsledkovke vyššie ako prvý, čo sa ale nemôže nikdy stať.

• Posledný riešiteľ musí byť mínusový. Podobne, ak by bol posledný riešiteľ plusový, musel sa od predošlého kola zlepšiť a niekoho predbehnúť. Ten niekto by mal byť v terajšej výsledkovke pod ním. Pod posledným riešiteľom ale už nie je nikto, a tak posledný nemôže byť plusový.

Našli sme dve podmienky, ktoré musíme overiť. Ak ľubovoľná z nich neplatí, žiadna predošlá výsledkovka neexistuje. Nevieme však, či stačí overiť len tieto podmienky. Možno aj po ich splnení riešenie stále niekedy existovať nebude…

Ako by to mohlo ísť?

Napriek tejto neistote sa pokúsime nájsť riešenie len za predpokladu, že sú splnené tieto dve podmienky.

Keďže mínusoví riešitelia od minulého kola klesli, je pomerne dobrý nápad dať ich čo najviac navrch predošlej výsledkovky (aby mali odkiaľ klesnúť) a podobne môžeme skúsiť dať plusových riešiteľov čo najviac na spodok. Spravíme to ale tak, aby sme zachovali relatívne poradie plusových riešiteľov navzájom a poradie mínusových navzájom:

1. zoberieme všetkých mínusových a v poradí, v akom sú v terajšej výsledkovke ich zapíšeme na vrch predošlej výsledkovky

2. zoberieme všetkých plusových riešiteľov a v poradí, v akom sú v terajšej výsledkovke ich postupne zapíšeme pod mínusových

Z terajšej výsledkovky teda vytvoríme predošlú takto:

 terajsia       predosla
 --------       --------
+ peter      (-) zygro
+ petka      (-) mario
- zygro      (+) peter
+ janko      (+) petka
- mario      (+) janko

Bude to fungovať?

To, že tento postup bude vždy(ak sú splnené 2 predošlé podmienky) fungovať, si musíme dokázať. To ale bude jednoduché.

Pozrime sa na umiestnenie ľubovoľného plusového riešiteľa (napr. Peťky) v predošlej (4. miesto) a v terajšej výsledkovke (2. miesto). Miesto, na ktorom je daný riešiteľ závisí len od toho, koľkí riešitelia sú nad ním vo výsledkovke. V predošlej výsledkovke sú teda pred týmto plusovým riešiteľom všetci plusoví, čo sú pred ním aj v terajšej (Peter) a zároveň aj všetci mínusoví (Zygro a Mário). Keďže ale v terajšej výsledkovke nie sú pred plusovým všetci mínusoví (lebo jeden mínusový je posledný) tak je v terajšej výsledkovke aj náš plusový riešiteľ určite vyššie, lebo je nad ním menej riešiteľov ako v predošlej.

Pre mínusových riešiteľov vieme podobne dokázať, že v predošlej výsledkovke boli vyššie, pretože sme pod nich umiestnili všetkých plusových riešiteľov (aj toho plusového, ktorý je v terajšej výsledkovke prvý).

Čo s nulovými riešiteľmi?

Je jasné, že nuloví riešitelia museli byť v predošlom kole na rovnakom mieste ako sú teraz (lebo sa ani nezhoršili, ani nezlepšili). Môžeme si teda úlohu zjednodušiť a riešiť ju akoby bez nich. Jednoducho ich pomyselne vyškrtneme z terajšej výsledkovy a úlohu vyriešime vyššie uvedeným postupom len pre plusových a mínusových riešiteľov – nazvime toto riešenie nenulové.

Riešenie úlohy aj s nulovými riešiteľmi získame tak, že ich najprv umiestnime na ich pôvodné miesta a potom postupne zaplníme zvyšné miesta nenulovými riešiteľmi v takom poradí, v akom boli v nenulovom riešení.

Ak nenulové riešenie neexistuje, nebude existovať ani žiadne riešenie úlohy (predošlá výsledkovka aj s nulovými riešiteľmi). Nutné podmienky vieme totiž prepísať tak, aby platili aj pre riešenie s nulovými riešiteľmi:

• Prvý nenulový riešiteľ musí byť plusový. Ak by bol mínusový, musel ho niekto predbehnúť, no pred ním sú len nuloví riešitelia, ktorí tu boli aj predtým.

• Posledný nenulový riešiteľ musí byť mínusový. Ak by bol plusový, musel niekoho predbehnúť, no pod ním sú len nuloví riešitelia, ktorí tam boli aj v predošlom kole.

Ako to naprogramovať?

Hneď na začiatku si vytvoríme tri polia reťazcov. Pole mínusových riešiteľov, plusových riešiteľov a pole, kam budeme zapisovať riešenie – predošlú výsledkovku.

Ak pri čítaní vstupu narazíme na nulového riešiteľa, zapíšeme si ho do poľa s riešením na jeho pôvodné miesto. Meno plusového alebo mínusového riešiteľa si zapíšeme do plusového alebo mínusového poľa.

Ďalej potrebujeme overiť dve podmienky. Na to si stačí počas čítania vstupu do premenných zapamätať, aké znamienko bolo pri prvom a poslednom nenulovom riešiteľovi. Po dočítaní vstupu podmienky overíme a program buď vypíše FAIL a skončí, alebo bude pokračovať.

Na záver bude stačiť vyplniť zvyšné miesta v riešení. Stačí nám teda raz prejsť pole s riešením a ak je nejaké miesto voľné, priradíme sem (alebo rovno vypíšeme) ďalšieho mínusového alebo (keď sa minú mínusoví) plusového riešiteľa.

n = int(input())
plusovi, minusovi = list(), list()
riesenie = ["" for x in range(n)]

prvy_nenulovy = "0"
posledny_nenulovy = "0"

for i in range(n):
    zmena, meno = input().split()

    if zmena != "0":
        if prvy_nenulovy == "0":
            prvy_nenulovy = zmena
        posledny_nenulovy = zmena

    if zmena == "+":
        plusovi.append(meno)
    elif zmena == "-":
        minusovi.append(meno)
    else:
        riesenie[i] = meno  # nulovych hned pridame na ich povodne miesto

if posledny_nenulovy == "+" or prvy_nenulovy == "-":
    print("FAIL")
    exit(0)

print("OK")
nenulovi = minusovi + plusovi
dalsi_nenulovy = 0

for i in range(n):          # na zvysne miesta postupne pridame minusovych a plusovych
    if riesenie[i] == "":
        riesenie[i] = nenulovi[dalsi_nenulovy]
        dalsi_nenulovy += 1

print("\n".join(riesenie))

Zložitosť

Časová zložitosť algoritmu je \(O(n)\) – lineárna od počtu ľudí vo výsledkovke, keďže stačí len raz prejsť vstup, a prípadne raz prejsť cez všetky pozície výsledkovky.

Pamäťová zložitosť tohto algoritmu je tiež \(O(n)\) – každé z našich troch polí bude obsahovať najviac \(n\) reťazcov.