Interviu cu Radu Berinde - partea intai

Radu Berinde este unul din putinii romani cu doua medalii de aur la olimpiada internationala de informatica. Acum studiaza la MIT, iar vara trecuta a facut un internship la Google pentru a doua oara. Am avut ocazia sa lucrez cu el pe acelasi proiect si m-a impresionat prin o gramada de idei bune si viteza cu care scrie cod elegant si util. In aceasta prima parte a interviului ne povesteste ceva din experienta lui legata de olimpiade.

(Radu cu tiburonul sau).

Cum ai inceput cu informatica? Dar cu concursurile?

Eram prin clasa a patra cand sora mea a adus acasa un 286. Se intamplase ca imi rupsesem picioru (intr-un mic accident de masina) si stateam acasa toata ziua. Dupa ce m-am plictisit de ce jocuri se gaseau, am inceput sa ma uit din ce in ce mai interesat la ce facea sora mea, care isi scriea proiectu pt facultate in Pascal. Am invatat incet incet, pana am rescris de la capat tot proiectul (initial proiectul folosea programarea pe obiecte, eu l-am rescris fara obiecte). Asa a inceput pasiunea pentru programare; am tot continuat sa invat de prin carti si sa fac diverse programe. Prin clasa a 5-a sau a 6-a am inceput sa merg la Palatul Copiilor; acolo au vazut ca stiu deja destul de multe si am intrat direct in grupele unde se pregateau cei care mergeau la concursuri nationale de informatica. Am fost pregatiti foarte bine de Dna. Rodica Pintea. In clasa a 6-a am fost la primul meu concurs de informatica (la Lugoj), unde am luat punctaj maxim. Nu mai e nevoie sa spun ca de-atunci problemele de concurs au ramas pasiunea mea.

Ai participat si la alte olimpiade? Ai avut alte subiecte care ti-au placut in scoala?

Dintre subiectele de la scoala, cel mai mult imi placea matematica (surpriza..); participam la olimpiade si faceam destul de bine la proba de sector, dar la municipiu eram depasit total :) Am fost si la fizica o data sau de doua ori, dar spre sfarsitul gimnaziului nu prea mi-a mai placut. In liceu m-am concentrat destul de mult pe concursurile de informatica; nu pot sa zic ca m-am implicat prea mult in ce se facea la scoala.

Cum te antrenai pentru olimpiade?

In primul rand, lucram foarte multe probleme, de oriunde se putea: olimpiade din romania, internationale, din alte tari, USACO, ACM, orice. Incercam sa gasesc si teste ca sa pot verifica solutia mea. Pana prin clasele 9-10 mai participam si la pregatiri, la Palatul Copiilor, sau la liceu, organizate de Dna. Pintea sau alti profesori si studenti.

Ai avut pe cineva care te-a ajutat in lumea olimpiadelor, sau ai invatat totul singur?

Bineinteles, probabil mai multi decat pot mentiona aici. Cred ca cea mai mare influenta a avut-o Dna. Prof. Rodica Pintea, care a fost profesoara mea de la Palatul Copiilor. Am fost pregatit si de si de Dl. Prof. Atanasiu in anumite perioade. Am invatat mult si de la prieteni olimpici mai mari ca mine: Andrei Marius, Adrian Drumea, Andrei Gheorghe, Angel Proorocu (hmm de ce incep toti cu A?). La diverse pregatiri am mai invatat lucruri si de la alti (atunci) studenti fosti olimpici, ca Bogdan Batog, Mihai Stroe, Dumitru Bogdan.

Sunt cateva probleme ce ti-au ramas in minte de la concursurile la care ai participat?

Mi-a ramas in minte problema XOR de la IOI 2002. Se dadea o matrice cu patratele albe sau negre; se putea face o singura operatie, de a alege un dreptunghi (o submatrice) si a inversa culoarea tututor patratelelor din dreptunghi. Era cu intrare data in prealabil, si se cereau solutii cu numar de operatii cat mai mic. Solutia era un algoritm foarte simplu care obtinea o 2-aproximare - cu acest hint va las sa va prindeti singuri de el :)

Care e structura ta de date preferata?

Dintre cele mai de baza, AVL.. Dintre cele de geometrie, range trees (cu Willard-Lueker refinement/fractional cascading).

Care e algoritmul preferat?

Greu de spus exact, dar voi descrie ceva ce mi-a placut intodeauna foarte mult - algoritmii in timp liniar bazati pe ideea de lista dublu sortata, in care la fiecare pas se insereaza un element nou, stergandu-se mai intain elementele din coada listei care sunt mai "proaste". De exemplu, pentru problema sirului divizat: se da un sir de numere A[1..N], se cere un M maxim astfel incat toate A[1..M-1] sunt mai mici decat A[M] si toate A[M+1..2M] sunt mai mari decat A[M]. Se poate rezolva in timp daca la fiecare pas (pentru fiecare M) putem afla minimul elementelor A[M+1..2M}. Putem rezolva problema in timp liniar daca mentinem o lista dublu sortata pentru a afla la fiecare pas minimul elementelor A[M+1..2M]: lista e sortata crescator dupa valoare si dupa pozitie. Ideea este ca daca in zona curenta de interes avem doua numere A si B, A e la stanga decat B, si A > B, nu ne va mai interesa niciodata A, deci il putem arunca. Cand inseram un numar nou X mai intai stergem repetat ultimul element al listei pana cand acesta e mai mic ca X, apoi inseram pe X la sfarsitul listei. La fiecare pas se sterge si cate un element de la inceputul listei. Minimul va fi intotdeauna ultimul element din lista. Pentru o problema mai avansata care foloseste aceasta metoda, vedeti problema Batch de la IOI 2002.

Cate probleme crezi ca ai rezolvat la viata ta?

As zice ca peste 1000, poate chiar spre 1500-2000.

Ce mai tii minte din viata de olimpic? Care erau concurentii cu care te infruntai? (ai ramas prieten cu unii?)

Multi dintre cei din Bucuresti care participau la olimpiade (si faceau bine) imi erau (si sunt) prieteni buni. Era foarte placut sa ne intalnim la o bere si sa discutam probleme si idei de rezolvare. Formam un grup destul de mare, era foarte distractiv sa mergem impreuna la olimpiade sau loturi.

Stiu ca la IOI cand erai clasa a 12-a ai bushit doua probleme si tot ai luat aur, ne poti povesti mai mult despre acel episod?

Anul acela nu a fost atat de bun pentru mine (am facut destul de prost si la CEOI), n-as putea sa spun exact din ce motive. In prima zi a fost o problema grea la care am gasit o solutie inteligenta, insa era destul de complicata si intr-un program imens am uitat sa pun un if sau doua si am pierdut 100 de puncte (care la final m-ar fi adus pe locul 1). Am mai facut alte greseli si in ziua 2, mai mult din cauza rezultatului prost din ziua 1. Dar sunt convins ca mai toti care au luat aur atunci au facut si ei tot felul de greseli stupide, deci nu cred ca am fost neaparat mai ghinionist. Nu pot spune neaparat ca meritam sa iau mai mult, dar sunt sigur ca as fi putut sa fiu in forma mai buna in care sa nu am probleme. Pot spune totusi ca am fost dezamagit de subiectele de atunci, care nu mi s-au parut deloc la fel de frumoase si inteligente ca cele din 2002. M-a intristat un pic cand am realizat ca pana la urma te pregatesti ani intregi pentru 6 probleme care se poate intampla sa "iti pice prost" in ziua respectiva.

Cum te prinzi de probleme? Ai observat vreo metoda care ajuta?

A fost o evolutie destul de clara. Am lucrat multe probleme, pana cand la un moment dat eram foarte bucuros sa primesc probleme "clasice", insa eram inca speriat de cele "de idee". In timp insa, cunoscand problemele clasice am inceput sa am idei foarte bune. Nu e ceva ce poti sa obtii printr-o metoda anume; daca intelegi foarte multe idei, vei incepe la un moment dat sa le combini in moduri noi.