Zk 22.2.2010
Napsal: 22. 2. 2010 20:20
Ja byl ten, kdo prisel a nebyl prihlaseny - vzhledem k tomu, ze mista byla dost (neprislo zdaleka vsech 20 lidi), to nebyl problem; pokud se na nejaky z poslednich terminu v SISu uz nevejdete, doporucuji prijit stejne, pravdepodobne Vas vezme.
Celkem bylo tak 15 lidi, cca 3 lidi to vzdali po kratke chvili, mezi ostatnimi iteroval. Ja jsem dostal jednu z nejlepsich moznych veci , vyhledavani v setridene posloupnosti. Sepsal jsem snad celkem presne obecny algoritmus i vsechny zakladni modifikace vcetne "trislovnych dukazu" slozitosti (to je fakt trivialni, az na ocekavane O(loglogN) u interpolacniho, a to se zase zrejme nedokazovalo a nezkousi vubec). U zobecneneho kvadratickeho jsem chvili musel vzpominat, jak je to s temi odmocninami, ale s matnymi vzpominkami se dal algoritmus uhadnout, jen jsem zapomnel, ze unarni kroky jdou tim smerem, kterym je prvek (ne vzdy dopredu) - ale to jsem rychle opravil, kdyz se mne na to zeptal. Nejvetsi problem byl se slozitosti, u ocekavane jsem si jen pamatoval, ze se da ukazat, ze v ramci jednoho interpolacniho kroku je ocekavany pocet tech ostatnich konstantni, ale neumel jsem to dokazat; tak mi nabidl, ze mne "jeste necha se s tim morit", nebo mi da rovnou trojku, kterouz jsem s povdekem prijal. Dokonce mi pak pri zapisovani znamky i docela srozumitelne vysvetlil, jak se to vlastne dokazuje, jdu to pripsat na wiki.
Celkem bylo tak 15 lidi, cca 3 lidi to vzdali po kratke chvili, mezi ostatnimi iteroval. Ja jsem dostal jednu z nejlepsich moznych veci , vyhledavani v setridene posloupnosti. Sepsal jsem snad celkem presne obecny algoritmus i vsechny zakladni modifikace vcetne "trislovnych dukazu" slozitosti (to je fakt trivialni, az na ocekavane O(loglogN) u interpolacniho, a to se zase zrejme nedokazovalo a nezkousi vubec). U zobecneneho kvadratickeho jsem chvili musel vzpominat, jak je to s temi odmocninami, ale s matnymi vzpominkami se dal algoritmus uhadnout, jen jsem zapomnel, ze unarni kroky jdou tim smerem, kterym je prvek (ne vzdy dopredu) - ale to jsem rychle opravil, kdyz se mne na to zeptal. Nejvetsi problem byl se slozitosti, u ocekavane jsem si jen pamatoval, ze se da ukazat, ze v ramci jednoho interpolacniho kroku je ocekavany pocet tech ostatnich konstantni, ale neumel jsem to dokazat; tak mi nabidl, ze mne "jeste necha se s tim morit", nebo mi da rovnou trojku, kterouz jsem s povdekem prijal. Dokonce mi pak pri zapisovani znamky i docela srozumitelne vysvetlil, jak se to vlastne dokazuje, jdu to pripsat na wiki.