30.5. 2016 - Holan - Burza

Opět Burza

http://forum.matfyz.info/viewtopic.php?f=247&t=9668

S komentářem anakondy:
"souboru Holan dovoloval maximalne tolik, jako ISINu, tedy klidne i 3000. Sam jsem to tak napsal a u ustni casti mne vysvetlil, ze na to stacil soubor jeden, ale zadne problemy s tim nemel:). Nakonec za 1"
nesouhlasím, možná mu byl student sympatický ale za tohle by mě poslal pryč dřív než bych to vůbec stačil doříct. S ukládáním do pole problém nebyl, na to ten 1 MB stačil. (ve smyslu array o 3000 prvcích)
vlastně i na začátku zadání explicitně zmínil že udělat si jeden soubor pro každý ISIN je vyloženě zakázané

Z Burzy jsem dostal 2 a nejspíš jen proto, že jsem mu v jednom bodě řekl, že předpokládám že umím soubor číst odzadu xD
Vypadl jsem ale potom na teorii, neuměl jsem setřídit soubor :-( pokud má někdo stejný problém:
https://en.wikipedia.org/wiki/External_sorting
Tu první část, kde načítáte 100 MB do paměti, tu setřídíte a následně sléváte jsem mu na místě vymyslel ale zakázal mi jí, prý by to nebylo dost rychlé.
Co chce je něco obdobného, bylo to prej jednou na přednášce ZS - na začátku je v souboru N 1-prvkových posloupností, soubor otevřu 2krát pro čtení a vždy slévám dvojice za sebou do nového souboru - mám soubor s N/2 2-prvkovými setříděnými posloupnostmi, opakuju...

Zajímavá informace ke zkoušce obecně by mohla být, že Holan ten papír co odevzdáte vůbec nečte. Stačí tam kreslit jen schematický obrázky a hesla pro vás a potom ústně mu v podstatě celej algoritmus stejně přeřikáte znova, s pomocí toho papíru.

Co ho už zajímalo víc byl pseudokód pro hlavní část algoritmu - v tomhle případě vybírání nejlepšího kursu akcie - kterej dost pitval a zkoumal i krajní případy, co se stane při rovnosti atd. S tim si teda na papíře určitě vyhrajte :-)

Složitosti a Očka vůbec neřeší, pokud to je aspoň v základu dobře a nedějou se tam věci typu Nkrát otevři soubor.

Řešení je úvodní soubor setřídit (hehe) podle ISINů, pak po blocích ISINů dělit na nákup/prodej... Tělo algoritmu už neni tak složitý když si dobře soubory připravíte. Určitě to jde s méně než deseti, pokud máte koule tak možná i pěti soubory (otevřenými v jednom okamžiku).

No tak ja som z burzy dostal za 1 a tu mate moje rady:

1. Nakreslit obrazok!! Holan ma obrazky rad. Je potom vidno co presne algoritmus robi.

2. Napisat vsetky dolezite casti! Tzn. nepredpokladajte, ze k vam bude zhovievavy, ak mu poviete nieco, co nemate napisane na papieri. Mozete doplnit detaily ktore ste nestihli napisat ale v podstate musi byt jasne, ako vase riesenie funguje.

3. V ulohe burza mate malo pamate. Tzn. nepocitajte s tym, ze si loadnete vsetky ISINy do pama a tak podobne. Odporucam pocitat s konstantnym mnozstvom pamate, potom nebude problem a vojdete sa aj do 1 kb.

4. Pseudokod: Minimalne mne velmi pomohol. Snazil som sa mu vysvetlit, ako funguje pocitnie kurzu, ale oc mi to neslo, tak som otocil papier na stranu s pseudokodom a Holan sa velmi potesil. Kede pseudokod bol jasne a prehladne napisany, tak mi moj pos bez rypavych otazok uznal a napisal mi jednotku.

5. Ak nechape nejakej casti vasho riesenia, tak mu to nakreslite/napiste este raz a zrozumitelnejsie.

Co sa tyka citania z disku, dajte si na to pozor. Ziadne citanie od zadu, otvaranie desiatich suborov a podobne. Snazte sa prist na riesenie, ktore vsetko vypocita naraz. Konkretne ja som si na zaciatku roztriedil subor podla ISINov a potom som zacal riesit samotne ISINy. Vytvoril som dva subory, jeden na nakup, jeden na predaj, roztriedil som ich zostupne podla ceny a prechadzal oba naraz. Najprv subor Prejad urcil kurz a potom som v subore predaj vypocital, kolko akcii sa preda pri danej cene. Tak som prechadzal oba subory, az kym sa pocet predanzch akcii zacal znizovat. Potom uz nema zmysel pocitat dalej a rovno mozete vypisa vysledok a pokracoval dalsim ISINom. Dokopy som mal naraz otvorene max 2 subory s tym, ze je to mozne vyriesit aj s jednym. Staci nakupy a predaje dat dokopy, roztriedit zostupne a... no, si uz rozmyslite sami.

Tak... Tolko k pisomnej casti.

Ak mu je jasne,ako vas algoritmus funguje, tak sa vas opyta este nejaku teoreticku otazku. Konkretne u mna sa pytal na hladanie medianu.

Na zaciatku som navrhol riesenie v O(NlongN), kde najprv roztriedite subor a potom vezmete prostrey prvok. Potom som spomenul Quicklect, co je alg. ktory hlada k-ty najvacsi prvok v linearnom case (priemerne).
Nakoniec sa maopyal, ako by som hladal napr. 1000 najvacsi prvok. Prisiel som s riesenim, ktore pouzivalo haldu, v ktorej sa udrzovalo 1000 najmensich prvkov. Hladanie tohto prvku by potom bolo v linearnom case, pretoze operacie v halde (insert a extract max) su sice logaritmicke, ale logaritmus 1000 je rovny 10 (čo som označil akokonštantu, ktora sa schova do thety) a navyse sa v nahodne usporiadanej postupnosti nebude do haldy insertovat tak casto :)

No.. a poto uz mi dal za jedna a stastne som isiel prec.

Tak... vela stastia pri skuske, snad vam moje rady nejak pomozu. Nezabudnite hlavne v tej pisomnej casti nakreslit pekny obrazok a pseudokod. Na nom sa vase riesenie vysvetluje lepsie.