Pergel 28.5.2018

Pomsta postmistra Antonina
Postmistr Antonin se chce pomstit svemu zamestnavateli Ceske Poste s. p. a pri sve posledni smene pred duchodem chce postavit co nejvyssi vez z krabic, kterou nasledne demonstrativne zapali.
Vstup: Posloupnost krabic, ktere maji ruznou vysku, sirku, delku. Jsou oznaceny krabice, ktere muzeme rotovat a ktere ne (protoze by se rozbil obsah krabice).
Vystup: Vyska nejvyssi mozne veze a posloupnost tech krabic, ze kterych dokazeme tuto vez slozit.

Podminky skladani krabic: Pri skladani krabic musi byt vzdy podstava dolni krabice vetsi nebo rovna podstave horni krabice (tj. napriklad krabici o podstave 2x2 nemuzeme postavit na krabici o podstave 1x2 ale muzeme na sebe postavit dve krabice o podstavach 2x2).
Skladat krabice na sebe muzeme pouze v poradi, v jakem nam prichazely na vstupu (tedy pokud nam prijdou na vstup pouze dve krabice, prvni bude mit podstavu 2x2 s vyskou 2 a druha podstavu 3x3 s vyskou 3, pak nejvyssi mozna vez, kterou dokazeme sestavit z takto zadanych krabic, ma vysku pouze 3).
Postmistr Antonin si pamatuje, v jakem poradi mu krabice budou prichazet (protoze je predtim vlastnorucne skladal na pas), tedy si muze naplanovat, kterou krabici pouzije a kterou na pasu necha.

Doplnil bych, že označená krabice není povoleno rotovat kolem vodorovných os - kolem svislé ano.
K podmínkám skládání - krabice mají tvar kvádru a skládají se tak, že jsou příslušné hrany podstav rovnoběžné, nelze je tedy otáčet v různých úhlech, ale vždy jen o 90 stupňů. Krabice lze postavit na sebe, když horní krabice na žádné straně nepřečnívá přes dolní a horní je v posloupnosti za dolní. Joffreyho příklad nefunguje, protože neudal výšku krabic, takže nelze výšku věže určit.

K ústní zkoušce (u Pergela):
Ptal se mě na definici složitosti problému, óčkovou, thétovou a omegovou notaci, a chtěl dokázat, že třídění porovnáváním má složitost théta n log(n) - chtěl tedy dolní i horní odhad. Ukázal jsem mu mergesort a dal dohromady náznak důkazu dolního odhadu z Průvodce a byl spokojený.

domestomas wrote:Joffreyho příklad nefunguje, protože neudal výšku krabic, takže nelze výšku věže určit.

Sorry, text jsem upravoval a zapomnel dopsat vysku. Hned to opravim.

Dodal bych k zadání:
Cíl byl nalézt řešení s polynomiální časovou složitostí. K dispozici jsme měli stovky MB.

Řešení:
Úloha se mohla řešit dynamickým programováním. Jde navázat na hledání nejdelší klesající (resp. rostoucí) posloupnosti. Co jsem slyšel, tak se vyskytlo řešení i přes grafové algoritmy.

K ústní zkoušce (u Holana):

1. část)
   Čekal jsem na čtvrtém patře u výtahu, v čas na který jsem se zapsal si pro mě přišel a zavedl před svůj kabinet. Seděli jsme u jednoho ze stolků na chodbě.
   Tam čekala moje písemná práce.
   Dopředu ji nečetl. První otázka, která přišla byla, jak jsem řešil daný problém. Při vysvětlování jsem trochu komolil slova, ale nechal mě všechno v klidu vysvětlit, působil příjemně. Občas se zeptal na nějakou nejasnost. Ptal se, jakou jsem měl paměťovou a časovou složitost, a po očku pozoroval písemnou práci, jestli mám dané věci popsány, ale celkově ji nečetl ( celý algoritmus mě nechal jen vysvětlit ). Nakonec chtěl probrat postřehy a ptal se na jiná možná řešení. Celkově to byla spíše konverzace ohledně řešení, hlavní ale byla funkčnost algoritmu. Na papíře jsem ale neměl všechno funkční a často jsem v tom měl chaos, ale nebyl to žádný problém. Berte v potaz, že mu z písemky můžete číst, takže si do ní pište poznámky i pro sebe.

2. část)
   V momentě, když jsme probrali písemnou část, přišla jedna otázka. Ptal se co, jak, proč je Dynamické programování a chtěl nějaké příklady (vysvětlovat je nechtěl), stačilo popsat pár větami. To bylo všechno.

Pozorování:
Holan lpí více na písemné části, snaží se váš algoritmus pochopit. Má rád pseudokód, obrázky (ani jedno jsem neměl). Pokud budete mít správné řešení, i když nemusí být optimální, příjde jednodušší otázka vetšinou ja nějaký grafový algoritmus, statické\abstraktní třídy a virtuální metody, haldu... chce pouze vysvětlení.
Pergel naopak, písemku asi ani nečte, jen se zeptá na řešení a to nějak odkýve. Celkově mám dojem, že písemka je pro něj jen zápočet a pak vám dá nějaký set z otázek. (někdy i s měnšími důkazy)
Když se zapisujete na ústní, jeden sloupec znamená Holan a druhý Pergel (ale nevíte který), takže můžete mít i toho ke komu nejste zapsáni.

Na zkoušku si doporučuji vyzkoušet pár příkladu co jsou tady na fóru, a nepodceňujte definice a základní pojmy.

Nevím jestli je to pravidlem, ale Holanův sloupeček měl půlhodinové rozestupy (zapsat se lze na 10:00, pak 10:30, ...), kdežto Pergel měl patnáctiminutové. :D