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
Řešení P7: Jen 232 kombinací věcí? Nemá smysl ztácet čas přemýšlením, projedu je triviálním prográmkem v C a budu se mezitím věnovat jiné úloze. Doběhlo to asi za pět minut.
(Yeti)
Tohle jsem taky zvažoval, ale nakonec jsem napsal obyčejný backtracking v Perlu. Trochu jsem to prořezával – když jsem přelezl součet, nevnořoval jsem se do další rekurze, a z druhé strany jsem si držel součet toho co ještě zbývá k zařazení, a pokud jsem zařazením všeho zbývajícího nemohl dosáhnout velikosti batohu, tak jsem taky nelezl do další rekurze. Rozhodně jsem nedělal ty složitosti, které popisuje autorské řešení (jestli mu teda aspoň přibližně rozumím :-)
Přesný čas běhu nevím, ale nějaké malé minuty.
Jasne, autorské riešenie riešilo aj to, keby úloha vyžadovala pre batohy zoznamy vecí ktoré v ňom sú, a je vlastne popisom riešenia 0/1-Knapsack problému dynamickým programovaním z https://en.wikipedia.org/…sack_problem#… .
– Ján (autor úlohy)
No nevím, seznamy věcí by šlo Yetiho i mým přístupem získat triviálně.
- Yenya
Možno je len zložito napísaný popis, keď si prečítam tvoj popis riešenia, vyzerá to veľmi podobne ako to moje, akurát, že to vzorové už má rekurziu vyrovnanú do iterácie a zoznamu „predošlých“ výsledkov.
Ešte jednoduchšie riešenie od niekoho kto testoval tu: `
items = list(map(int,
„61170 51206 63455 37985 47604 61260 51853 27713 39404 25287 20853 37492 65262 22132 8396 24308 43064 50827 30481 65172 63318 17272 60912 58712 20444 48950 9463 4627 13382 13774 22912 6723“.split()))
backpacks = list(map(int,
„1111062 666431 848372 1096306 503315 1110531 708859 1173231 681602 672415 1086793 806143 505906 776307 616308 525781“.split()))
max_capacity = max(backpacks)
possible_capacities = {0}
for item in items:
next_possible_capacities = possible_capacities.copy()
for capacity in possible_capacities:
next_capacity = capacity + item
if next_capacity <= max_capacity:
next_possible_capacities.add(next_capacity)
possible_capacities = next_possible_capacities
print(‚item‘, item, ‚number of capacities‘,
len(possible_capacities))
result = [int(backpack in possible_capacities) for backpack in backpacks]
print(''.join(map(str, result))) `
- Ján (autor úlohy)
Nemůže ten seznam možných výsledků být brutálně paměťově náročný? Největší batoh má kapacitu jen o kousíček menší než součet všech věcí, a možností výběru (a tedy přibližně i možných kapacit) je 232.
Já jsem to rekurzil do nalezení řešení pro každý batoh zvlášť. Což by mi i triviálně dalo informaci, které prvky se do batohu použily, pokud bych ji potřeboval.
Zo zoznamu vyhadzuješ duplikáty. Po spracovaní každej veci je zoznam nejakou podmnožinou {0,1,…,S}, kde S je súčet dovtedy spracovaných vecí. A keďže veľkosti vecí boli malé, možných kapacít je výrazne menej ako 232.
To vyhadzovanie duplikátov v podstate spôsobí, že toto riešenie je ekvivalentné s riešením pomocou rekurzie s memoizáciou (cacheovaním).
-- mišof
Ještě jsem chtěl poděkovat za hru. Jak mi letos to programování moc nešlo, tak jsem si aspoň taky trochu zaluštil i šifry… Z toho, co jsem viděl, se mi asi nejvíc líbila S8 (plakáty).
A doplnil bych nějaká alternativní řešení: S3 se otevře v GIMPu, klikne na očičko u Background a přečte řešení MASO. Čísla i čísla framů jsme sice taky poctivě opsali, leč k řešení to na rozdíl od uvedeného postupu nevedlo.
A alternativní řešení P5 (tady trochu zklamání, protože když jsem to konečně dneska zdebugoval, tak to okamžitě vydalo správnou odpověď, ale za hry to vydávalo akorát nesmysly). Když si vyberu nějaký typ lístečku, říkejme mu B jako Bariéra, tak se mi fronta rozdělí na bloky B a bloky ne-B. Existuje-li nějaké pořadí odcházení, kdy všichni odejdou, tak existuje i takové, které začíná odejitím jednoho celého bloku B anebo jednoho celého bloku ne-B (důkaz nechávám čtenáři, hint je ta bariéra). Tudíž prostě nějaký zkusím, problém se zmenší a můžu řešit menší problém.
To by ještě neběželo úplně okamžitě, takže přidám následující úvahy: 1. Kdo se vyskytuje pouze ve skupinkách > 1, může odejít kdykoli jakkoli, a tedy je odstraním na začátku. 2. Jako B vybírám vždy typ lístečku, který má nejméně souvislých bloků, což drží rekurzi na uzdě. 3. Začínat odcházením krajních bloků nepomůže, tak to ani nezkouším. 4. Výsledky se, jak navrhuje i autorské řešení, cacheují.
Kdyby se někdo chtěl pobavit, vyčištěný skript je na http://physics.muni.cz/~yeti/tmp/p5.py
(Yeti)
Moje riešenie S3: chcel som si mergnúť dokopy všetky výskyty cifier, tak som cez imagemagick spojil dokppy všetky framy metódou „lighten“ (zjednodušene, pre každý pixel zoberiem jeho najsvetlejšiu verziu). Toto mi povedalo, že z toho žiadne pekné dvojciferné čísla nevylezú, tak som bol smutný. Tak som ešte skúsil darken, average a multiply a pri poslednom z toho vyšlo „maso“, tak som odovzdal maso a prestal byť smutný :)
-- mišof
convert S3-nyanlos.gif los.png ; convert los*png -compose multiply -flatten solution.png
Prošel jsem si autorské řešení P5 a jsem trochu zklamán. Z hlediska hry je určitě adekvátní – je rozhodně stručnější než moje, i kdybych vymazal všechny komentáře, a doběhne asi za tři minuty, což je OK.
Zklamán jsem z toho, že pracuje s jednotlivými losy a chybí v něm elementární úvaha, že stačí pracovat pouze s celými skupinkami. Existuje-li postup odcházení, při kterém odejdou všichni, tak existuje i takový, kdy vždy odcházejí kompletní skupinky. Skupinka tvoří bariéru, takže odejití po částech lze vždy nahradit odejitím celé skupinky, když odcházela její poslední část.
Ad S3 nyanlos: pomocí gifsicle jsem rozbil animovaný gif na obrázky. Obrázky jsem prohlídl a smazal jsem všechny, kde nebyly číslice. Zůstalo přesně 26 obrázků s číslicemi. Tohle byla opravdu jen nevyluštitelná náhoda?
Taky děkuji organizátorům za hru, skvěle jsme si ji užili i když jsme byli rozkročení na dvou kontinentech. Já si opět potvrdil, že neumím programova – ze třech úloh, co jsem zkoušel jsem úspěšně zvládl jedinou :-/ Ale holt interlos je programovací a vymyslet úlohu, která není nějakým zamaskovaným informatický problémem na který existuje knihovna nebude jednonuché.
Z toho, co jsem viděl bych chtěl vyzdvihnout především L3 (Miny), S1 (Stříhací), S4 (Třípatrová) a S7 (plakáty), fakt super nápady a u S7 i boží grafické zpracování.
Naopak S3 (Nyanlos) a S5 (Futurolosia) měly sice zajímavý nápad, ale nikdo je nevyluštil (autorsky), což mi přijde škoda a S6 (QR kód) a S9 (Zvuky) mne taky moc nenadchly. Všechny bych je spíš označil za „počítačové úlohy“, které by podle pravidel mělý být v množině P (ale letos tam žádné nebyly). Takže jestli mi chcete udělat radost, tak uberte programování, změňte kategorii u počítačových úloh a přidejte šifer. Anebo upravte pravidla. Anebo ne. Já se za rok zúčastím v každém případě :-)
Honza
To jsem nečekal, že se dočkám autorského řešení ve smyslu „odhadneme jméno problému, vygooglíme knihovnu pro nějaký náhodný jazyk, použijeme knihovnu naším krásným dvacetiřádkovým programem“. Umíte někdo popsat, jak vypadá skutečné řešení problému? Jde nějak iterovat od řešení získaného hladovým algoritmem k lepším řešením?
Ja mám k P2 riešenie ktoré som celé implementoval ja. Robím to tiež cez tok s minimálnou cenou. Ľahko implementovateľné polynomiálne riešenie sa dá založiť na pozorovaní, že keď máš tok veľkosti V1 ktorého cena je najmenšia spomedzi všetkých tokov veľkosti V1 a nájdeš najlacnejšiu zlepšujúcu cestu (*1) ktorou vieš veľkosť toku zväčšiť o V2 tak nový tok, ktorý dostaneš, bude najlacnejší spomedzi všetkých tokov veľkosti V1+V2.
Algoritmus je teda „začni s nulovým tokom, while existuje zlepšujúca cesta nájdi a použi najlacnejšiu z nich, keď skončíš, máš najväčší tok s minimálnou cenou“.
(*1) „zlepšujúcou“ v štandardnom tokovom zmysle, cena sa počíta tak, že keď na hranu pridávaš tok, tak dáš plus jej cena, keď z hrany uberáš tok tak mínus jej cena.
-- mišof
@mišof: hmm, musím to promyslet, ale třeba to pochopím, díky. Jinak gratulujeme, byli jste dobří.
- Yenya (i ostatní nepodepsané příspěvky segmentation fault)
Vďaka. Ak to pomôže, tu je (trochu neefektívna ale zato v rámci možností stručná) implementácia: https://ideone.com/6osvht
-- mišof
Acho jo, holt jsem se příliš upnul na to, že řeším logické úlohy a neprogramuju :(
Přitom to, že jde o tok, bylo jasné, a algoritmus na max flow (Dinic a MPM) byla asi poslední komplexní věc, co jsem programoval (no jo, je to už „pár“ let …)
-- bulik
Díky velice za vaše úsilí při přípravě hry, líbila se mi moc Stříhací a Třípatrová, škoda že jsme nedotáhli QR kód. Co se týče Myslím si číslo – jakože cože? Vymyslela jsem krásné řešení a bylo to úplně jinak: pro přehlednost jsem udělala substituci #1=a, #2=b atd… a pak mi tu vznikly rovnice – spojené obloukem: a*1=f, b*3=a, c*2=b atd… vyzkoušením dosazování různých čísel od 1 do 9 za a) mi nakonec vyšlo toto řešení: a=5 = PET = tri znaky … takze trojku dosadime do prvni rovnice a*1=f 5 = PET 3*1=3 TRI …3.. f=3 dalsi rovnice: f*5=e 3 = TRI 3*5=15 PATNACT … 7.. e=7 e*4=d 7 = SEDM 4*4=16 SESTNACT … 8.. d=8 d*6=c 8 = OSM 3*6=18 OSMNACT … 7.. c=7 c*2=b 7 = SEDM 4*2=8 OSM … 3.. b=3 b*3=a 3 = TRI 3*3=a DEVET … 5.. a=5 Bohužel číslo 537873 nebylo správné ;).
Orgove – co rikate na tohle reseni? :-)
Ahoj, to riešenie je síce pekné a prepracované, ale obsahuje zásadnú chybu: medzi políčkami #1 (a) a #6 (f) je v zadaní znak nerovnosti. Pričom tvoje riešenie kladie a*1 = f, teda a = f čo je jasne v spore s pravidlom, že #1 a #6 sa nesmú rovnať. Takže tvoj nápad bohužiaľ nezodpovedal zadaniu. Maťa (autor úlohy)
No prave ze ne, v mem reseni: a=5 a f=3. a=5 5*1=PET=f=3 (tri znaky) Hodnota vysledneho cisla v reseni odpovida poctu pismen matematickeho vysledku rovnice.
V tom pripade ak spravne chapem tvoje riesenie:
!!a = 5 [TRI] (do rovnic dosadzam pocet znakov) ⇒ a * 1 = f ⇒ 3 * 1 = 3 ⇒ f = 3 [TRI] ⇒ f * 5 = e ⇒ 3 * 5 = 15 ⇒ e = 15 [SEDM] ⇒ e * 4 = d ⇒ 4 * 4 = 16 ⇒ d = 16 [OSM] ⇒ d * 6 = c ⇒ 3 * 6 = 18 ⇒ c = 18 [SEDM] ⇒ c * 2 = b ⇒ 4 * 2 = 8 ⇒ b = 8 [TRI] ⇒ b * 3 = a ⇒ b * 3 = 9 ⇒ !!a = 9 [PET]
Chyba je nasledovna pismeno „a“ ma v tvojom rieseni dve ciselne hodnoty (9 a 5). Podla tvojho postupu by malo platit:
a = 9 [PET] ⇒ a * 1 = f = 3 * 1 = f ⇒ f = 3 [TRI] ⇒ …
Takze tvoje riesenie nie je jednoznacne a splna ho rovnako aj napr. cislo : 937873.
(Respektive, bude ho splnat kazde cislo, pre ktore plati: pocet pismen pre slovny zapis „a“ = 3)
Mata (autor ulohy)
P1 – losí utkání: komu jsem ukradl body? Já jsem si napsal jen komunikaci plus náhodný výběr čísla, zjistil jsem, že server většinu času nefunguje, tak jsem aspoň občas tu náhodnou strategii spustil, a když se poprvé stalo, že jsem vyhrál, řeklo mi to i rovnou heslo. To jsem se trefil do „tajného slova“ nějakému jinému týmu, kterému jsem zbývající dvě vítězství ukradl? Nebo se za vítězství počítá i když druhý tým nestihl odpovědět včas? Použil jsem jako tajné slovo „jezecek“.
Nejde mi do hlavy, proč můj postup na P2 nefunguje. Nejdřív jsem hranám snížil cenu Floyd-Warshallem, pak je všechny hladově prošel od nejlevnější a zaměstnanců přestěhoval po každé hraně tolik, aby se výchozí nebo cílové místo naplnilo podle plánu. Výsledek je 1280, o 22 peněz dražší. Napadá vás někoho, na čem to může selhat? Adam
Jestli spravne chapu tvuj algoritmus, tak protipriklad je: Mejme ctyri mesta, A-D, 2 zamestnanci (pocatecni stav A1,B1, cilovy stav C1,D1). d(A,C)=d(B,D)=2, d(A,D)=1, d(B,C)=5. Hladovy algoritmus posle jednoho z A do D a dostane reseni s cenou 6 – optimum je ovsem 4. Majk
Díky za hru! Od 20:30 se s námi můžete potkat u Dřeváka (http://www.udrevaka.cz/).
Díky za pěknou hru! NnqJirka
V L9 pozor na AdBlocker. Po jeho vypnuti se nam konecne zobrazila cisla. Predtim jsme nevedeli, co s tim delat.
V L9 / znaci celociselne delenie?
Ano, je to tak