L-am rugat pe Andrei Grigorean sa ne scrie un jurnal despre experienta lui la Olimpiada Interantionala de Informatica. Initial ma gandeam ca ar fi misto sa ne zica aproape live ce s-a intamplat in fiecare zi :), dar asta ar fi adaugat la stresul competitiei. Astfel am fost bucuros cand s-a oferit sa faca un rezumat dupa concurs, apoi am fost si mai bucuros cand l-a terminat. Multumim Andrei! Acum puteti sa il cititi si voi:

IOI 2007

In perioada 15-22 august 2007 am avut ocazia de a participa la cea de a XIX-a editie a Olimpiadei Internationale de Informatica , desfasurata in capitala Croatiei, Zagreb. Ceilalti trei membri ai lotului Romaniei au fost: Cosmin Gheorghe, Bogdan Tataroiu si Adrian Airinei. Am fost insotiti de prof. Emanuela Cerchez (Team Leader) si de Mugurel Ionut Andreica (Deputy Leader).

Acomodarea

In data de 15 august, la ora 4:30 dimineata, ne-am intalnit cu totii la aeroportul international "Henri Coanda" din Otopeni. Am zburat pana in Budapesta, unde am schimbat avionul pentru a ajunge in Zagreb. Am aterizat in Croatia pe la amiaza si am fost una din primele delegatii sosite. Un autocar ne astepta in fata aeroportului si am fost dusi in complexul unde am fost cazati si unde am luat masa timp de o saptamana. Am stat cate doi in camera, eu impreuna cu Cosmin, respectiv Bogdan cu Adrian, si imparteam aceeasi baie. Conditiile nu erau extraordinare, insa nici nu ne puteam plange - erau totusi camine studentesti. In privinta mancarii insa, am doar cuvinte de lauda. Puteam servi oricat doream din mese diverse, foarte gustoase. Am mancat foarte mult la IOI, mai ales eu si Cosmin :P.

Competitia

Inainte cu o zi de a incepe competitia a avut loc sesiunea de pregatire. Scopul acestui eveniment este familiarizarea cu sistemul folosit in concursul real si oarecum o usoara "incalzire" a concurentilor. Am avut posibilitatea de a implementa si submita timp de doua ore cele trei probleme afisate pe site-ul olimpiadei cu trei saptamani inainte. Totul a decurs bine, cu exceptia catorva probleme cu Rhide-ul.

Apoi a venit prima zi de concurs. Eu personal ma asteptam sa fie probleme interesante si asa a si fost. Am primit doua batch-uri si o problema interactiva. Dupa o scurta trecere in revista, am decis sa aboredez mai intai problemele sails si flood. Dupa doua ore si jumatate nu gasisesm nicio rezolvare, moment in care m-am hotarat sa incerc aliens. Dupa aproximativ o jumatate de ora gasisesm rezolvarea si am inceput sa implementez. Pana la sfarsitul concursului nu am mai reusit sa gasesc solutiile optime la sails sau la floodm asa ca am trimis rezolvari brute-force (la flood am terminat de implementat cu 5 minute inainte de final). Rezultatele din prima zi au fost conform asteptarilor: Cosmin - 235 pct (a facut sails de 100), Bogdan - 172 pct, eu - 145 pct si Adrian - 120 pct. Dupa estimarile mele aveam un aur, un argint si doua medalii de bronz cu aceste punctaje. Nu am reusit niciunul sa rezolvam problema flood, desi dupa ce am auzit solutia mi se parea mai simpla decat estimasem initial. Si punctajele obtinute de ceilalti concurenti aratau ca sails fusese cea mai grea din prima zi, nu flood.

A doua zi de concurs a fost putin diferita de prima. Am primit trei batch-uri, de dificultate variata. Miners era clar problema simpla, imediat cum am citit-o am si implementat-o. S-a dovedit ca peste 100 de concurenti au luat maxim la ea. Pairs era de fapt compusa din trei subprobleme independente - am gasit rezolvarea in timp util la toate, insa trebuia sa implementez arbori de intervale 2D, asa ca am decis sa o las la urma si sa incerc sa rezolv training. Aceasta a fost cea mai grea problema din concurs, cu doar 3 punctaje maxime :). Nu am reusit sa gasesc solutia optima, asa ca dupa ce am implementat o sursa care lua 30 de puncte, m-am intors la pairs. Faptul ca nu am implementat pana la urma ultima subproblema, si ca am uitat sa pun un -1, au facut ca punctajul meu in a doua zi sa fie de 172 de puncte. Adrian si Bogdan au luat 200, iar Cosmin 150.

Excursii

Dupa fiecare zi de concurs, organizatorii ne-au dus in doua excursii care mie mi-au placut foarte mult. Prima din ele a fost la un lac unde se pregateau sportivii croati pentru diferite sporturi pe apa (gen canoe). Acolo ne-am petrecut jumate de zi. Eu si Adrian, impreuna cu 3 bulgari, am jucat fotbal cu rusii, care aveau o mare vedeta in echipa - Petr Mitrichev. Daca la informatica nu am fost mai buni, macar la fotbal i-am batut... de doua ori :D. Se mai putea juca badminton, tenis de masa - a fost un fel de picnic cu vreo 400 de persoane.
A doua excursie a durat o zi intreaga. Am vizitat Lacurile Plitvice si casa memoriala Nikola Tesla. Puteti vedea cateva poze aici. Peisajele erau superbe, aratau mai bine in realitate decat in poze. Am fost la cea mai mare cascada din Croatia (din pacate nu apare in album), iar dupa masa am ajuns la casa memoriala a faimosului om de stiinta - pe mine nu m-a impresionat prea tare, nu aveau o modalitate atractiva de a prezenta informatia.

Sfarsit de poveste

Cu punctajele noastre am obtinut pana la urma cu totii medalii de argint, sa speram ca in anii urmatori Cosmin si Bogdan, impreuna cu ceilalti participanti la IOI, vor face mai bine decat am facut noi anul acesta. Ne-am intors acasa pe data de 22 august pe aeroportul "Henri Coanda", unde ne asteptau parinti, profesori, reprezentanti Intel si presa. Si-am incalecat pe-o sa, si v-am spus povestea asa.

Felicitam echipa Romaniei inca o data pentru rezultatul obtinut si mentionam ca dupa olimpiada, cei doi seniori ai echipei (Andrei Grigorean si Adrian Airinei ) s-au alaturat echipei infoarena .

Din dorinta de a face enuntul problemei cat mai simplu am lasat cateva cerinte ale problemei nespecificate. De aici au aparut si cele trei updateuri la text.

Cei care au rezolvat problema sunt: Teodorescu Andrei-Marius , Adrian Sandor si Radu Cebanu.

V-am promis si o solutie:
Impartim planul in patrate de latura unu. Suprapunem toate patratele unul peste celalalt, si cum aria totala a petelor este strict mai mica ca unu rezulta ca va exista un punct care nu este acoperit de vreo pata. Marcam acest punct in toate patratele. Cand le punem inapoi in plan, punctul marcat se transforma in o grila de puncte. Acum putem selecta ca origine oricare dintre aceste puncte si ca axe dreptele paralele cu abscisa respectiv ordonata din sistemul initial, care trec prin punctul ales ca origine.

Sper ca v-a placut, chiar daca e o problema de mate.

Scoala a inceput de ceva vreme si se apropie perioada concursurilor online. Ca in fiecare an, din 2004 incoace, echipa infoarena va pregateste o noua editie a concursului preONI. Primul pas ar fi gasirea unui logo pentru concurs, si aici avem nevoie de ajutorul vostru.

Majoritatea logourilor folosite pe site au fost facute cu ajutorul userilor. Sa vedem cum au aratat siglele de-a lungul timpului.

La inceput infoarena.devnet.ro avea acest logo:

Cand s-a facut trecerea la a doua versiune a siteului pe domeniul infoarena.ro, Dan Burzo ne-a facut o sigla simpatica, in care mascota siteului are ochelari, ca orice geek respectabil, dar poarta un coif pentu ca e gata de lupta in arena.

Logoul pentru preONI 2006 a fost realizat tot de Dan Burzo.

Iar logourile pentru fiecare runda de Cristina Stancu Mara

Urmatoarele doua logouri au fost facute pentru preONI 2007. Al doilea nu a fost folosit.

autor Radu Lupaescu

autor Alexandru Marinescu

Le multumim inca o data celor ce ne-au ajutat si vrem sa va cerem ajutorul in realizarea unui logo pentru preONI 2008. O sugestie ar fi pentru culorile alese sa se integreze bine cu cele ale siteului.

Dumitru Daniliuc mi-a zis o problema simpatica de pe vremea cand se antrena in liceu pentru olimpiadele de matematica, pe care acum vreau sa v-o zic si voua.

Problema suna asa: Se da o multime S, de puncte in plan. Aria ocupata de puncte e strict mai mica decat unu. Se cere sa se gaseasca un sistem de coordonate astfel ca punctele de coordonate intregi din acest sistem de coordonate sa nu se suprapuna peste nici un punct din multimea S.

Va rog, daca aveti solutii, sa nu le publicati pe forum ci sa mi le trimiteti ca mesaj privat. In doua zile voi publica o solutie si numele celor ce au rezolvat corect problema.

Update: Multimea S poate contine o infinitate de puncte. De exemplu S e formata din cateva pete si o dreapta. Aria dreptei e 0 si suma ariilor petelor e mai mica ca 1.

Update2: Pentru a nu complica problema si definitia a ce inseamna arie, impunem restrictia ca multimea S este formata din un numar finit de pete, fiecare avand o arie. Deci S nu va contine drepte, spirale sau mai stiu eu ce.

Update3: Sistemul de coordonate trebuie sa fie ortonormat si sa pastreze dimensiunile initiale.

Eu stiam de Jon Bentley pentru ca este autorul cartii Programming Pearls, o carte scrisa foarte bine si care se citeste foarte usor, spre deosebire de Introducere in algoritmi. Ea contine multe trucuri dragute de algoritmica si poate reprezenta o introducere foarte buna pentru cei ce vor sa invete algoritmica. Singura problema e ca nu este tradusa in romana.

Astfel am fost curios cand Jon a avut o prezentare, numita Three Beautiful Quicksorts, la Google acum doua luni. In talk apar chestii interesante cum ar fi optimizarea metodei qsort() din C (si ca paranteza Joshua Bloch mentioneaza ca implementarea din Java a functiei sort() urmareste indeaproape ideile din talk) sau o imagine in care vedem ca variante diferite ale quick sortului nu au graficul similar cu cel al functiei , ci se vad trei bucati care se comporta diferit, ele corespunzand nivelelor de cache si memoriei. Sperand ca v-am deschis putin apetitul, puteti sa vizionati aici prezentarea:

Ultimul feature adaugat la site este un blog. Va invitam sa il folositi si speram sa fie interesant si util.

Am avut ocazia sa il reintalnesc acum vreo doua luni pe Mihai Patrascu dupa ce ultima data cand il vazusem a fost la Olimpiada Nationala de Informatica din Bacau in 2001. Era venit in Bay Area la un internship la centrul de cercetare IBM Almaden. I-am propus atunci sa facem un interviu pentru viitorul blog de pe infoarena.

Mihai Patrascu are printre cele mai bune rezultate la olimpiadele internationale la informatica dintre romani. A luat premiul I la Olimpiada nationala de informatica din clasa a 4a (concurand la clasa a 5a) pana intr-a 12a. La olimpiada internationala la de informatica a luat doua medalii de aur si una de argint (in 2001 a fost locul doi la internationala). La Concursul Europei Centrale de Informatica a luat un aur si un argint, iar la Balcaniada de informatica un argint. In 2005 a luat premiul Outstanding Male Undergraduate Award pe Statele Unite si Canada. Are chiar si o pagina pe wikipedia

Interviul va fi impartit in doua parti. In aceasta parte Mihai discuta despre MIT, despre cercetare si despre olimpiade:

Cum ai inceput cu informatica?

In clasa a 2a, am decis sa ma duc la Palatul Copiilor si sa studiez electronica. Din pacate, cursul de electronica se umpluse, dar mai erau locuri la cursul de programare...

Ai avut pe cineva care te-a ghidat? Un mentor, o persoana de la care ai invatat?

Nu, practic niciodata. La mai sus-mentionatul curs de programare am invatat sa programez in Basic timp de cateva luni, si am fost captivat. Dar cu asta s-au sfarsit cursurile de programare care le-am luat. Am invatat Pascal dintr-o carte intr-a 4a, C din alta carte (in engleza) intr-a 6a, apoi pentru pregatire mai serioasa la olimpiada am citit GInfo, probleme de pe la concursuri, Knuth si CLR. In liceu am fost la profilul de mate-fizica.

Prin facultate a continuat cam la fel. Dupa 1 an la MIT m-am mutat in departamentul de matematica (ca protest pentru departamentul de CS care nu ma lasa in pace), asa ca n-am luat nici pana azi nici un curs de programare. Am luat multe cursuri de algoritmi, evident. Dar n-au avut niciodata legatura cu cercetarea mea :) Probabil mi-am ales domeniul de lucru dupa aceleasi criterii: un domeniu unde nu se facuse progres de peste 15 ani, si ca atare nu mai existau nici profi nici cursuri predate in mod curent...

De ce MIT si nu alte universitati din state sau din Romania?

Am facut un an la poli in Craiova, dar era o atmosfera trista. Practic lumea nu era acolo decat ca sa ia o diploma, si, partea cu adevarat trista, diploma aia nici nu prea conta...

In State, doar MIT-ul m-a acceptat :) Simplu.

Cum a fost procesul de admitere? Cat de mult conteaza o medalie la olimpiada internationala?

Pana acum cativa ani, la MIT studentii internationali erau practic 100% cu medalii la diverse discipline, si clar asta era criteriul de baza. Multe alte universitati (gen Harvard si restul de Ivy League) cautau oameni cu un profil diferit, care sa ajunga politicieni, manageri etc. In perioada aia era faimoasa bariera culturala intre studentii de la MIT si cei de la Harvard.

In zilele noastre a aparut o oarecare convergenta. Internationalii de la MIT sunt mult mai "normali" si doar putini mai au medalii, in timp ce celelalte universitati au inceput sa aprecieze mai mult oamenii cu medalii.

La MIT au fost multe proteste (spre exemplu, Leiserson s-a plans mult) si speram sa revenim la admisia mai elitista (decanul de admisii a fost concediat recent, pe alte motive, si anul asta vom vedea ce face noul decan).

Cum e viata unui roman la MIT, sunt romanii sau strainii in general priviti ca outsideri?

La MIT e foarte greu sa gasesti americani... Toti "americanii" sunt de fapt la prima generatie, fiind imigrati recent impreuna cu parintii. Asta se datoreaza educatiei la nivel de liceu in State, care orienteaza lumea spre stiinte sociale, avocatura etc. Persoanele care stiu teorema lui Pitagora la liceu sunt "buni la matematica", iar cei care Doamne-fereste iau un curs de trigonometrie sunt "geeks".

La toate capitolele, MIT-ul este mai mult decat deschis... Majoritatea oamenilor sunt foarte inteligenti, si exista o toleranta foarte mare (dupa principiul ca oamenillor destepti li se permite). Cei mai ciudati oameni i-am vazut la MIT.

Cursuri preferate in facultate?

Advanced Data Structures (care l-am si predat un an), Advanced Algorithms, Randomized Algorithms, Geometric Computing, Computer Architecture, Microeconomics, Syntax (in lingvistica, nu programare :p)

De ce cercetare si nu programare?

Cred ca mentalitatea de om de stiinta ma caracterizeaza. Imi doresc foarte mult sa aflu raspunsuri, nu numai sa fac ceva care sa mearga. Ca cercetator pot sa las ceva in urma, ceva cunostiinte noi pentru omenire. Ca programator m-as simti mult mai egoist -- fac ceva ca sa castig eu niste bani.

In plus, programarea mi s-a parut intotdeauna o unealta la ce facem noi, nu un scop in sine. Principalul este sa te gandesti, sa "te prinzi", si apoi poti sa stai cuminte si sa programezi ideea. Dar esenta e ideea. Un programator bun e unul care gandeste bine, nu unul care tasteaza repede.

Te-au influentat in vreun fel olimpiadele din liceu?

Foarte mult. Motivul evident e ca mi-au oferit o deschidere -- am vazut locuri noi, oameni noi, probleme mai grele, si apoi din cauza lor am ajuns la MIT. Motivul mai subtil dar mai important e ca olimpiadele au fost locul ideal pentru dezvoltarea spiritului competitiv. In Romania este foarte usor sa ajungi blazat si mediocru. La olimpiade descoperi ca poti sa castigi si poti sa pierzi, iar agonia si extazul sunt la un pas distanta. Odata ce prinzi gustul luptei, iti vei dori mereu sa faci mai mult in viata, si asta te face un om mai reusit.

Ti-a ramas in minte vreo problema de la concursuri?

Am dat la BOI'03 o problema draguta cu Farey sequence. E exemplul meu favorit despre cum problemele de concursuri pot fi interesante si pentru "oamenii mari". La concurs era suficienta o rezolvare in , si s-au prins cativa oameni. Apoi m-am mai gandit la problema, am gasit o rezolvare in si am publicat-o la o conferinta de Algorithmic Number Theory, ca amuzament matematic. Oamenilor le-am placut, si recent un tip din Polonia (care a fost si
el la IOI prin 1995) a gasit in algoritm in , care l-a publicat la European Symposium on Algorithms. Bineinteles ca asta m-a motivat, si i-am imbunatatit algoritmul la -- deci recordul revine la Romania :)

Nu e o problema fundamentala care chiar sa conteze, dar arata cum tipul de rationament de la olimpiada e acelasi ca pentru cercetare.

Cum te antrenai in timpul liceului? Studiai din carti? Rezolvai probleme de pe siteuri cu evaluatoare automate? Discutai probleme cu colegii?

Pe vremea mea nu prea existau siteuri cu evaluare automata. N-am folosit niciodata unul, desi cred ca sunt utile.

Eu in principal citeam carti, GInfo, etc si ma gandeam la probleme. Discutam destul de mult cu ceilalti concurenti, de la care invatam idei interesante. Asta se intampla la lot, pentru ca in Craiova nu era nimeni cu care sa pot sa discut.

Ai vreun algoritm/structura de date preferata?

Partial sums, care este o structura de date foarte clasica si simpla. Problema: ai un array , poti sa faci update (A[i] = valoare noua), si queries: raporteaza suma , pentru k dat.

Cred ca toata lumea stie ca se face in cu binary trees, si ideea e super-utila in multe probleme.

Cand am ajuns la MIT, vroiam sa incep sa lucrez in cercetare si citeam lucrari pe care le gaseam pe Internet sa vad despre ce e vorba. Am citit undeva ca nu s-a putut demonstra ca e optim la problema asta (spre exemplu, ganditi-va ca pentru a face un dictionar, in loc de binary trees poti sa folosesti hashing, care merge in timp constant). Mi s-ar parut straniu ca nimeni n-a putut demonstra asta, asa ca am scris un paper in care am demonstrat. Mi s-a spus apoi ca asta era "problema nr 1" in data structures din 1989, am fost invitat sa dau talkuri despre solutie, si am primit si un premiu.

Totul a fost accidental, pur si simplu eu nu stiam nimic si am avut o perspectiva total diferita de toata lumea... Dar acum evident sunt foarte atasat de problema asta :)

A doua parte din interviu va fi publicata in curand.

 Salutare, sunt Cosmin Negruseri si sunt bucuros sa va anunt ca infoarena si-a tras blog.

 Vorbeam cu Cristi pe la inceputul verii de nevoia unui blog pe inforena. Am ajuns imediat la concluzia ca trebuie sa fie un blog nativ pe infrastructura infoarena si nu unul pe care doar sa il integram. Pe de o parte nu ar trebui sa reinventam roata, dar pe de alta parte sunt multe feature-uri ale siteului de care vrem sa ne folosim.

 Am discutat si cu Mircea care era interesat de partea de programare, dar a avut timp de ea doar dupa ce si-a terminat internshipul pe vara in Redmond. A terminat prima varianta vinerea asta, dar a pus noul feature pe site doar dupa concursul de duminica. Inca mai e de lucru pe partea tehnica, dar e mai bine sa incepem mai repede decat mai tarziu.

Bine ati venit pe blogul infoarena, speram sa plecati de pe el putin mai destepti de fiecare data.

Vacanta de vara a ajuns la sfarsit. E timpul sa te revezi cu vechii tai prieteni de la concursurile de info si sa le demonstrezi ca ai ramas in forma. :)
Te invitam sa participi la runda 1 a concursului Autumn Warm Up cu probleme propuse de utilizatori infoarena.

Runda 1 se desfasoara Marti, 11 septembrie 2007, orele 10⁰⁰ - 15⁰⁰.

→ Autumn Warm Up, Runda 1

Concursul online Summer Challenge organizat de infoarena s-a incheiat.
Felicitari participantilor si, mai ales, castigatorilor!

→ Clasamentul cumulat pe cele 3 runde
→ Pagina concursului

Speram ca a fost o experienta utila pentru lotul Romaniei la IOI 2007 (care incepe peste numai 3 zile!).
Va tinem pumnii!