Već neko vreme imam određen broj tekstova koji čekaju da budu napisani, ali se zbog raznih obaveza to nikako nije dešavalo. Došlo je vreme za promene…
Sada je sredina oktobra, što će onima sa jakom moći zapažanja reći da je početak septembra bio dosta davno (na stranu to što je vreme relativno, ignorišući za sada otkriće čestica bržih od svetlosti). A tog davnog trećeg septembra 2011. godine održano je finale četvrtog Bubble Cup takmičenja.
Još u martu sam pisao o ovom događaju u organizaciji srpskog Microsoft razvojnog centra, ali u pitanju je bila samo najava, pošto u tom trenutku ni kvalifikacije nisu bile u toku. Zato je najbolje o celom takmičenju, koje je trajalo od aprila do septembra, pisati hronološki.
Kvalifikacije
Prvog aprila tačno u ponoć, kao što je i najavljeno, započeta je prva runda takmičenja. U skladu sa samim početkom nadmetanja, za ovu rundu su odabrani nešto lakši zadaci, vrednosti od po jedan bod, pa je tako čak dvadeset timova rešilo svih deset problema, dok je četrdeset timova imalo pet ili više urađenih zadataka. Bar jedan zadatak je rešio 71 tim, a tu su se našle prvenstveno ekipe iz Srbije, ali i odlične ekipe iz Hrvatske, BiH, Rumunije i Bugarske.
Iako posle prve runde nije bilo ni približno jasno ko bi mogao proći u finale, druga runda se pobrinula da se to pitanje reši. Naravno, odabrani su teži zadaci, od kojih je svaki nosio dva boda, što je dovelo do toga da nijedan tim ne reši svih deset — dva tima su imala po devet zadataka, a samo 15 timova pet ili više zadataka. Na kraju druge runde je sve bilo jasno, i u finale su pozvani svi timovi koji su imali 18 ili više bodova — devetnaest timova sve ukupno.
Finale
Po planu i programu, test runda je održana u petak uveče (2. septembra), pa su svi imali priliku da se upoznaju sa radnim okruženjem, odnosno da se podsete ukoliko su već učestvovali. Vredi primetiti da velikom broju takmičara ovo nije prvo učešće, što pokazuje da se rado vraćaju Bubble Cupu (a i sa razlogom to čine). Sâmo takmičenje je održano u subotu prepodne, nakon zvaničnog otvaranja, držanja govora (uglavnom na engleskom, zbog internacionalnog karaktera) i omanje zakuske.
Od 19 timova koliko je pozvano u finale, jedan je bio van konkurencije (Gastarbubblers), ali su odlučili da ipak učestvuju i pokušaju da za pet sati reše što više zadataka od osam ponuđenih. Pripremljeno je devet zadataka, ali je odlučeno da se jedan izbaci kao pretežak, što se pokazalo kao dobra odluka, pošto je prvoplasirani tim finale završio sa 7 zadataka. Pritom je izbačeni zadatak zapravo varijacija jednog od prisutnih zadataka, pa nije pričinjena velika “šteta”.
Iz rezultata se može videti da su težine zadataka bile krajnje adekvatne — niko nije uradio sve zadatke, ali su svi uradili bar tri zadatka. Detaljima se neću baviti, ali jedan zadatak moram da pomenem, pošto je veoma zanimljiv, posebno zato što se pojavio na takmičenju gde se očekuju i vremenska i memorijska efikasnost algoritama. Naime, u pitanju je zadatak u kome se traži broj prirodnih brojeva iz zadatog intervala koji zadovoljavaju određene uslove. Te uslove je veoma lako proveriti, ali najveći interval može pokrivati vrednosti od 1 pa sve do 1018, što momentalno isključuje bruteforce rešenje. Međutim, ograničenja su ipak pažljivo birana — ukoliko bi neko generisao na svom računaru sve tražene brojeve, primetio bi da ih ima samo 4343 i shvatio bi da se niz tih brojeva bez problema može ubaciti direktno u kôd. Datoteka bi u tom slučaju imala oko 60kB, dok je dozvoljena veličina 64kB. Bilo je potrebno samo da se krene na vreme sa generisanjem brojeva, pošto je ovaj proces dosta spor, ali posle toga je sve mačji kašalj. Svaka pohvala za onoga ko je osmislio ovaj zadatak i ko je čak i u zvaničnom rešenju obradio ovaj pristup. Nije sve u algoritmima, nešto je i u snalažljivosti.
The emphasis was on stimulating students’ creativity — some of the problems were not so standard for programming competitions.
Dodela nagrada
Nakon finala i ručka, organizovan je obilazak Beograda u otvorenom autobusu (nebo se u pravom trenutku razvedrilo) koji sam ja po ko zna koji put propustio. Posle kratke pauze usledio je obilazak Microsoft razvojnog centra i priča o njegovom napretku (osnovan 2005. godine sa šačicom programera, trenutno zaposleno oko 80 ljudi) i timovima koji postoje (Office, SQL i Bing) — takođe ustaljena tradicija i fina ideja, jer ljudi koji će vrlo verovatno biti neki od najboljih programera u regionu mogu da vide u kakvim uslovima se radi, kao i na čemu se radi u jednom malom razvojnom centru velike firme.
Dodela nagrada je takođe bila tradicionalna — piće i hrana za sve, torta da se proslavi četvrti rođendan, dodela sertifikata, kao i glavnih nagrada za tri najbolja tima. Treće mesto je osvojio tim ex1t iz Bugarske, čiji su članovi Alexander Georgiev, George Acev i Preslav Le. Oni su kao i drugoplasirani tim uradili šest zadataka, ali im je na osnovu vremena potrebnog za rešavanje zadataka (odnosno penalty-ja) izmaklo drugo mesto. Ono je otišlo timu wehmuma, takođe iz Bugarske, u čijem sastavu su bili Rumen Hristov, Georgi Georgiev i Alex Ivanov. Prvo mesto je ubedljivo osvojio Hrvatski tim Suit Up! — Gustav Matula, Ivan Katanić i Ivica Kičić — sa sedam urađenih zadataka, pa su za razliku od prošle godine, kada su bili drugi, ovaj put slavili osvajanje Bubble Cupa. Nagradu za najbolji srednjoškolski tim je odneo novosadski tim Gari (bio je red da neka nagrada ostane u Srbiji) koji su činili Demjan Grubić, Boris Grubić i Mario Cekić.
Osim normalnih nagrada, “scientific committee” je odlučio da dodeli još tri specijalne nagrade:
- Award: Silver lightning
Team wehmuma — for the first accepted solution to a problem - Award: system(“pause”);
Team Gastartbubblers — for lifetime achievement in programming excellence and spreading the BubbleCup spirit (prvi tim koji je poslao rešenje sa system(“pause”);) - Award: Hardcoding Expert
Team v.haralampiev — for being the first to solve LR Primes despite a lack of manpower (jednočlani tim i gore pomenuti zadatak sa prekalkulisanjem)
Ne treba previše filozofirati o opštim utiscima nakon takmičenja. Možda nije u pitanju veliki događaj, ali je svakako organizovan kao jedan. Topla preporuka.
Bilten i fotografije
Ove godine je nastavljena praksa (započeta prošle) da se takmičarima odmah nakon takmičenja obezbedi bilten sa svim zadacima, kako sa kvalifikacija, tako i sa sâmog finala — naravno, sa detaljnim rešenjima. Rešenja zadataka sa kvalifikacija su uglavnom pisali takmičari, dok su za zadatke sa finala bili zaduženi organizatori. S obzirom da je zapravo u pitanju omanja zbirka algoritamskih problema, verujem da bi ovaj bilten svima mogao biti zanimljiv.
Link za download ovogodišnjeg biltena se može naći na http://msacademic.rs/News.aspx?id=547, dok se prošlogodišnji nalazi na sledećoj adresi: http://bubblecup.org/2010/bubbleBook.pdf
Takmičenje će sigurno biti organizovano i sledeće godine, pa nije na odmet početi sa pripremama za isto. Ipak, ostalo je još samo šest meseci… A dotle, tu su fotografije sa finala: http://bit.ly/BCv4-Finals-Pictures. (I snimak.)