Pobednik prvog otvorenog prvenstva Srbije u optimizacijama je Rus Vlad Kljačin, koji je u drugom kolu svih šest zadataka uradio za čistu "desetku". Drugo mesto i titulu šampiona Srbije za 2008. godinu osvojio je Marko Obradović, treći je Zoran Tanasić, a četvrti Milovan Kovačević. Konačnu tabelu, kao i neka od najboljih rešenja drugog kola, možete videti na zvaničnom sajtu Saveza zagonetača Srbije.
9. 12. 2008.
TRIJUMF RUSA KLJAČINA, PEHAR MARKU OBRADOVIĆU
Pobednik prvog otvorenog prvenstva Srbije u optimizacijama je Rus Vlad Kljačin, koji je u drugom kolu svih šest zadataka uradio za čistu "desetku". Drugo mesto i titulu šampiona Srbije za 2008. godinu osvojio je Marko Obradović, treći je Zoran Tanasić, a četvrti Milovan Kovačević. Konačnu tabelu, kao i neka od najboljih rešenja drugog kola, možete videti na zvaničnom sajtu Saveza zagonetača Srbije.
Пријавите се на:
Објављивање коментара (Atom)
37 коментара:
Najpre čestitke pobednicima i osvajačima medalja, ali i svim učesnicima. Sad kada je sve završeno pokušaću da u kratkim crtama iznesem neke svoje utiske.
Prvo, mislim da smo se u vrlo dobrom svetlu predstavili pred čitavim svetom. Da smo jedno ovakvo takmičenje organizovali malo ranije, to bi bio taj tas na vagi koji nam je bio potreban da dobijemo organizaciju svetskog prvenstva.
Imali smo čak 33 učesnika, što smatram velikim uspehom. Koliki je to odziv govori i podatak da ni velemajstor Portugalov na svom nadaleko poznatom Forsmartsu nije uspeo da okupi više ljudi od nas.
Kada sam skupio sve zadatke, napravio sam selekciju za prvo kolo, plašeći se pomalo da bi neki zadaci iz drugog kola mogli odbiti takmičare. Mnogi učesnici su uz rešenja prvog kola dodali i "sjajni zadaci" ili "hvala na divnom takmičenju".
Zadaci su vam se očito dopali, što pokazuju i ove ankete. Imali smo još dosta ideja, na primer da se postavi ceo špil od 52 karte u kvadrate koji su činili brojku 2008, ali se od toga odustalo zbog malo komplikovanijeg slanja rešenja. Možda je baš tako nešto i nedostajalo u ovom drugom kolu, a žao mi je i što nismo imali ideju za neki geometrijski optimajzer.
Nadam se da će ovo takmičenje biti tradicija, ali bih voleo kada bi se i drugi uključili u sastavljanje ovakvih zagonetki. Siguran sam da imamo sigurno 5-6 ljudi koji bi mogli da "iznesu" ovo takmičenje.
Voleo bih da čujem i mišljenja oko sistema takmičenja. Znam da je bilo naporno, ali upravo zbog toga ostavljen je prostor za "preskakanje" dva zadatka. Može dogodine biti i drugačije, na primer četiri kola po 5 zadataka, ili npr. 8 kola po 2 zadatka, pri čemu bi svako kolo trajalo 3-4 dana itd.
E, a sad da vidim kakve ste sve softvere pravili. Ajde, ajde, znam da ste ih imali :))
Pre svega, moram reći da je Nikolina ideja da organizuje jedno ovakvo takmičenje na blogu sjajna. Ne znam da li za blog postoje statistike posećenosti, ali verujem da je ona u proteklih dve nedelje bila značajno veća. Poruka o startu otvorenog prvenstva Srbije u optimizacionim logičkim problemima je imala najviše komentara do sada (35). Sada, kada je takmičenje završeno, očekujem da će i ovaj rekord biti oboren :)
Žao mi je što Nikoli nisam pružio priliku da se i on takmiči. Kako mi je ovo prvi put da sastavljam zadatke za jedno ovakvo takmičenje, morao sam se s njim konsultovati oko zadataka. Tako je tek njegova modifikacija problema kraljev slalom zadatak učinila kvalitetnim.
Izuzetno sam zadovoljan i odzivom rešavača i kvalitetom pristiglih rešenja. Analiza će još biti. O zadacima, rešenjima, programima kasnije...
Na nemačkom forumu možete pogledati zanimljivu diskusiju o ovom našem takmičenju u koju se povremeno uključuju i Holanđanin Bearda, Estonac Raude i još poneko od stranaca. Možda još zanimljivija diskusija vodi se o strategiji rešavanja nekih naših zadataka. Vidim da su dosta preokupirani matematičkim problemima. Link je:
http://translate.google.com/translate?hl=en&sl=de&u=http://www.logic-masters.de/&sa=X&oi=translate&resnum=3&ct=result&prev=/search%3Fq%3Dlogic%2Bmasters%26hl%3Den
Odaberite opciju forum i tamo ćete naći diskusiju koja se vodi u dva topika.
Nikola, molim te da ponovo daš link za nemački forum, pošto je u prethodnom komentaru ostao nepotpun
Stranica se otvori, ali forum ne može direktno. Klikni levo na forum i tamo ćeš naći.
Čestitke pobjedniku, čestitke Marku, a onda redom ostalim učesnicima.
Posebna pohvala organizatoru.
Žao mi je što nisam imao vremena da se oprobam i u rješavanju zadataka drugog kola. Ipak, nadam se da je moj doprinos bio doboljan da ovo takmičenje bude što bolje. Slavko
Cestitke svima i od mene i slobodno mogu da kazem da sam ponosan na rad naseg saveza i nasih clanova. Ovo prvenstvo, iako prvo, po kvalitetu zadataka, organizaciji, odzivu takmicara, i svemu ostalom sto ga je pratilo je apsolutno u rangu takmicenja na sajtovima Diogena,Turkzeke ili Forsmartsa. Mogu da kazem u ime svih clanova da cemo se potruditi da postane tradicionalno.
Uh, moram da konstatujem da je za mene pomalo bilo i malerozno. Evo moj komentar pisem po drugi put (prvi mi nije prihvacen!), a isto tako sam i neke zadatke radio dvaput, jer sam pogresno tumacio zahtev zadatka, jedan zadatak mi nije priznat jer sam ga pogresno nacrtao. Sve ovo je dalo bar za mene, dodatni sarm ovom takmicenju. Zahvaljujem svima na ucescu sa zeljom da sledeci put bude 99 takmicara iz 39 zemalja.
zorant.
p.s. a ovi sto koriste programe, dobice viruse : - )))
bravo, marko, cestitke i od mene... naravno, cestitke i ostalim ucesnicima, posebno osvajacima medalja, zoranu i milovanu.
a pooooosebne cestitke organizatorima/sastavljacima, nikoli i (opet) milovanu. ne samo da su zadaci sjajni, nego je i sve oko pregledanja zadataka i objavljivanja rezultata (kao i nacin na koji je to ucinjeno) zaista odlicno odradjeno. divno je sto je bilo toliko ucesnika iz inostranstva, a raduje i podatak da se o ovome prica i na nemackom forumu. tesko organizatoru sledeceg takmicenja, postavljeni su mu visoki standardi :)
sledece prvenstvo... jeste da do njega ima godinu dana, al' mozda nije rano poceti pricu o tome. slazem se da vise ljudi treba da se ukljuci u sastavljanje zadataka. ja sam vec poceo da razmisljam i da belezim neke ideje :). ne znam samo da li je tehnicki izvodljivo da svako bude autor maksimalno tri zadatka, pa da svi mogu da se takmice. ipak mislim da neko mora propustiti natjecanje, da bi mogao da prikupi zadatke, spremi fajlove, odgovara na pitanja...
sto se tice samog sistema takmicenja, priznajem da mi nije bas 'leglo' dvonedeljno mudrovanje, ali ne bih ga bas ni razvlacio na mesec dana. mozda bi moglo isto ovako, dvaput po nedelju dana, sa jednom nedeljom pauze? nikola, stavi na blog anketu, pa da izglasamo format takmicenja.
da ne gnjavim vise... samo nek' ga bude i sledece godine... i da na'vatamo i stotog ucesnika :)
O programima...
Ukratko, sa minimumom matematike. Ako ima zainteresovanih možemo ići u detalje.
Kod optimajzera u većini slučajeva niste sigurni da ste došli do optimalnog rešenja. Kako i kod mene postoji izvesna doza nestrpljenja, želja mi je bila da odgovore obradimo što pre, da tabela sa rezultatima kao i najbolja rešenja budu objavljena što je moguće pre. Zato sam napravio programe koji prihvataju odgovore u zadatom formatu i vrše sve moguće logičke kontrole prema uslovima zadatka (za 4 koja sam dao) i proveravaju deklarisani rezultat. Bez toga, pregledati pentomino loop i kuglice bi bio mukotrpan posao. Kako se Nikola snašao s njegovim, ne znam ;) ali je uspeo.
Programe koji pomažu pri rešavanju delim na asistente i tragače. Asistenti računaju, boduju, proveravaju vaše rešenje i omogućuju vašu laku manipulaciju rasporedom, pozicijom i sl. Za asistenta je često dovoljan i Excel. Ali, oni ne nude rešenja. To rade tragači. Tu se već mora programirati.
Kod traganja za rešenjima, postoje neke 3 metode.
1. gruba sila – proći sve moguće varijante
Uglavnom neprimenljiva zbog prevelikog broja kombinacija. Treba imati na umu da za današnje PC računare npr. 10! (deset faktorijel) ne predstavlja problem – potrebno vreme da se ispišu sve permutacije od 1234567890 do 9876543210 meri se minutama. Gotovo svi zadaci sa ovog takmičenja ovom metodom ne mogu da se reše za života programera.
2. backtrack metoda.
Ideja je jednostavna – ako parcijalno rešenje nije korektno, onda ni konačno rešenje koje ga uključuje neće biti korektno (Ako anakonda na 50. mestu dodiruje sivo polje, ne vredi ići dalje tim putem, mora se vratiti nazad).
Najjednostavniji primer je prolaz kroz lavirint koji nema kružnih putanja. Idete dok ne dodjete do slepe ulice, onda se vratite do prve raskrsnice i krenete drugim putem. Ako se na raskrsnici uvek ponašate na isti način (npr. prvo probate levo, pa pravo i na kraju desno), sigurno nalazite izlaz.
Metoda postaje upotrebljiva tek ako se nadje dovoljno dobar kriterijum za rano odbacivanje neperspektivnih varijanti – putanja, rasporeda figura itd.
3. iterativno popravljanje rešenja (metoda pozajmljena iz numeričke matematike)
Kreće se od nekog rešenja koje se kontrolisanim ili slučajnim izborom menja. Ako se dodje do boljeg rešenja nastavlja se s njim, ako ne – odbacuje se. Mana ovog metoda je što vas vodi u lokalni minimum/maksimum koji može biti daleko od pravog.
Programe koji bi rešili zadatke primenom ovih metoda nije jednostavno napisati, delom što je (bar se nadam) dobar deo zadataka originalan. Potrebno je dosta vremena da se istestira i proveri da li programi rade korektno. A potrebno vreme za nalaženje rešenja opet može biti neprihvatljivo dugo. Zato će analiza postavljenih problema potrajati...
Izrada kompjuterskih programa za ovakva takmičenja nije ništa nedozvoljeno. Štaviše, to postaje normalno. Dobar programer često će naći način kako da savlada neki zadatak, ali ne uvek. Lepota optimajzera je upravo u tome da nikada niste sigurni da je vaše rešenje najbolje i onda jednostavno dođete do neke granice kada se zadovoljite nađenim rešenjem. U pregledanju rešenja drugog kola imao sam Nenadovu svesrdnu pomoć, koji je napravio lepe programčiće za proveru tačnosti unetog rešenja. Kako su rešenja pristizala, tako sam i ja sukcesivno pregledavao zadatke i već negde oko dva ujutro (posle američkog fudbala) imao sam kompletnu tabelu. Kasnije je bilo samo manjih korekcija.
Priznajem da su najslabiji zadaci bili zmija i drugi matematički zadatak, jer su svi koji su ispravno uradili dobili poene. Isto bi bilo i sa pentominom u krug, da nije nađena ona briljantna 74. Ali da nije bilo ovakvih zadataka, bar desetak učesnika ne bi uopšte osvajalo poene.
Po meni, najbolji zadaci su oni u kojima je samo jedan učesnik dobio desetku. U prvom kolu to su ukrštenica i kockice, u drugom xo, pentomino brodovi, sudoku palindrom i kuglice. Čak četiri solo desetke dobio je Rus, po jednu Milovan i Marko. U ovim zadacima bilo je stvarno fenomenalnih rešenja. Eto, niko se nije dosetio ideje koju možemo videti na xo. Kasnije Milovan uz malo korekcije napravi i 176! Ali trebalo se dosetiti. Palindrom je isto izuzetno rešenje - sad da vidimo da li možemo da ubacimo unutra neku rečenicu :))
Što se tiče sistema takmičenja za sledeću godinu, biće dobro ako se on iz godine u godinu bude menjao, a sistem se ne može odabrati baš u jednoj anketi. Priznajem da sam odluku ovom sistemu takmičenja doneo sam i to najviše zbog toga da bi omogućio i Milovanu da se takmiči.
Ako bude više zainteresovanih za sastavljanje, možda se za iduću godinu može razmisliti o varijanti da bude sedam kola i recimo po 3 zadatka. Svako kolo imalo bi drugog autora. Svaki učesnik imao bi pravo da preskače jedno kolo ili mu se najslabiji rezultat ne bi računao, a autor zadataka bi preskakao svoje. Tako bi možda mogli dati poverenje i nekom strancu da uradi zadatke za jedno kolo. Svako kolo moglo bi da traje recimo u periodu sreda-nedelja. Možda bi se oteglo, ali može se razmišljati.
Uh bas mi se svidja ova ideja sa sedam nedelja i da svi ucestvuju. pa nista lepse nego kad pobedis i autore zadataka
optimist
Možda bi trebalo otvoriti novi post za svaki zadatak, pa tamo komentarisati. Veoma sam zainteresovan za vaše komentare i razmenu ideja. No, da krenem...
#1 ZGODNA MATEMATIKA
Rešavanje: Nije bilo teško. Veliki brojevi treba da množe što više drugih brojeva, unutar višecifrenih brojeva veće cifre idu prve itd.
Asistent: Excel. Svaka cifra u posebnu kolonu, medjurezultati daleko desno, a uz cifre krajnji rezultat. Laka izmena cifara (nisam se trudio oko makroa)
i trenutan rezultat.
Tragač:
Metod 1 (gruba sila) - neprimenljiv.
Metod 2 (backtrack) - neupotrebljiv, ne znam šta bi bio kriterijum za odbacivanje nakon upisivanja prvih x cifara.
Metod 3 - upotrebljiv i jednostavan za realizaciju. Krećemo od slučajnog rasporeda 18 cifara (po dve od svake, u skladu s postavkom zadatka) i nalazimo rezultat. Idemo redom po svim parovima cifara (prva-druga, prva-treća,..., 17.-18.), menjamo im mesta i nalazimo reziltat. Ako je veći od do tada dostignutog idemo dalje, a ako ne, vraćamo cifre u prethodni položaj. I tako sve dok ima napretka. Ovo nas vodi u neki od lokalnih minimuma tj. kada zamena dve cifre ne donosi poboljšanje, a još nismo stigli do pravog maksimuma. U tom trenutku treba zakoračiti daleko nazad, na slučajan način uzeti novi polazni niz i ponovo krenuti sa poboljšanjem. Uz malo sreće, za sat-dva, dolazite u pravi maksimum. Moguće je ugraditi još malo pameti, npr. gledati trojke cifara i sl.
Ovde je Milovan video moju prvobitnu ideju koja je izgledala ovako
_ _ _ x _ _ x _ _ x _ x _ x _
Ovde je trebalo uneti svaku cifru od 0 do 9 jednom. I brzo se našlo najbolje rešenje 610x52x43x9x8x7 iako i druge kombinacije npr. 9x7x5 daju vrlo približni rezultat. I onda sam izbacio nulu, duplirao brojeve, postavio zagrade i - ispostavilo se da je više ljudi sa osmicom nego sa desetkom, a između ta dva rezultata ima još nekoliko koje, zanimljivo, niko nije prijavio.
#2 ANAKONDA
Rešavanje: Prilično teško. Ideja je bila da svako 10. polje s obe strane tj. označena polja (kod mene *) moraju biti jedno uz drugo, da bi ostavili što veći manevarski prostor. Da bi mogao posmatrati sve samo s jednog kraja, a biti siguran da će sve biti ok, postoje 2 varijante: zvezdice idu na 1,10,11,20 tj. šema 1-10 ili na 9,10,19,20 tj. šema 9-10 s tim da zmija mora da se na kraju nastavi sa još 8 polja da bi sve leglo kako treba. Ovaj pristup mi je uštedeo jako puno vremena, tako da sam stigao da proigram više perspektivnih polaznih tačaka i varijanti.
Asistent: Excel, Word, ali samo za crtanje. I to je pomoć, jer kod ovog zadatka i kvalitetna gumica brzo posustaje. O rešavaču da i ne govorimo :)
Tragač:
Metod 1 (gruba sila) - neprimenljiv.
Metod 2 (backtrack) - upotrebljiv, ali opet traži jako puno vremena. I za programiranje i za rad programa. Kod programiranja najlakše je koristiti tehniku rekurzije, mada ona donosi dodatno usporenje. Za ubrzanje programa mora se tražiti dobar kriterijum za kresanje stabla kombinacija. I pored dosta sivih polja koja ograničavaju putanju, postoji mnoštvo prolaza koji donose more kombinacija. Probao sam razne ideje. Najbolje se pokazalo sledeće: kod svakog koraka analizirati preostala dostupna ("dohvatljiva") slobodna polja. Ako ih je premalo (npr. ako zmija ostavi jedan ugao nepopunjen) ne vredi se dalje truditi. No, i uz ovo, program nije nalazio rešenje dok mu nisam zadao polaz otkriven rešavanjem. Ono što sam dodatno pokušao je da tražim putanju gde je samo s jednog kraja markirano svako 10. polje. Čak ni takvu zmiju (koja ne zadovoljava uslove) nisam pronašao dužu od 128. Za dokaz da je 128 najbolje što se može treba i još pameti i još vremena...
Metod 3 - neupotrebljiv.
Ja sam ovde nasao max rezultat slicnom metodom koju je primenio Milovan ali nije bio trenutan rezultat vec upravo tako ooko sat i po do dva. Zasto? Odmah se videlo da 9 ide na kraj jer mnozite vec maksimalni broj sa najvecim brojem. Kecevi su opet logicno isli na mesto 1 ili destice u visecifrenim brojevima i brzo sam dosao do zakljucka da oba moraju biti u prvom cetvorocifrenom broju na kraju, jer kad mnozite kecevima nnista ne dobijate. Ali i pored uspesno resenog zadatka za mene je ostala jedna tajna (taj raspored sam ipak srecno pogodio) zasto je zbir dvocifrenih brojeva bi o idealan 73+64 ili 74+63. Sve drugo sto sam probao davalo je "drasticno manji rezultat, cak i enornmo povecanje ovog zbira kao i minimalno povecanje ovog zbira. da li neko ume ovo da obrazlozi na logican nacin.
Smatram da onaj ko nije pogodio ovu kombinaciju nije mogao doci do maksimuma.
zorant.
Sto se tice anakonde, intuicija mi govori da je moguce bolje resenje, '130' sigurno. Nemam vremena da probam ali sam siguran da moje poslato resenje od 128 moze da se popravi jer je ostalo dosta mesta za pomeranje tela zmije. Mislim da nisam dobro spajao "desetke". Inace sam koristio slicnu logiku posebnom bojom sam obelezavao polja koja ne smeju dodirnuti siva i u tom opsegu sam pomerao telo zmije.
Bilo je logino samo traziti 10 ili 8 jer sve druge kombinacije ostavljaju ta markirana polja razmaknuta i vrlo tesko se onda krecete izmedju sivih polja.
zorant
naci cu 130
Ja sam dobio informaciju da je Jelena Đurić našla zmiju od 130 pa je molimo da nam pošalje.
evo još jedan komentar za danas.
#3 OLIMPIJSKA GODINA
Ne volim ovakve zadatke. Osim čistog "nabadanja" ne vidim neki lep način za rešavanje.
Rešavanje: Prilično teško. Jedva sam i ono malo ukrstio :) Sva rešenja, a posebno ono najbolje, mi deluju fantastično.
Tragač:
Metod 3 - krenuti od prazne table, upisati negde reč, pa ukrštati sa upisanim jednu po jednu dokle god može. Onda ispočetka. Kao kod rešavanja, čisto nabadanje i sreća. Program jeste u tome brz, ali nažalost jednako neuspešan.
Da pokušam da odgovorim na:
"zasto je zbir dvocifrenih brojeva bi o idealan 73+64 ili 74+63"
moja logika je da popunjavanje mora ići od solo brojeva, pa tek onda oni u zbirovima i prvo brojevi sa manje cifara. Krećem od 9 i trudim se da se velike cifre medjusobno množe. Ako obeležimo mesta u jednačini ovako:
1,2,3,4 x 5,6,7 x (8,9,10 + 11) x 12,13, x (14,15 + 16,17) x 18
je sledeci:
18. 9, mnozi najvise cifara
12. 9
5. 8
1. 8, mnozi najvise brojeva i sve devetke i postavljenu osmicu
8. 7
16. 7
14. 6 svi postavljeni se madjusobno množe
prva dilema. sledeća šestica može množiti 9,9,8,8 i jednu 7. ima dva mesta, biram ono sa većom težinom
9. 6
1. 8 jer će tu množiti najviše - 76,9,6,7,9
6. 8 tu množi 85,76,9,6,7,9
po istom principu, dalje
15. 4
13. 4
17. 3
10. 3
time smo došli do (64 + 73) uz dozvoljene permutacije koje daju isti zbir.
#4 KRALJEV SLALOM
Inicijalno, nije traženo da se figure ne dodiruju i da su u različitim redovima i kolonama. To je ono što je zadatku nedostajalo, a što je dodao Nikola. Nije jednostavno "provući" kralja kroz sve postavljene uslove.
Ne znam da li je nadjeno rešenje najbolje moguće, ali to ostavljam vama da dalje analizirate :)
#5 KOTRLJANJE KOCKE
Prilično težak problem.
Rešavanje: Levi deo tabele (sredina i gore levo) ima samo jednu dobru varijantu za prolaz sa karakteristicnim manevrom (gornji levi ugao). Taj manevar se moze koristiti i na drugim delovima tabele. Donji red i prvi iznad njega sam koristio da na pravi način udjem u taj prolaz u levom delu tabele. Naravno, Rus je to ucinio na jos bolji nacin.
Tragač:
Metod 2 (backtrack) - Uz primenu rekurzije. Dobar kriterijum za odbacivanje neperspektivnih varijanti je provera da li preostala polja čine jednu celinu. Ako ne, ne mogu se obići sva polja. Drugo, ta celina mora da sadrži gornje desno polje. Treće, ako su npr. preostala samo 3 zelena i 3 crvena polja, maksimalni dodatak na ostvaren medjurezultat je 3x6-3x1 = 15. Ako to nije dovoljno da premašimo rekordni rezultat, ne vredi nastavljati tim putem. Kako pomeramo rekord, ovaj kriterijum sve više dobija na težini.
Potpuni prolazak kroz sve varijante bi potrajao danima. Zavisno od redosleda prioriteta prolaska (desno, levo, gore, dole) program nalazi rešenje koje bi osvojilo nešto bodova za nekih par sati.
ps Ako sam preterao s komentarima recite ;))
#6 PENTOMINSKO KOLO
Pentomina. Večna tema sa neograničenim brojem varijacija. Brzo vam postane jasno šta se traži u pentominskom kolu i gde je problem. Mali broj elemenata, njih dvanaest, stalno vas teraju da nastavite dalje jer znate da je rešenje blizu. Za rezultat preko 70 je trebalo dosta truda. I sam sam stigao samo do 72. Dva data rešenja sa 74 su gotovo identična i zaslužuju sve čestitke.
Programiranje ovoga je prilično veliki zalogaj. Nisam probao.
#7 NEOBIČNE DOMINE
U startu mi je delovao jako komplikovano, pa sam ga ostavio za kraj. Brzo sam video koliko je zadatak u stvari lep. Napravio sam neko rešenje i počeo da uviđam gde je problem i kako popraviti rešenje. Bio sam zadovoljan koliko sam ga popravio, više nije ni bilo vremena - kad ono samo 2 poena :) Mora da je početno rešenje bilo jaaaaako loše ;))
Odličan, zadatak.
Kod sastavljanja domina glavna dilema je bila koliko ostaviti praznih polja za manevar. Prvobitna mreža 8x8 bila je suviše tesna, pa sam je proširio na 8x9, iako sam razmišljao i o nekom nepravilnom obliku. Druga dilema je bila kako bodovati zadatak, pa sam razmišljao o tome da se uz dužinu petlje svako slovo boduje sa 1 poenom, a svaki broj (pošto dolazi kasnije) 2 poena. Od ovoga sam odustao jer se moglo krenuti i unatrag. Imam još jednu dobru ideju sa ovim slovno-brojčanim dominama za neki sledeći put. Mislim da do sada nisam nigde video domine sa kombinacijom broj/slovo.
Sad prelazimo na drugu nedelju. Iks-oks, jedini "autentični" zadatak na kojem sam dosta insistirao prvobitno je bio zamišljen kao brojčana crnilica (link-a-pix), ali da bi se dobro postavio zadatak, trebalo je mnogo, mnogo uslova. Zato sam od toga odustao. Sledeća ideja: pošto mreža ima 222 polja, što je 6x37, zamislio sam da se ubaci po šest kompleta svih 26 slova alfabeta i šest kompleta brojeva od 0 do 9, uz šest praznih polja, sa idejom da se boduju svi kvadrati 2x2 ili pravougaonici 2x3 sa jednakim brojem slova i brojeva. Suviše komplikovano, zar ne. Tako je nastao iks-oks.
Ево да се и ја јавим. Хвала свима на честиткама.
Што се тиче задатака, највише сам поносан на укрштеницу и пентомино, где сам и направио најбоље резултате.
Што се укрштенице, тиче, уопште ми, док сам решавао није пало на памет да могу да имам 2х2 или већи правоугаоник испуњен словима! Моја идеја је била да имам што мање празник 2х2 правоугаоника. Да не бих писао и брисао, прецртавао и одцртавао искоришћене речи, ја сам исекао речи од папира и почео да их ређам. Морало се кренути од нечега, па сам кренуо од најдуже речи у последњем реду и почео да укрштам. Кад ми се учини да нешто није добро, лако је било уклонити с табле последњих пар речи и наставити одатле. Имао сам и један пропуст. Наиме, првобитно сам одштампао мрежу 20х19 уместо 20х20, направио задовољавајућу умкрштеницу и тек кад сам је преписивао видео сам грешку! Па опет све из почетка.
На крају, већ готова укрштеница се лако оптимизује, уочавањем речи које се најмање укрштају и уочавањем могућности да се те речи замене другима ако тако може да се убаци још која.
Марко
Што се тиче пентомина, јасно је одмах било да решење мора што правилније да изгледа споља, па сам задатак решавао као минимизацију спољног обима (има мање да се броји :)
Првобитна идеја је била да то што више личи на правоугаоник (или квадрат) и тако сам добио решење, најпре од 70 па онда и 72) Дуго сам мислио да боље и не може, а проблем који је изгледао нерешив били су фластер (Х) и буџа (F) који су штрчали из правоугаоника.
А онда, тренутак инспирације и идеја да споља не мора да баш буде прави правоугаоник, већ да може да буде правоугаоник коме је из ћошка (или више њих) исечен други правоугаоник. То је такође минимално коришћење спољних ивица, а и површина целе фигуре се смањује јер се не мора "обилазити преко свих ћошкова" Сада је проблем био само уклопити унутрашња пентомина јер се због скученијег простора сада врло лако додирују. Али, као што рече Милован, има их само 12 па се брзо врте комбинације. Шта да кажем, успело је :)
Надам се да нисам био превише конфузан у објашњењима :)
Марко
Још само пар речи о укрштеници. Рекао сам да ми није пало на памет да речи могу да захватају правоугаонике 2х2 и веће. Али, ако се тога сетите, почетак се сам намеће - потребно је наћи скуп(ове) речи који то омогућава(ју). То доноси невероватну уштеду простора и самим тим места за нове речи. То се може најбоље видети на примеру укрштенице естонског загонетача који има изузетне 4х2 и 3х2 правоугаонике. То је оно што прави разлику између његове и моје укрштенице, а у питању је видели сте, чак 14 поена. Кад се будем мало одморио од оптимизирања, покушаћу да, користећи ову идеју пребацим 400.
Марко
Fenomenalno takmičenje! Nikola i Milovane - svaka vam čast! Marko, Zorane, Čedo, sve čestitke!
Sledeće godine ću uzeti godišnji odmor kad ovo opet počne:)
Evo skromnog priloga za iks-oks i abcd kuglice:
http://rapidshare.com/files/172221997/xoxo.zip.html
http://rapidshare.com/files/172223155/abcd.zip.html
#8 IKS-OKS PO SRBIJI
Najteže je bilo prebrojati. Tri puta brojim, tri ipo rezultata :) To se odmah moralo isprogramirati, poput Nenadovog programa.
Onda matematičko/ programerski pristup. Kada se popuni mapa, postoji 5 tipova polja, gde: 1 (problematicno) - ni X ni O ne daju korektno rešenje, 2 (fiksno) - ako se promeni upisano, rešenje postaje nekorektno, 3 (lose X) - X treba promeniti u O da bi bilo korektno, 4 (lose O) - O treba promeniti u X i 5 (slobodno) - u polju moze stajati i X i O. Problematicna polja uvek prate losa X ili losa O i tu se mora korigovati. Idealna situacija nastaje kada je broj losih X jednak broju losih O. Samo ih zamenimo. Tek na kraju treba "trošiti" slobodna polja. Kategorizaciju i markiranje polja obavlja program, a manipulacija je na vama. Ili na programu :) primenom metoda 3. Takvom programu treba 4-5 sati da od slučajno postavljanih po 111 x i o dodje do rešenja oko 140.
Rešenje Kljačina je za tri koplja ispred naših. Koristeći kategorizaciju polja, našao sam da u tom rešenju (od 175) ima dosta slobodnih polja. Ipak, uspeo sam da popravim rezultat samo za 1.
Ja ću probati ovako odjednom da prođem kroz sve preostale zadatke. Sudoku s palindromom je moja omiljena vrsta sudokua. U 9x9 uspeo sam da "uglavim" dobru palindromnu rečenicu od 23 slova. Ideja je ovaj put bila da vidim koliki može biti palindromni niz. Uz pomoć programa sa lakoćom sam uspeo da dođem do rezultata 55, ali ga je bilo teško popraviti. Milovanov rezultat je sjajan, a ima još malo prostora za teoretski maksimum od 73 polja.
Domino je simpatičan zadatak na kojem je nađen teoretski maksimum. Moglo se možda ovde još malo dopuniti pa da se u rezultat računaju i dijagonalni parovi.
Mreža za pentomino brodove izgledala je drugačije u fazi pripreme zadataka. Umesto tripleta, plavim poljima bila su ispisana slova S (serbian), O (optimizing) i C (shampionship) pa je trebalo ostvariti što veći rezultat u plavim poljima, ali sam se pribojavao da bi puno njih našlo maksimum.
Šahovski optimajzer iz drugog kola imao sam spreman i kada je na blogu organizovano takmičenje u problemskom šahu, ali sam ga sačuvao za ovu priliku. Teoretski maksimum je nađen, a interesantno, na mogućnost rokade nisam ni pomislio.
Četiri jednačine je rezervni zadatak, koji je došao umesto perli. Bila bi to još jedna petlja, a već mi je bilo dosta petlji. Mislim da bi zadatak bio kud i kamo bolji da je umesto prve ušla ovakva jednačina
_ _ _ _ x ( _ + _ ) + _ _ _
U ovom slučaju rezultat bi morao da bude minimum 6 hiljada, pa bi otpala mnoga niska rešenja. Zapravo, niko nije imao rezultat 0 sa rešenjem većim od 6 hiljada. Kada sam zamišljao zadatak, pošao sam od nekog većeg rezultata, konkretno 9315, znajući da će biti još ispravnih rešenja.
I na kraju kuglice. Šta reći? I ja sam svoj glas u ovoj drugoj anketi dao kugicama. Nesvakidašnji zadatak bio je prava trešnja na vrhu šlaga. Voleo bih da ima više ovakvih zadatka, bez mreže, bez kvadratića i brojeva. Sjajno, svaka čast Milovane!
Milovane, nadam se da ćemo čuti i ostatak zanimljivih metoda pre nego što poruka ispadne sa glavne stranice.
#9 SUDOKU S PALINDROMOM
Veoma zanimljiv problem. Još se bakćem s njim. Isprobao sam najrazličitije ideje, no i dalje ostaje kao najbolji rezultat 65. Nakon doterivanja, program je pronašao nekoliko ovakvih rešenja.
Jedini metod koji ovde pomaže je backtrack. Evo ideja koje su ugradjene u program:
- Kreće se od centra palindroma, označavamo ga s 1.
- Postoji 9 različizih mesta gde može biti centar (c1, d1, c2,d2, c3,d3, d4, c5, d5). Ostala su ili nemoguća ili simetrična ovima.
- U svako polje upisujem kandidate. Kako se upisuju brojevi u sudoku, tako se skidaju mogući kandidati iz redova, kolona i malih kocki (3x3) - 1. nivo rešavanja sudokua.
- Kad se izabere put i broj za nastavak krakova palindroma, odmah se skidaju mogući kandidati, tj. rešava se sudoku. Koristio sam samo 1. nivo rešavanja sudokua.
- Brojevi na kraku: npr. broj 8 se ne može na kraku pojaviti pre broja 7. U gotovom rešenju je uvek moguće ovo obezbediti prostom zamenom svih brojeva 7 i 8. Naravno, ovo pravilo važi za sve brojeve. Time se broj kombinacija značajno smanjuje. Npr. dovoljno je ispitati varijantu 1-2-3-1-4 a onda ne mora 1-2-3-1-5 ili 1-2-3-1-6.
- Ako je nekom kraku ostalo nedovoljno polja za "širenje", ta varijanta se može napustiti. Pošto nam je poznato rešenje od 65, tražimo da prostor omogući bar 67. Tu postoje dve varijante, kada se krakovi šire u istom polju i kada se šire u dva odvojena polja.
Postoji još jedna mogućnost. Pošto je broj kombinacija enorman, može se pokušati gadjati "najizglednija" varijanta. Npr. kod izbora daljeg puta kraka birati varijantu kojom se skida što manji broj mogućih kandidata, čime se ostavlja što više slobode za nastavak. Svaka uočena osobina parcijalnog ili konačnog rešenja može biti interesantna i vredna za kresanje stablja kombinacija. Ako imate neku ideju, podelite je s nama.
#12 ŠAHOVSKI RASPORED
Volim šahovske probleme. Ograničena tabla, poznato ponašanje figura i bezbroj kombinacija.
U programiranju, ovde pomaže metod 3 - postepeno popravljanje rešenja.
U startu treba postaviti regularnu poziciju prema uslovima zadatka. Pešaci idu prvi i to nije problem. Jedini problem koji se tu javlja su raznobojni lovci. Rešava se zamenom lovca s nekom drugom figurom.
Popravljanje rezultata ide nekom od transformacija (slučajnim izborom):
- zamena dve figure
- pomeranje para figura tako da prva dodje u red druge, a druga u prvobitni red prve figure
- kao prethodno samo što se pomeranje vrši po kolonama
- rotacija pozicija 3 figure
- pomeranje po redovima 3 figure
- pomeranje po kolonama 3 figure
Kod svake transformacije, proverava se regularnost (pešaci, lovci). Sam izbor transformacija obezbedjuje zadržavanje osobine "2 u redu i koloni". Kada se iscrpi mogućnost poboljšanja, sledi nova startna pozicija, pa sve ispočetka.
Program veoma brzo nalazi rešenje oko 90. Uz malo sreće dolazi se do 94, a uz dosta vremena i do 96-98.
Isti princip, samo promena kriterijuma napredovanja, vodi ka rešenju sa minimalnim brojem poteza. Ovde se brže dolazi do rešenja, a stepenice su 20, pa uz sreću 16, a vremenom i 15.
#13 ČETIRI JEDNAČINE
Jedini problem koji se mogao rešiti i primenom grube sile.
Olakšavajuća okolnost je što postoji rešenje gde je razlika nula. Proveriti rezultat za zadati broj sve 4 jednačine za sve permutacije (9!) je stvar minuta. Za manje od sat se može proći kroz sve brojeve od nekih 2400 do 20000, gde zbog tipa jednačina moraju biti rešenja. Od 2500 - 2800 ima na desetine brojeva koji se mogu dobiti u sve 4 jednačine.
Vaši komentari? Ili komentari komentara? ;))
rado bih ja komentarisao, al' se bojim da bi tekst bio prilicno monoton, jer bi se sastojao od nabrajanja stepena grubosti primenjene sile na pojedine zadatke :). jedina svetla tacka bi bilo spominjanje asistenta (excela) pri resavanju oba matematicka zadatka. s tim da sam u prvoj nedelji, nakon tri minuta, matematiku ostavio za kraj ('ovo je lako, asistent ce pomoci da izguram maksimum'), a onda potpuno zaboravio na nju...
tako daaaa... prvo komentar komentara. potpuno mi je jasna nikolina ocena najboljih i 'najslabijih' (pod navodnicima, posto zaista nije bilo slabih) zadataka, jer je data sa stanovista sastavljaca. mi, resavaci, smo na suprotnoj strani i jaaaako volimo kad postoje zadaci na kojima mozemo da uzmemo bodove :). zato nikako ne bih nazvao anakondu slabom. ima tu sta da se mudruje. pored rasporeda 2-8, trebalo je pogledati i 1-6-1-2, paziti na sve te tacke dodira... pa dovoljno je sto jos uvek ne znamo dal' je 130 moguce ili ne.
moj glas u prvoj nedelji za najbolji zadatak je dobila olimpijska godina. kao sto se vidi iz naknadno poslatog najvrednijeg resenja, ipak nije u pitanju puko nabadanje. marko je to vec lepo prokomentarisao, a pritom i spomenuo isecanje reci od papira, jednostavnu ideju koje se nikad, ali nikad ne bih setio (a sve to zajedno me gotovo rasplace kad pomislim kol'ko sam puta drljao gumicom). jos jedan razlog zasto mi se svidja zadatak: nemogucnost programiranja ;). i zato odmah glasam da ovakav zadatak imamo i na sledecem takmicenju. nije ga preterano komplikovano pripremiti, a odlican je.
posle odlicnih pentomina (gde sam bio ubedjen da je 72 maksimum), slaloma i domina (pretpostavljao da moze bolje, al' sam bas bio zadovoljan svojim dostignucima), u prvom delu me je najvise umorilo kotrljanje kockice. pocinjao sam s kraja, s pocetka, iz sredine... svaki put sve vise ocajan, shvatajuci da rezultat necu popraviti, a da je to sigurno moguce.
druga nedelja je druga prica: uz nedostatak vremena, stig'o me je i neki umor, pa se nisam posvetio zadacima koliko sam zeleo. rezultat toga je da sahovski raspored nisam ni pokusao, a za kuglice i brodove sam poslao prvo resenje do kojeg sam dosao. sudoku palindrom sam sve vreme resavao sa pogresnom pretpostavkom, sto me je dovelo samo do 55, ali sam na kraju pogresio pri ukucavanju resenja. x/o - zadatak za izludjivanje! :) kako god popunim imam 111 x i 110 o. u petom brojanju konacno 111 o, ali zato i 112 x. kad konacno ustanovim da je lik od starta ispravno popunjen, tri uzastopna prebrojavanja mi daju za resenje 138, 139 i 140. i tako desetinama puta. a kako je samo jednostavno odradjeno... mnooogo lepo.
sve u svemu, odnos hardvera -olovka, gumica, sveska na kvadratice pocevsi od treceg dana (prvo sam spartao po praznim listovima), drvena kocka s budimpestanskog maratona na kojoj sam napisao brojeve, sinovljeve domine u kojima fali nekoliko tackica na pojedinim komadima i kompletna dupla cetvorka- i softvera -asistent excel- je bio negde 99 spram 1. sto uopste ne znaci da ne uzivam u citanju milovanovih komentara. koristice mi ta prica, jos kako... :)
Šteta za tvoj palindrom, sa tih 5 poena prestigao bi još dva stranca. Izem ti pravila i ko ih izmisli... :o)
Постави коментар