Zkouška 28.5.2007

"Malou úlohu" na dynamické datové struktury dostal každej jinou, typicky něco na LSS a binární stromy - seřadit, zrušit, sečíst dlouhá čísla, vyhodnotit výraz atd...

Velká úloha:
Máme tabulku čokolády 10x10 políček. Délka strany políčka je 1. V čokoládě jsou oříšky a rozinky (kulaté, na vstupu jsou jejich souřadnice a poloměry), jejich počet je <= 1000. Máme napsat program, který určí, jak nesnadněji rozřezat čokoládu na 3 díly. Nejsnadněji s míní s co nejmenší prací, přičemž rozříznuzí čokolády o délce 1 stojí práci 1, ořechu o délce 1 stojí práce 5 a rozinky o délce 1 stojí práci 1/2. Každá hrana stojí práci v poměru kolik je tam čokolády, rozinek a ořechů. Řezat se smí jen po hranách, ale libovolně klikatit atd. Čokoláda má konstantní výšku, řezání ořechu středem i u kraje stojí stejně práce (nezáleží na výšce ořechu), prostě je to všechno jen 2D. Řezáním čokolády nesmí v žádném kusu vzniknout díra. K dispozici je paměť maximálně 1MB. Dále nám dali k dispozici funkci DélkaTětivy(xstřed,ystřed,R,y), která vrátí délku tětivy ořechu nebo rozinky o poloměru R, která protíná hranu na souřadnici y. Výstupem programu mají být hrany, které se mají řezat a cena (práce).

ja som mal ako mini program spravit vypisanie stromu pomocou priechodu do sirky.. nezabudnite ze frontu musite odalokuvavat, ako sa to stalo mne..

Jo, to moje "mala" uloha byla velmi opravdu bezva, mate soubor, ve kterem jsou cisla (obecne dlouha cisla), ktera mohou byt i zaporna, a ta se maji vsechna secist. Paradni uloha, akorat na 1h docela zabijejici, rekl bych.

Prý může být ještě hůř, někdo tam měl dokonce násobení čísel ve spojáku nebo tak. Je pravda, že tam zase skoro odpadá problém se zápornými.
Já teda osobně měl klasiku - průnik dvou binárních stromů - a taky mi to zabralo skoro celou hodinu.

Jinak ta velká úloha vypadá těžká, ale zase tak složité řešení nemá. Po konzultaci s Topferem (trochu mi vypíchl věci, které se daly ušetřit) by to mělo být asi takhle:

Nejprve uděláme ohodnocený graf, ideálně přímo v matici (to je docela dobrá reprezentace).
Pak si uděláme pomocí Floyd-Warshalla nebo Dijkstry tabulku všech vzájemných vzdáleností v tom grafu.
Máme tři možnosti, jak to může vypadat:
a) Disjunktní hrany - čili najdeme dvě nejmenší vzdálenosti mezi body na okraji
b) Jeden společný bod - pro každý vnitřní bod najdeme tři nejbližší okrajové body a hledáme minimum součtu
c) Dva společné body (oko s cestami na okraj) - pro všechny dvojice bodů spočítáme minimum součtu nejbližších vzdáleností těch bodů od okraje + dvou nejkratších cest mezi nimi (nejkratší máme v tabulce, druhou nejkratší ještě nějak musíme ošetřit)
Výsledek je minimum z a), b), c).

Neměl jsem pořádně domyšlené to c), takže mi to vycházelo O(n^8), jde to i na O(n^6) - jenom se musí dovymyslet ta druhá nejkratší cesta. Jako n beru 10 - čili šířku tabulky.

jako malý příklad jsem měl stvořit ze vstupní posloupnosti čísel BVS mimo 3 největších čísel

• celkem jednoduché jen jsem se lehce zamotal do uchovávání těch 3 hodnot

velký příklad jsem řešil podobně jak je popsáno v příspěvku o jedno výš, pospal jsem 5 A4, problém byl ale v tom, že mi byl ukázán protipříklad

z teorie jsem dostal vnitřní třídení

Wolda wrote:Jo, to moje "mala" uloha byla velmi opravdu bezva, mate soubor, ve kterem jsou cisla (obecne dlouha cisla), ktera mohou byt i zaporna, a ta se maji vsechna secist. Paradni uloha, akorat na 1h docela zabijejici, rekl bych.

Tady je docela dobry napad pocitat si zvlast kladne a zvlast zaporne a az nakonec to odecist (odecist mensi od vetsiho a znamenko doplnit).
Pri prubeznem odecitani by bylo asi docela blbe resit "zaporne + zaporne", "zaporne + kladne s prelezem pres nulu" a tak..

ano ale ono je to aj tak problem stihnut, dokonca by som povedal ze je to nemozne. ja som mal tu istu ulohu a nestihol som ani polovicu. ke som si to potom cvicne napisal doma tak to vyslo na viac ako 150 riadkov...

Z toho zadání mi není úplně jasné, jaké jsou přípustné řezy. Je to myšleno na 3 díly o stejném obsahu? Protože pokud ne, tak mi z toho vychází, že můžu odříznout třeba 2 čtverečky, čímž mi vzniknou 3 díly. To sice nic nemění na faktu, že tam můžu najít delší cestu u které se míň nadělám, ale daly by se tam potom možná vymýšlet nějaké heuristiky.