Kai trims programuotojams duoda vieną kompiuterį (įspūdžiai iš ACM ICPC pasaulio finalo)

2014 metų birželio mėnesį komanda iš KTU dalyvavo ACM ICPC (International Collegiate Programming Contest) pasaulio finale. Štai įspūdžiai iš pirmų lūpų…

Pradžia

Kadangi registracija į finalą prasidėjo sekmadienį popiet, tai teko iš Lietuvos išvykti dar šeštadienio naktį. Skridom lėktuvu per Maskvą. Skridom ne vieninteliai, nes dar bent kelias komandas teko atpažinti oro uoste ir lėktuve. Visgi tikrų programuotojų komandą iš toli galima atpažinti 🙂

Atskridus į Jekaterinburgą iškart autobusas nuvežė į viešbučius. Viešbučiams nepagailėta pinigų – keturios žvaigždutės ir su tuo susiję patogumai.

Neilgai pailsėję viešbutyje vykome į komandų registraciją. Registracija šiek tiek užtruko, nes buvo 122 komandos, o ir registruojantis reikia atlikti nemažai žingsnių – pateikti dokumentus, susirinkti smulkias dovanėles, nusifotografuoti su komandos marškinėliais ir kt.

Komandos nuotrauka

Komandos nuotrauka

Šių metų talismanas – sabalas Urfoo:

2014 metų talismanas – sabalas Urfoo

2014 metų talismanas – sabalas Urfoo

Be kitų smulkmenų dar gavome ir kauliuką pagalbininką, kai nesiseka surasti bug’o:

Programuotojo kauliukas

Programuotojo kauliukas

Programuotojo kauliukas

Programuotojo kauliukas

Programuotojo kauliukas

Programuotojo kauliukas

Matyt ne vien mes visos kelionės metu beveik nemiegojom, nes tai vienur, tai kitur galėjai pamatyti tokį vaizdą:

Bemiegė kelionė

Bemiegė kelionė

Bemiegė kelionė

Kembridžo komandos treneris

Pastarasis tarp kitko yra latvis, treniruojantis Kembridžo komandą.

Po registracijos laukė vakarienė, vėliau grįžome į viešbučius. Maitinimas itin puikus – pusryčiams, pietums ir vakarienei švediškas stalas.

Pirmadienį vyko IBM TechTrek. Atstovai iš IBM pasakojo apie Cognitive computing ir jų kurtą protingą kompiuterį Watson, kuris sugebėjo žaidime Jeopardy nugalėti du daugkartinius šio žaidimo laimėtojus, kurie buvo žmogiškos kilmės. Taip pat pasakojo ir apie galimus jo panaudojimus, ypač patiko robotinė ranka Eli.

IBM TechTrek

IBM TechTrek

Po pietų vyko atidarymas. Ceremonija šiek tiek užsitęsė, nes tai vienas pašneka, tada pakviečia ką kitą, tas vėl pašnekėjęs pakviečią trečią. Daugybė žmonių šnekėjo, be to, dar ir apdovanojimus vienas kitam dalino.

Po atidarymo vakarienė ir įvairūs užsiėmimai. Buvo galima nueiti į IBM Chillzone, kur galėjai pasišnekėti su darbuotojais iš pačio IBM ar šiaip paskanauti įvairiais užkandžiais.

IBM Chilzone

IBM Chilzone

Iškilus kokiam klausimui pagalbos galėjai kreiptis į savanorius, kurie būtent paskirti pagelbėti. Jų buvo vos ne ant kiekvieno kampo. Tiesa, su kai kuriais teko šiek tiek pavargti kalbantis angliškai, bet su visais, kuriais šnekėjome – susišnekėjome.

Finalas (repeticija)

Antradienį jau buvo šiek tiek rimčiau – dalyvavom Dress rehearsal. Kol laukėm repeticijos pradžios, teko nusifotografuoti su Bill Poucher, ACM ICPC vykdomuoju direktoriumi, bei su nugalėtojų taure. Turbūt nesu sutikęs linksmesnio ir draugiškesnio žmogaus už Bill’ą. Netgi teko dar šiek tiek pabendrauti su juo lėktuve pakeliui namo.

Nuotrauka su taure

Nuotrauka su taure

Per repeticiją buvo lygtais 6 skirtingi uždaviniai, bet kiekvienas iš jų po du kartus – iš viso 12 uždavinių. Dubliavimasis skirtas tam, kad būtų gaunama maksimali apkrova sistemai. Surinkti buvo lengvesni uždaviniai iš senesnių metų finalų. Per 2,5 valandos pavyko išspręsti 3 (o gal 4, neprisimenu). Savijauta prieš pagrindinį pasirodymą buvo gera, nors ir nepavyko išvengti kelių žioplų klaidų.

Tą pačią dieną papietavus dar buvo galimybė vienai valandai pasipratinti su kompiuteriu ir pačia sistema. Šia galimybe irgi pasinaudojome.

Varžybų vieta

Varžybų vieta

Finalas (jau iš tikro)

Trečiadienis – finalas. Visi susirinkome į tą pačią vietą kur vyko treniruotė – Jekaterinburgo krepšinio arenoje. Taisyklės griežtos: negalima įsinešti nieko elektroninio, o geriausia kad iš vis nieko neįsineštum – tik marškinėliai, kelnės ir batai. Viską, ką norėjai turėti sprendimo metu, turėjai pateikti dar tik registruojantis. Visi tie daiktai buvo padėti maišelyje ant stalo dar treniruotės metu + kitos papildomos priemonės: pieštukai, tušinukai, blonknotai baltų lapų bei su langeliais, kalkuliatorius, kompiuteris. Viską, ko neišnešei po treniruotės, galėjai rasti per finalą.

ką randi ant stalo

ką randi ant stalo

Finalo pradžia. Atsiplėšėm voką ir išsidalinom jame buvusias užduotis. Visi pasidalinom ką skaityti: aš skaičiau nuo pradžių, Evaldas nuo vidurio, Karolis nuo galo. Kol kas tik permetėm uždavinius akimis, nesiruošdami spręsti rimčiau, prasitardami kitiems, kai galimai rasdavome sprendžiamą uždavinį.

Iš pradžių priešininkai nusiuntė kelis nesėkmingus submit’us. Kiek vėliau sekė pirmas AC (accepted). Būtent pirmieji sėkmingi bandymai papildomai apdovanojami – komanda, pati pirmoji išsprendusi uždavinį, gauna $1500. Tie kurie patys pirmieji išsprendė uždavinį, kurio niekas kitas neišsprendė, gauna $1000 prizą. Buvo viena komanda, kuri per visą laiką išsprendė tik vieną uždavinį, bet jį išsprendė pati pirmoji – vieta lentelėje nekokia, bet užtat $1000 kišenėje.

Pirmasis priešininkų AC ir pagaliau rimtai kimbame į darbą – žinome, kad šitas uždavinys yra sprendžiamas ir kad ties juo reikėtų susikoncentruoti. Beveik visą finalą taip ir vaikėmės kitus – sprendimo statistikoje pasižiūrėdavom, kurie uždaviniai labiausiai sprendžiami, ir ties jais susikoncentruodavome.

ACM ICPC logo

ACM ICPC logo

Gali kilti klausimas, ką reiškia ACM ICPC logotipas. Debesėlis – tai mąstymo procesas, lemputė – kilusi idėja, o balionas? Balionas – tai AC. Kiekvienam uždaviniui yra po skirtingos spalvos balioną. Išsprendęs uždavinį (gavęs AC) gauni atitinkamos spalvos balioną. Komanda, pirmoji išsprendusi tam tikrą uždavinį, gaudavo priedo pagražintą tos spalvos balioną. Tokia sistema leidžia sekti aplinkiniu situaciją – žvilgteli ir matai, kad pas vienus balionų nėra, o pas kitus jau visi 5.

Pirmiausia išsprendėm uždavinį K. Surveilance. Pavyko implementuoti dinaminį algoritmą. Po to sėdome rašyti C. Crane balancing. Pastarasis buvo nesunkus, tiesiog reikėjo žinoti formulę poligono svorio centrui skaičiuoti. Pačios efektyviausios formulės nežinojom, todėl su šiuo uždaviniu suvargome. Dar nepabaigus spręsti C sėdome spręsti D. Game strategy.
Būtent jis ir gavo antrąjį mūsų AC. Grįžome ir sutelkėme jėgas ties C. Laimingo atsitiktinumo dėka radome testą, su kuriuo programa vietoj realaus skaičiaus pradėjo spausdinti NaN – kažkur yra dalybą iš nulio. Šiek tiek pakeitę algoritmą likus vienai valandai iki finalo pabaigos, turėjome 3 AC.

Praėjus 4 valandoms rezultatų lentelė užšaldoma. Nematai, ką priešininkams pavyko išspręsti, matai tik jų bandymus. Taip išlaikoma intriga iki pat rezultatų paskelbimo.

Taigi, turim dar valandą iki varžybų pabaigos. Pasiėmėm spręsti E. Maze reduction ir L. Wire crossing. Deja, pirmajam nepavyko sugalvoti veikiančios idėjos, o antrasis turėjo itin sudėtingą implementaciją. Likome su trim išspręstais uždaviniais.

Prieš varžybas mūsų tikslas buvo išspręsti daugiau uždavinių nei pernai. Kadangi 3 > 2, tai tikslas buvo įvykdytas. Be to, turint omeny, kad šių metų finalo uždaviniai buvo vieni sudėtingiausių istorijoje, net ir 3 AC leido pasiekti 30 vietą.

Tą pačią dieną vyko uždarymo ceremonija. Vėl visus nugalėtojus apdovanoja, sveikina, fotografuoja. Buvo apdovanojami išsprendę uždavinius pirmieji, pasiekę aukščiausią vietą iš savo regiono bei pirmos 12 komandų (4 aukso medaliai, 4 sidabro ir 4 bronzos). Nugalėtojai priedo prie medalių gavo ir taurę.

Visi medalininkai tiesiai į rankas gavo ir voką su pakvietimu dirbti IBM.

Nugalėtojų paskelbime taip pat atsirado šiek tiek intrigos, nors atrodė nugalėtojas jau aiškus. Maskvos komandą per pirmas 4 valandas sugebėjo išspręsti 6 uždavinius ir iš prieš pat galą išgirstų jų džiaugsmo šūksnių buvo aišku, kad pavyko išspręsti ir septintą. Matyt visi tikėjosi, kad jie ir taps nugalėtojais (taip manė ir patys maskviečiai – galėjai suprasti iš jų veidų atsiimant antros vietos apdovanojimus). Deja, Sankt Peterburgo komanda per paskutinę valandą išsprendė 3 uždavinius ir taip pat surinkę 7 AC iškopė į pirmą vietą dėl mažesnio laiko. Jei maskviečiai būtų gavę dviem WA (wrong answer) mažiau ir taip išvengę 40 baudos minučių, būtų likę pirmi. Bet yra kaip yra.

Pakeliui namo

Ketvirtadienis – pusryčiai ir išvykimas. Kadangi mūsų lėktuvas skrido tik penktadienį, šią laisvą dieną skyrėme pasivaikščiojimui po miestą. O penktadienį vėl bemiegė kelionė namo…