From KSP.sk

Seminar: Ideálne riešenie

Na tomto mieste by sme vám radi povedali niekoľko slov o tom, ako si predstavujeme popis ideálneho riešenia. Ako má vyzerať odovzdaný program sa môžete dočítať na samostatnej stránke.

Nechceme, aby ste nám zbytočne popisovali manipuláciu so vstupom a výstupom. Samozrejme, zakazovať vám to nebudeme, ale bodíky navyše za to nedostanete a ešte môžete znechutiť opravovateľa, ktorý musí čítať množstvo textu nesúvisiaceho s riešením samotnej úlohy. Vo svojom riešení sa nemusíte zaoberať kontrolovaním správnosti vstupných údajov.

Pod pojmom popis algoritmu nerozumieme preloženie programu z Pascalu, prípadne C-čka do slovenčiny. Popis by mal zhruba obsahovať:

• Popis myšlienky, na ktorej je založený algoritmus (bez detailov ako sú názvy premenných, procedúr...).
• Popis dátových štruktúr. Čo si vlastne chceme počas výpočtu pamätať a aké štruktúry sú na to vhodné.
• Popis algoritmu. Tu môžeme využívať už popísané dátové štruktúry a spomenúť dôležité procedúry a funkcie, ako aj najdôležitejšie premenné.
• Zdôvodnenie správnosti. Nemusí to byť formálne presný ani detailný dôkaz, avšak mal by obsahovať argumenty zdôvodňujúce každý dôležitý aspekt programu, ktorý nie je na prvý pohľad zrejmý. Sem zaradíme aj dôkaz konečnosti v tých prípadoch, keď nie je zrejmé, že sa program (resp. niektorá operácia, ktorú vykonáva) nezacyklí.
• Na koniec príde odhad časovej a pamäťovej zložitosti programu.

Takáto štruktúra popisu nie je univerzálna. Niektoré časti možno vynechať, niektoré zlúčiť, prípadne nejaké pridať. Poradie by však malo byť zhruba zachované.

Niekoľko slov o odhade zložitosti

Pod odhadom časovej zložitosti rozumieme odhad času, ktorý bude program trvať, v závislosti od vstupných premenných. Tento čas je priamo úmerný počtu elementárnych operácií, ktoré program vykonáva - priradenie jednoduchej premennej, porovnanie jednoduchých premenných, aritmetické operácie, atď. Väčšinou sa zaujímame o to, ako dlho beží program v priemernom, alebo najhoršom prípade (čiže si všímame priemerný, alebo maximálny čas vykonávania programu). Analogicky odhad pamäťovej zložitosti je odhad veľkosti použitej pamäti v bajtoch v závislosti od vstupných premenných.

Väčšinou nás nezaujímajú presné hodnoty (niekto má rýchlejší počítač, na niektorých počítačoch má integer 2 a na iných 4 bajty a pod.), preto používame tzv. O-notáciu. Hovoríme, že funkcia f(n) (napr. čas behu programu v milisekundách v závislosti od veľkosti vstupu n) je O(g(n)) (g(n) je tiež funkcia), ak existuje taká konštanta c, že pre všetky dostatočne veľké n (n>n0) je f(n) <= c.g(n).

Napríklad, ak program pre vstup veľkosti n nebeží nikdy viac ako T(n)=0.5n³ + 5n.log(n) + 83 mikrosekúnd, môžeme povedať, že má časovú zložitosť O(n³). Ak program potrebuje najviac M(n) = 3n.log₂(n) + 150n + 15 bajtov pamäti, povieme, že má pamäťovú zložitosť O(n.log(n)). (Poznamenávame, že ak je nejaká funkcia O(n²), tak je aj O(n³) atď. Vždy sa však snažíme nájsť čo najmenšie horné ohraničenie, t.j. funkciu, ktorá čo najpomalšie rastie.)

A ešte jedno upozornenie pre vás - riešiteľov: uvedením nepostačujúceho popisu prípadne jeho vynechaním riskujete, že opravovateľ vaše riešenie nepochopí a dostanete napr. 0 (slovom nula) bodov.

---

Na doplnenie horeuvedných (pre niekoho možno príliš nekonkrétnych) rečí o tom, ako si predstavujeme ideálne riešenie, pripájame dva kompletné príklady z KSP aj s ich vzorovými riešeniami. Na týchto vzorových riešeniach jasne vidno, čo chápeme pod slovami popis, program a odhad časovej zložitosti. Nech vám teda tieto vzorové riešenia slúžia ako svetlý vzor pre písanie vlastných riešení :-) (P.S. K popisu. Ak si niekto myslí, že popis je nepodstatný, skúste si vytlačiť len listing druhého programu a zistiť, čo tým autor myslel.)

Vzorový príklad #1

Tento príklad je z KSP-Z 19. ročník, 1. kolo, 4. Zhrdzavené potrubie

Zadanie

"Zase ďalšia diera!", v duchu si povedal Zápla, dvorný opravár Zimbabwejského kráľovstva. Za tých - 1, 2, 3,... no proste veľa - rokov svojej služby videl už mnoho hrdzavých potrubí. Zvyčajne bola diera len jedna, a preto nebol problém, čo s ňou - jednoducho ju Zápla zaplátal záplatou. Z ničoho nič ho dnes ráno zavolali k veľkej havárii na hlavnom vodovodnom potrubí, ktoré dopravuje vodu z jazera Kariba (16o 53' S, 28o 1' E) do hlavného mesta, Harare (17o 50' S, 31o 3' E). Z asi dvadsiatich miest potrubia striekala voda cez prehrdzavené steny hrubej rúry. Záplaty na také veľké potrubie sú drahé (záplaty sa dnes už nevyrábajú zo železa, ktoré ľahko a rýchlo hrdzavie, ale z prefíkanej umelej hmoty, ktorá určite prežije celé pôvodné potrubie), a preto si Zápla musí dobre rozmyslieť, ako ich na diery poukladať.

Úloha

Záplaty sú už z továrne narezané na metrové kúsky a nedajú sa už na mieste rezať na menšie. Zhrdzavený kúsok potrubia, teda diera, je zanedbateľne malá; ak položíme záplatu jej krajom na dieru, bude táto diera zaplátaná. Záplat môžeme dať aj viac na seba.(záplaty z prefíkanej umelej hmoty sú dostatočne tenké, takže to nebude ničomu vadiť) Zhrdzavené miesta (nech je ich N) sú určené ich polohou na potrubí, a keďže sú veľmi malé, budeme ich uvažovať len ako body na priamke a ich poloha bude udaná vzdialenosťou od začiatku potrubia (v metroch); môžete predpokladať, že pozície všetkých dier sú na vstupe utriedené podľa vzdialenosti od začiatku potrubia.

Zápla je už mierne nervózny, voda stále strieka a on vás žiada o radu, ako má záplaty na potrubie dávať, aby ich musel čo najmenej použiť.

Formát vstupu Na prvom riadku je číslo - počet dier. Na druhom riadku je čísel - pozície dier.

Formát vstupu Pre každú použitú záplatu vypíšte jeden riadok, obsahujúci jedno číslo - pozíciu začiatku záplaty.

Príklad

Vstup

3
1 3 3.5

Výstup

0.5
2.75

Vzorové riešenie

Kvôli ľahšiemu vyjadrovaniu si predstavme, že potrubie ide zľava doprava. Ľahko si všimneme, že najľavejšiu záplatu môžeme položiť od najľavejšej diery. Viac vpravo najľavejšiu záplatu dať nemôžeme, inak by sme nezakryli najľavejšiu dieru. Ak by zase ležala viac vľavo, tak posunutím doprava do vyššie spomenutej polohy nič nestratíme.

Teraz už vieme, kam môžeme dať našu najľavejšiu záplatu. Tá zakryje nejaké diery. Podobnou argumentáciou zdôvodníme, že druhú najľavejšiu záplatu môžeme dať od najľavejšej nezakrytej diery. Podobne s ďalšími záplatami.

Náš postup si možno predstaviť takto: Predstavme si, že sa postavíme na začiatok potrubia a pochodujeme po ňom smerom doprava. Ak zbadáme dieru, tak od nej dáme záplatu. Ignorujeme diery, ktoré sú od poslednej položenej záplaty vzdialené do jedného metra, pretože sú zaplátané našou záplatou. Toto robíme, až kým neprídeme na koniec potrubia.

Program potom bude vyzerať jednoducho. Budeme postupne načítavať diery. Keďže sú utriedené, tak ich načítavame presne v tom poradí, ako by sme ich pri našom pochode zbadali. Pamätáme si, odkiaľ sme položili poslednú záplatu. Pri načítaní ďalšej diery len zistíme, či je poslednou záplatou zakrytá, vtedy neurobíme nič. Ak nie je zakrytá, tak položíme novú záplatu t.j. vypíšeme jej pozíciu a zapamätáme si ju ako polohu novej poslednej záplaty.

Tento algoritmus urobí nanajvýš niekoľko málo operácií pre každú z dier, preto povieme, že jeho časová zložitosť je lineárna od počtu dier. (Niekedy sa jednoducho povie, že časová zložitosť je lineárna a šikovný čitateľ si má domyslieť vzhľadom na aký paramenter.) Matematici tento fakt povedia takto: Časová zložitosť je O(N).

Podobne je to s pamäťovou zložitosťou. Program si pamätá len niekoľko málo čísel, preto povieme, že pamäťová zložitosť je konštantná. (Niekto by opäť mohol povedať konštatná od počtu dier). Konštanta má ale tú výhodu, že je konštantná od ľubovoľného parametra.) Pododne ako predtým matematik povie toto: Pamäťová zložitosť je O(1).

---

Vzorový príklad #2

Tento príklad je z KSP-Z 13. ročníka (áno aj vtedy bolo KSP a malo príklady), 1. kolo, 4. O valcočlovekovi II.

Zadanie

Valcočlovek je taký človek, ktorého tvar sa približuje tvaru valca s určitou výškou a polomerom. Výskyt ľudí takéhoto tvaru je veľmi vysoký napríklad medzi pracovníkmi francúzskych vínnych pivníc (čím viac vína pracovník skonzumuje, tým je širší). Francúzske vínne pivnice sú veľké podzemné sály tvaru obdĺžnika podopierané tenkými stĺpmi. Strany obdĺžnika sú orientované v smere svetových strán. Často sa stáva, že valcočlovek sa zasekne medzi stĺpy a vínna pivnica sa stane nepoužívateľnou (zaseknutý valcočlovek zle vplýva na kvalitu vína). Preto si valcočlovek musí vždy dobre rozmyslieť, cez ktorú pivnicu môže ísť.

Úloha

Napíšte program, ktorý načíta rozmery pivnice M, N, počet stĺpov P a polomer valcočloveka R. Potom načíta súradnice stĺpov ( [0.00,0.00] je severozápadný roh pivnice, [M,N] juhovýchodný ) a napíše, či môže tento valcočlovek prejsť pivnicou od západnej steny po východnú.

Formát vstupu

Na prvom riadku sú čísla M, N, P a R. Potom nasleduje P riadkov, na každom sú 2 číslo - súradnice stĺpov.

Formát výstupu

Vypíšte jeden riadok obsahujúci vetu "Valcoclovek II neprejde pivnicou." alebo "Valcoclovek II prejde pivnicou."

Vzorové riešenie

Riešenia možno rozdeliť v zásade na tieto skupiny:

• Pokúšame sa zistiť, či existuje cesta zo západu na východ. Tu sa vyskytlo niekoľko modifikácií. Buď ste si predstavili pivnicu v podstate ako grafickú obrazovku, okolo stĺpov ste vyfarbili kruhy a pokúšali sa vyfarbiť pivnicu od západu k východu, alebo ste rekurzívne prehľadávali pivnicu s nejakým krokom (o 1 hore, dole, vpravo, vľavo). Tieto riešenia sú veľmi nepresné a neefektívne. Dali sa za ne získať maximálne 2 body.
• Pokúšame sa zistiť, či nejaké stĺpy tvoria taký rad, že každé dva susedné sú od seba vzdialené o menej ako priemer Valcočloveka a prvý je od severnej a posledný od južnej vzdialený tiež o menej ako priemer Valcočloveka. Tu sa vyskytlo niekoľko prístupov. Rekurzie s exponenciálnou zložitosťou mohli získať maximálne 4 body, algoritmy s kubickou zložitosťou 5 bodov a s kvadratickou zložitosťou maximálne 10 bodov. Vyskytlo sa niekoľko typov kvadratických riešení, všetky sú ale v podstate modifikáciou uvedeného vzorového riešenia.

1 bod sme strhávali pri nekontrolovaní podmienky 2R < N. Ďalší bod bolo možné stratiť v prípade neuvedenia popisu algoritmu a ešte jeden v prípade absencie príkladov vstupu a výstupu programu alebo odhadu zložitosti algoritmu.

Ak sa na pivnicu pozrieme zhora, stĺpy si môžeme predstaviť ako body a Valcočloveka ako kružnicu. Je zrejmé, že medzi dvoma stĺpmi ktoré sú bližšie ako priemer Valcočloveka sa on neprepchá. Spojme teda každú takúto dvojicu hranou. Navyše si predstavme severnú a južnú stenu ako špeciálne stĺpy (jeden označme 0 a druhý P+1). Stena bude spojená hranou s iným stĺpom, ak je k nemu bližšie ako priemer Valcočloveka. Úlohu teraz možno previesť na grafovú. Je zrejmé, že ak existuje cesta z vrcholu 0 na vrchol P+1, tak Valcočlovek pivnicou neprejde (ak by prešiel, musel by niekde križovať lomenú čiaru od severnej steny k južnej, čo je spor s predpokladom, že cez vyznačené hrany sa nedá ísť). Na druhej strane ak takéto prepojenie neexistuje, Valcočlovek dokáže prejsť (toto možno ľahko nahliadnuť, ak si predstavíme Valcočloveka, ktorý pôjde tak, že po ľavej ruke bude mať vždy nejakú hranu alebo severnú stenu - bude kopírovať terén. Určite prejde na druhú stranu, keďže nikde sa netiahnu hrany od severu na juh).

Zisťovanie existencie cesty medzi vrcholmi 0 a P+1 spravíme nasledovne: Začneme vo vrchole 0, ktorý označíme a uložíme do fronty (Fronta je dátová štruktúra, kde prvky ukladáme na koniec fronty a zo začiatku ich zase v prípade potreby vyberáme. Môžete si ju predstaviť ako rad na zaplatenie u pokladne v potravinách (ľudia sa postavia na koniec a čakajú, kým ich pokladníčka vpredu ``vyberie''). (pozn.red.)). Potom postupne vyberáme vrcholy z fronty a každý neoznačený vrchol, ktorý je s nimi spojený hranou označíme a uložíme na koniec fronty. Ak uložíme niekedy do fronty vrchol P+1, tak existuje cesta zo severu na juh a Valcočlovek neprejde. Na druhej strane keď vyčerpáme všetky vrcholy fronty a P+1-vý sa tam nenachádza, Valcočlovek pivnicou prejde.

Časová zložitosť algoritmu je O(P²), kde P je počet stĺpov, pretože každú hranu pozrieme nanajvýš dvakrát (vo fronte budú oba jej prislúchajúce vrcholy) a hrán je maximálne (P+1)² .

Poznámky k riešeniu

Či sú dva stĺpy bližšie ako priemer valca je výhodnejšie testovať podmienkou (x1-x2)² +(y1-y2)² < 4R² ako sqrt((x1-x2)²+(y1-y2)²) < 2R, pretože v prvom prípade netreba odmocňovať. Používať pole na vzdialenosti sa tiež neoplatí, pretože každú vzdialenosť budeme pri správnom algoritme počítať nanajvýš raz (i keď na hranu sa pozrieme dvakrát).