Pravidla diskuze losů
- Buďte slušní, nepoužívejte expresivní jazyk, kroťte emoce a nenechte se vyprovokovat k napadání ostatních diskutujících.
- Neprozrazujte řešení, ani žádné jeho části, neprozrazujte žádné nápovědy k řešení, ani tipy. Nekažte ostatním hru.
- Diskuze neslouží pro komunikaci s organizátory, k tomu slouží vývěska umístěná v horní části stránky a e-mail interlos@fi.muni.cz.
Diskuze
Díky za moc hru. Náš tým se schází jen na šifrovačkách, takže bylo příjemné se opět vidět, zavzpomínat na minulé šifrovačky, pobavit se na nad vlastní blbostí, nad kiksy organizátorů, potěšit nad pár vyluštěnými šiframi, a kroutit hlavou nad některými řešeními. Líbila se mi omalovánka, PC hra, sifra s návodem. Nelíbilo se mi reseni radia (prestoze jsme meli OHMANDY – nevideli jsme s v tom smysluplne slovo). Napad s puzzle pekny, ale reseni ??? Sfingu jsme poznali hned, ale mysleli jsme, ze je to jen jedna z indicii, takze jsme hledali nejaky sportovni nebo vysokoskolsky klub (indicie: sedacky z poslucharny, mladi lide, demonstrace), ktery ma ve znaku sfingu. Kazdopadne diky za vasi praci a za prijemne chvile, ktere jste nam pripravili!
Je kromě nás ještě nějaký tým, který se zakopal na Knowing me, knowing you? Nejprve jsme vůbec netušili, že existuje česká verze, pak jsme objevili tuto: http://www.karaoketexty.cz/…-znam-757429 a připadalo nám to hrozně podezřelé, žel, v závěrečném zmatení jsme to chybné „D“ nezpochybnili… a když nás google na hledání „oh maddy česky“ stejně opravil na správné řešení, ještě jsme mu vynadali
V původní verzi bylo Winner Takes it All a zamýšlený cover byl Poslední jde sám… ukázalo se, že ale hledat unikátnost coverů je dost těžká záležitost (kdosi našel známější verzi od Helenky…). Takže vyloženě naposlední chvíli jsme tam dali Knowing me, knowing you a Slunečné pobřeží… Mamma Mia je bohužel už za naším horizontem :)
Polyglot zdá se, že P9 nevyřešil nikdo (ani autoři)… autorské řešení hlásí „Vaše řešení bylo odmítnuto: Eval script exited with non-zero code“
Podle toho „řešení“ bylo zadání špatně, minimálně co tam vidím, je že v PLos řetězec nekončí s koncem řádku… pominu-li zcela zamlčenou informaci o syntaxi „komentáře“ (řetězec na pozici příkazu, který nic nevykoná), možná v PLosu se nahradí (viz pokus s END=‚\n‘)
Sorry, ale tohle se moc nepovedlo. Škoda času co jsem s tím strávil, to jsem mohl počítat uhlík (pokud se neodstěhoval do Humpolce :-).
P4 – Jak mám chápat ppodmínku „zároveň se však nenechají předběhnoout žádným losem, který nenávidí stejného losa co oni“ – vždyť v případě s 10 losy skončí hned po prvním kole 4 před 3, přitom 3 i 4 nenávidí 1 čili by se 3 neměl nechat předběhnout 4
Predpoklad, že 3 i 4 nenávidia losa 1 nie je správny. V prvom kole sa 4 zameriava(nenávidí) losa číslo 2.
„… pokud los s číslem které je dělitelem jejich čísla, startuje DŘÍV než on. Takové losy nenávidí“ – tato podmínka je splněna pro dvojici 4–1. „Nenávist vůči takovém losovi zmizí, pokud ho předběhnou“ – tato výjimka se neaplikuje. Čili mi vychází, že 4 nenávidí (krom 2) i 1. Ale už jsme naštěstí pochopili, jak je to myšleno :)
Stačilo číst pořádně zadání :-)
Pohybují se následovně: • před začátkem každého kola si každý los zjistí, který takový nenáviděný los startuje nejpozději a do konce kola ho předběhne a zůstane před ním,
Díky za super hru! Naše bilance v závěrečném okamžiku hry je 2× frustrace a 1× radost, která ale stála za to: Honza s Bulikem finišovali Losí vesnici, tak tak stíhali počítat cesty ve výsledném grafu. Opisuju jejich řešení, posílám 19:57:54, je to špatně. Někde musí být chyba/y. Honza láteří, co to po nás orgové chtějí za nesmyslné počítání. Nemůžeme to stihnout opravit. Ale taky můžeme mít štěstí, musíme to zkusit. Přepočítávají náhodnou dvojici, je v pořádku. Přepočítám první, kterou vidím, a místo 17 mi vychází 20! Honza to jde přepočítat po mně, dívám se ale na hodiny: 19:59, vteřiny nejsou vidět. Posílám úpravu bez konzultace s ostatními, teď nebo nikdy. A prošlo to. :) Martina
Přidávám se s díky, užil jsem si to nejvíc, jak si to jen detašovaný neprogramátor užít může. Děkuji obzvláště za úlohu L4 Mince: hodina práce, dvě rozbitá prasátka, nějaký náhodný software na spektrální rozklad audia, dva neúspěšné pokusy přiřadit to tak nějak po citu, a ten třetí konečně euforie! Většinu úloh jsem ani neviděl, z těch, co jsem řešil, se mi moc líbil i Losmonaut a Modrá. Dalibor
A nech tu ešte pospamujem diskusiu, tu je ešte linka na moje riešenia (oproti hre obohatené kde-tu o nejaký komentár), keby niekoho zaujímali: https://people.ksp.sk/…nterlos2016/
-- mišof
Ad P2: my jako bruteforce variantu uvažovali prozkoumání všech permutací (s vyloučením opakujících se) a jejich validaci. (Takových řešení by mělo být 1 307 674 368 125, vaše řešení prověřuje). Vaše řešení bych bruteforcovým nenazval, poněvadž zkouší a backtrackuje (current[i] = current[i+x] = x; go(x-1); current[i] = current[i+x] = 0;)
Vo všeobecnosti (teda pre n dvojíc čísel) má aj to moje backtrackujúce riešenie časovú zložitosť zrejme horšiu než exponenciálnu od n, keďže niekoľko prvých dvojíc sa dá uložiť skoro nezávisle. Stále to skúša „všetky“ možnosti, len to výrazne skôr odhalí a zahodí veľa vetiev, ktoré k riešeniu nevedú, takže je to pre malé n ešte rozumne rýchle.
Všetkých permutácií množiny {1,1,2,2,…,8,8} je 16! / (28) = 81 729 648 000.
Ano, počet permutací je jiný, omylem jsem při počítání permutací s opakování změnil znaménko z * na +… :D
P2 – Tvrzeni ze reseni v pythonu trva 45 min mi prijde mirne prestrelene. Nabizim celkem primocare reseni ktere sebehlo za cca vterinu. http://atrey.karlin.mff.cuni.cz/…terlos/p2.py (a pocitac taky nemam nejmladsi) . Spravnou odpoved dalo :)
Naše autorské řešení v C++ se podařilo optimalizovat až na 1.5 minuty (ale výrazně používá std kolekce, což ho zpomaluje než když by běželo přímo v intech, jako to má například Ubertým). Python řešení bylo uveden pro ilustraci, kolik zabere stejný způsob provedení v Pythonu (reálně by také mělo jít optimalizovat na čísla).
Mně to taky běželo v Pythonu pod vteřinu. Klíčové IMO je správně backtrackovat a odřezávat slepé cesty. Já nejdřív iteroval jedničky přes pozice (0,1), (1,2), (2,3), …, pak dvojky přes pozice (0,2), (1,3), …, pokud tam bylo volno atd.
Tohle jsem psal rovnou v C, obávaje se (z odhadu počtu permutací), že standardní backtrack to zase tak moc neořeže a efektivní řešení je nějaké chytřejší, takže to bude pořád na dlouho. Což teda byl totální kanon na vrabce. Výsledný program (nijak neupravený z hry) dávám pro pobavení na http://physics.muni.cz/~yeti/tmp/p2.c a čas běhu je něco jako 9 milisekund, pokud má ještě smysl věřit time(1)…
Řešení přes iteraci dvojic je hezké (a přemýšlím proč mě nenapadlo) :)
Já bych se chtěl zeptat, jestli někdo zkoušel řešit ty vodíky jinak než textovými substitucemi. Já jsem si za každý atom připsal 0 (a v tom pak počítal počet objevených vazeb), za %XY přičítal jedničku (lhostejno kam vazba vedla), nahradil [-=#] za \1,\1 (-,– =,= a #,#), pak jsem nahrazoval ty „půlvazby“ za přičtení čísla k příslušnému sousednímu prvku. A pak už jsem nejvnitřnější závorky spočítal a nahradil jen vazbou k předchozímu prvku, kterou jsem následně taky započetl. A tak dokola, dokud bylo co nahrazovat.
Ručne som zistil, ktoré S, N, P musia mať stupeň 4, 5, 6 (takých bolo len pár) a prepísal som ich vo vstupe na iné znaky. Potom pre každý atóm vieme, aký má stupeň. Keby neboli vôbec pospájané, tak je presne toľko vodíkov. Každá väzba zmenší počet vodíkov o 2. Takže napr. každé ‚#‘ zmenší počet vodíkov o 6, každé ‚%‘ len o 1. Zátvorky už spokojne ignorujeme, relevantné boli len pri tom ručnom prepise. O chvíľu uploadnem kód.
-- mišof
Nejdřív jsem pomalu 40 minut psal a testoval program, který z toho stejně nezískal smysluplný text…
Pak jsem se naštval, nainstaloval OpenBabel (http://openbabel.org/) a nechal si SMILES převést na tvar, který vodíky má explicitně (na tři minuty i se čtením dokumentace babelu). A nyní přichází pointa: dvě písmena mi vyšla stejně jinak než autorsky ;-) Sice jsem to dohaluzil, ale…
@mišof: to je ovšem dost podlé, dělat preprocessing ručně :-). Ale uznávám, že s tímto pak bylo řešení dost triviální, protože to stačilo už jen posčítat, nemusel člověk řešit k čemu jaká vazba patří.
- Yenya
Díky za hru! Omalovánková šifra velmi potěšila a kubické křivky jakbysmet.
Jen mne trochu zklamala vágnost zadání u mnoha programovacích úloh. Jazyky u Polyglota byly popsané naprosto nekompletně (z čeho třeba plyne, že příkaz smí začínat řetězcem?). Zadání Tower defense bylo sporné (dostřel 2 neodpovídá obrázku). U Výherního losa není jasné, zda se nenáviděnost určuje na začátku kola nebo i na konci (což způsobí +/- 1 rozdíl ve výsledku). A nakonec u LHD z ničeho neplyne, zda se sloučené zastávky v trase linky nahradí jedinou, nebo jestli se přepíší na více výskytů nového jména. Je to škoda, pokusy o interpretaci zadání jsme ztratili spoustu času.
+1. Už je bohužiaľ tradíciou, že Interlos má niekoľko úloh (zväčša programátorských) s nedostatočne / zle špecifikovaným zadaním. Tento rok nebol výnimkou. Podpisujem sa pod úplne všetky vyššie uvedené nejasnosti a pridám, že:
- v P1 chýbalo povedané že sa otáčanie neskladá, tú možnosť som vyskúšal prvú čisto preto že sa implementuje ľahšie, hoci podľa mňa má menší fyzikálny zmysel – otočenie prvého ramena by malo otočiť celú súradnicovú sústavu zvyšku kolotoča.
- v P1 mi chvíľu trvalo pochopiť že sme v rovine a nie v priestore :)
- P4 si myslím, že je underspecified, pravidlám v zadaní podľa mňa zodpovedajú viaceré „topologické“ usporiadania a správnu interpretáciu zadania som trafil až na tretí pokus, tipovaním čo vlastne chcete podľa príkladu v zadaní :(
- P6 v príklade zlučovania chýba fáza kedy sa (postupne? naraz?) A, F, G každá zlúčia so svojim okolím
- v P6 na linkách existujú „slučky“ (2× po sebe stojí na tej istej zastávke), tie v zadaní nie sú špecifikované vôbec a myslím si, že upresnenie zverejnené počas hry bolo nesprávne – moje riešenie bolo akceptované až vtedy, keď som aj slučky bral ako hrany, čo mohlo zvýšiť stupne niektorých vrcholov.
-- mišof
Tip do příštího roku: zkuste dát ke každé programovací úloze malá testovací vstupní data a vzorový výstup, abychom si mohli snadno zkontrolovat, že jsme správně pochopili zadání. Já také u některých úloh neměl úplně jasno, co tím chtěl básník říci. Neberte to jako kritiku, jen jako návrh. Interlos byl letos opět super!
+1
U některých úloh toto bylo, např. P2, P4, P5 (zde by mohl být příklad trochu méně triviální). Fakt to hodně pomáhá.
+1. Posílal jsem během hry dva dotazy na upřesnění zadání.
Někde mi pomohla lenost – u P1 je řešení s rigidním závěsem fyzikálně správnější (obzvlášť když je na dalším závěsu taky motor, takže se nemůže volně protáčet), ale volně se protáčející závěsy bylo prostě triviální vyzkoušet jako první.
Příklady by rozhodně pomohly, ale prosím konzistentní se zbytkem textu.
Obrázek dostřelu 2 u Tower defense mi na rozdíl od Pomocné školy přijde OK, protože text nepíše v jaké metrice a v diskretizované Euklidovské to takhle vychází.
Chybné dopsání vodíků u druhého příkladu P7 (spodní uhlík musí mít dva, stejně jako druhý ve vodorovném řetězci – ne tři a jeden) už je trochu víc znejisťující…
Úloha P6: Vzorové riešenie v Kotline sa mi zatiaľ nepodarilo skompilovať – kompilátor čo som poťahal hubuje na toMutableMap().
Vzorové riešenie v Pythone je ale celé mimo. Zle načítava vstup (nestripne načítaný riadok), zle parsuje vstup (preskočí posledný úsek každej linky), následne zle rieši úlohu (nespája dostatočne komponenty, toto je na rozdiel od ostatných seriózny bug) a na záver zle odstraňuje duplikáty (správne je odstraňovať len po sebe idúce). Nedá ani len správny výstup pre vstup použitý v hre. Toto má celé byť (ehm ehm, ak správne chápem zadanie :P ) celé jeden veľký komponent, až na „a“ a „m“.
Príklad, na ktorom to spájanie komponentov v pythonovom riešení skoro určite zlyhá (aj keď rôzne spustenia môžu viesť k rôznemu výsledku, lebo bugy):
1: a – b – d – e – g – h – j – k – m – n – p – q – s – t – v 2: a – c – d – f – g – i – j – l – m – o – p – r – s – u – v
(správny výstup a – d – v)
-- mišof
Vetu začínajúcu „Toto celé“ treba ignorovať, omylom tam ostala z draftu postu. Pred „2:“ je newline.