“E pur și simplu dur”

Ce e mai aprig decât o olimpiadă internațională de informatică? Răspunsul se află la Sankt Petersburg, într-un concurs la care trei studenţi de la Universitatea București merg pentru a-și testa vreme de cinci zile talentul de programatori.

Echipa Universității din București care va reprezenta România la Sankt Petersburg. Foto: Vlad Bîrdu.

 

Adrian Budău, Mihai Calancea și Șerban Stan nu mai sunt nişte necunoscuţi printre olimpicii internaţionali. Adrian e medaliat cu aur și cu de argint la Olimpiada Internațională de Informatică din 2011 și 2012, Mihai are un bronz la activ, câștigat la Turneul Internațional de la Shumen, iar Șerban are trei medalii de argint și două de bronz la Olimpiadele Europene. Dar tot acest palmares parcă nu-i la fel de strălucitor precum laurii unei competiţii mult mai acerbe.

 

ACM International Collegiate Programming Contest, ACM ICPC pentru cunoscători, este o competiție ce datează din anii ’70, când a fost organizată undeva prin Texas. Cu trecerea timpului a devenit tot mai cunoscută, iar din 1997 este susţinută de IBM. Numărul echipelor înscrise la ediţia de anul trecut a depășit 10.000, dintr-un total de peste 2.000 de universități de pe toate meridianele. Ediţia de anul acesta se va desfăşura la Sankt Petersburg, în perioada 30 iunie – 4 iulie.

 

În ultimii 10 ani, echipa României s-a calificat de patru ori în finala ACM ICPC, iar doi dintre foștii finaliști, Marius Dumitran și Andrei Grigorean, antrenează acum noua generație de ro-programatori.

 

Trimiși de Fundația eMag într-un cantonament de pregătire la Petrozavodsk, pentru a prinde la fața locului gustul viitorului duel de pe tărâm rusesc, Adrian, Mihai și Șerban speră la o clasare în vară în top 20. Das Cloud a stat de vorbă cu Mihai și Șerban, precum și cu antrenorii lor, pentru a afla cum arată o para-olimpiadă de informatică și ce super-conexiuni sunt necesare unor programatori câștigători. Un video-interviu, însoțit de o (nu atât de scurtă) dare de seamă a antrenantei discuții.

 

Interviu cu echipa României la concursul ACM ICPC 2013 from Das Cloud on Vimeo.

 

Das Cloud: Care sunt diferențele dintre o olimpiadă internațională și concursul ACM ICPC?

 

Andrei Grigorean: Concursul la care participă ei este pentru studenți. Și, deși nu este foarte cunoscut în România, e mult mai recunoscut internațional decât olimpiada. La Google (n.r. unde Andrei a făcut un stagiu de pregătire), colegii mei nu auziseră de olimpiada internațională, în schimb auziseră de ACM ICPC. România are tradiție la participările la olimpiadă, noi am fost cei care am găzduit prima și a doua ediție a olimpiadei internaționale de matematică. Am fost, deasemenea primii care am făcut olimpiada Europei centrale de informatică. Ca țară, avem o tradiție și o cultură a olimpiadelor. Care a început să dispară, dar asta este o altă poveste.

 

Care este diferența între aceste concursuri? În primul rând că sunt trei participanți într-o echipă, nu mai este un concurs individual. Au, deasemenea, un singur calculator. În loc de trei probleme au mai multe, 10-12. Și e mult mai greu, concurența e mult mai aprigă și problemele sunt mult mai grele. E, totodată, un sistem mult mai liber. Dacă la o olimpiadă internațională, fiecare țară vine cu patru concurenți, aici Rusia vine cu 19 echipe. Rusia e de departe cea mai tare țară la capitolul acesta.

”Natura problemelor nu se schimbă fundamental față de olimpiada internațională, doar că noțiunile sunt mai avansate: mai multă matematică” – Andrei Grigoreanu

 

Șerban Stan: Dacă venea și Rusia cu 2.000 de concurenți la o olimpiadă internațională, lua primele 30 de locuri.

 

Andrei Grigorean: Dacă olimpiada este mai degrabă politică, la modul că trebuie să ia puncte toți concurenți, și ăia din Bangladesh, și se mai dau și probleme ușoare ca să mai facă inflație de puncte, se mai dau și foarte multe medalii, în partea astalaltă e pur și simplu dur. În loc e 50% dintre participanți care iau medalii, aici iau doar 10% dintre participanți. Limitele de locuri alocate regiunilor se dau în funcție de rezultatele anterioare. De asta s-a ajuns ca Rusia să aibă 19 locuri și tot restul Europei doar 12. Rușii sunt pur și simplu atât de buni, încât au rezultate mai bune decât întreaga Europa la un loc.

 

Natura problemelor nu se schimbă fundamental față de olimpiada internațională, doar că noțiunile sunt mai avansate: mai multă matematică.

 

Das Cloud: Cum sună o problemă de la un concurs de informatică?

 

Andrei Grigorean: Anul trecut a fost un set de 12 probleme. Aveam un calculator, eram toți într-o sală, în total 112 echipe a câte trei oameni. Toți în aceeași sală, împărțiți pe mese.

 

O problemă suna ceva de genul: Tu ești șeful unei agenții de spionaj și tu trebuia să nu scapi spionii de sub control. Pentru fiecare om din agenție, tu știi care dintre ceilalți colegi ai săi poate să îl supravegheze. Trebuia, cumva, să îți alegi un sub-set de angajați care să îi supravegheze pe toți ceilalți. Vroiai un număr minim de informatori, astfel încât toți ceilalți să fie supravegheați de informatorii ăștia. Iar informatorii nu trebuiau să se supravegheze între ei. Citeai într-un fișier relațiile cu cine pe cine poate să spioneze. Sună a Securitatea, vremurile de dinainte de ‘89. Asta era problema la care ne-am blocat noi anul trecut.

 

O altă problemă de informatică este ce face Google Maps când îți calculează ruta între două puncte de pe hartă. E chiar un român care a lucrat pentru Google la dezvoltarea acestui algoritm.

 

Das Cloud: Ce instrumente aveți la dispoziție pentru a rezolva o problemă de informatică la un astfel de concurs?

 

”Avem voie să folosim doar calculatorul intern, n-avem nici net, nici măcar semnal la telefon. E ca la Bac” – Şerban Stan

Șerban Stan: Calculator la care lucrăm trei oameni și foi de hârtie.

 

Andrei Grigorean: Sunt foile alea și pixul care contează cel mai mult.

 

Șerban Stan: Avem voie să folosim doar calculatorul intern, n-avem nici net, nici măcar semnal la telefon. E ca la Bac.

 

Das Cloud: La ce vă ajută calculatorul?

 

Mihai Calancea: Trebuie să programăm pe el doar.

 

Șerban Stan: Trebuie să scriem codul în C˖˖ și îl scriem pe calculator. Ni se dă un fișier de intrare, cu cerințele problemei și noi trebuie să dăm la final un fișier de ieșire. După ce terminăm programul ăsta, îl trimitem pe un site al lor, al organizatorilor. Site-ul verifică automat rezolvarea problemei.

Mihai Calancea: Clasamentul la final e făcut pe numărul de probleme rezolvate, iar în caz de egalitate intră în calcul niște penalizări. Penalizarea e o combinație între cât de încet rezolvi problemele și cât de mult greșești înainte să îți iasă rezolvarea.

 

Andrei Grigorean: Pentru fiecare problemă contează când ai rezolvat-o corect. Tu știi în timpul probei dacă ai rezolvat-o corect sau nu. Poți să tot încerci să o rezolvi, dacă ai rezolvat-o greșit, ți se zice că ai rezolvat-o greșit și poți să reîncerci. În momentul în care ai rezolvat o problemă, se calculează câte minute au trecut de la începutul probei, și aia e penalizare. În total, proba are 5 ore. Să zicem că tu ai rezolvat problema corect, ai avut două încercări proaste și ai rezolvat-o doar după 60 de minute. În cazul ăsta, penalizarea totală e 60 de minute, câte au trecut de la începutul probei, plus 20 de minute de penalizare pentru fiecare încercare proastă. Va fi în felul ăsta o penalizare de 100 de minute. De aia e foarte important să ai acuratețe mare și să fii foarte rapid.

Alte articole