Interviu cu Catalin Francu - partea intai

Odata cu angajarea mea la Google am avut ocazia sa cunosc multi fosti olimpici, pe care ii stiam doar dupa nume, vazandu-i in Ginfo sau in listele cu premii la diverse concursuri. Unul dintre acesti olimpici este Catalin Francu , caruia, la o cina in San Francisco, i-am smuls promisiunea ca va raspunde la cateva intrebari pentru ce avea sa fie blogul infoarena. Acum va voi prezenta prima parte a interviului, dupa o scurta prezentare a lui Catalin.
Catalin este cunoscut in lumea celor pasionati de informatica prin cartea "Psihologia concursurilor de programare", o carte plina de probleme frumoase si deschizatoare de drumuri la vremea ei, si prin "lista lu' Francu", o lista de discutii pe email, unde cativa dintre cei ce au ajuns apoi olimpici internationali la informatica ai Romaniei rezolvau si discutau probleme. Iar in lumea lingvistilor este cunoscut prin proiectul dexonline . Acesta este un wiki (inovator pentru 2001, cand Catalin a inceput proiectul) care contine intreg Dictionarul Explicativ al limbii romane si alte dictionare. In timpul liceului, Catalin a luat o medalie de argint la olimpiada internationala de informatica, iar in timpul facultatii s-a clasat pe locul 7 la etapa finala a concursului ACM ICPC cu echipa reprezentanta a MIT. De asemenea a facut parte din comisia stiintifica a Olimpiadei de Informatica a Europei Centrale din 2000 care s-a desfasurat la Cluj. Dupa terminarea facultatii Catalin a lucrat patru ani ca programator la Google inc.

In aceasta prima parte a interviului, Cata ne vorbeste de olimpiade, de cartea "Psihologia concursurilor de programare" si despre "Lista lu' Francu".

Cum ai inceput cu informatica?

Parintii mei au facut parte din primele generatii de la ICI, ceea ce si-a pus amprenta asupra mea si a fratelui meu. Prin clasa a 4-a am vazut prima oara un calculator ZX Spectrum. Mi-au placut mult jocurile, iar cu timpul am inceput sa ma intreb si cum sunt facute si daca as putea face si eu ceva asemanator. in clasa a 8-a, cand s-a pus problema sa-mi aleg un liceu, deja nu mai aveam dubii.

Erau alte discipline de care erai interesat in timpul scolii?

Da... in dictionar, langa definitia pentru "tocilar" este poza mea :) Am invatat multe prostii care acum imi dau seama ca au fost pierdere de vreme, dar unele materii chiar mi-au placut. De felul meu am fost atras de matematica si fizica. Muzica si biologia erau frumoase, dar erau predate foarte prost.

Cum si ce lucrai pentru olimpiade?

Generatia mea (promotia 1996) n-a avut foarte multe resurse la indemana. Circulau colectii de probleme din anii trecuti, dar comunicarea intre olimpici era de baza, pentru ca unul afla de un algoritm interesant si il raspandea. Manualele domnului profesor Sorin Tudor au fost multa vreme "Biblia" mea; de altfel consider ca la vremea lor au fost pur si simplu avangardiste (si nu stiu cati profesori se pricepeau sa predea notiunile pe care le contineau acele manuale).

Ce persoane au avut o influenta in formarea ta?

Parintii si fratele meu Cristi, in primul rand. Mi-amintesc ca eram prin clasa a 2-a, iar Cristi tocmai invata despre scheme logice si se chinuia sa mi le explice si mie. Mie imi placeau romburile cel mai mult, dar altceva n-am inteles. :) La liceu am avut multi profesori buni de informatica, dar in special doamna Rodica Cherciu si domnul Sorin Tudor. Este adevarat ca un profesor poate sa atraga sau sa sperie un elev, dupa cum isi preda materia. Nu in ultimul rand, la loturile de informatica au fost intotdeauna oameni deosebiti (elevi si profesori). in lumea olimpiadelor mi-am cunoscut multi dintre prietenii de astazi.

Mai tii minte probleme frumoase de la olimpiada?

Mi-a placut intotdeauna, pentru simplitatea ei, problema acoperirii tablei cu L-triominouri (Se da o tabla cu dimensiunea de din care s-a eliminat un patrat. Se cere ca restul sa se acopere cu L-triominouri). Am pus de multe ori aceasta intrebare la interviuri la Google si putini au stiut sa o rezolve in 10-15 minute. Problema care m-a determinat sa ma apuc serios de studiul algoritmilor este "Se da un arbore neorientat. in fiecare nod se afla un bec. Initial toate becurile sunt stinse. Prin atingerea unui bec, el si toate becurile vecine isi schimba starea. Sa se identifice o ordine de atingere a becurilor astfel incat in final toate becurile sa fie aprinse."

Ce structura de date iti place cel mai mult?

E greu de raspuns la intrebarea asta. E mai important sa stii la ce e buna o structura de date decat sa-ti placa. De exemplu, am cunoscut oameni care nu suporta listele inlantuite si folosesc intotdeauna vectori, chiar si atunci cand au de facut insertii sau concatenari.
Cand folosesti Java si ambele structuri sunt deja implementate, si trebuie numai sa stii de ce tip sa declari variabila, aceasta reticenta este foarte daunatoare.

Pentru simplitatea implementarii, imi plac mult seturile disjuncte cu compresia caii (folosite, de exemplu, in algoritmul lui Kruskal pentru aflarea arborelui partial de cost minim). Analiza teoretica a complexitatii este foarte subtila.

Sunt olimpiadele folositoare?

Este iarba verde? :)

Cum e de partea cealalta a baricadei in concursurile de informatica, cand participi ca organizator?

Avem mai putin timp liber, pentru ca mereu e cate ceva de facut, dar satisfactiile si placerea sunt la fel de mari. Daca vreun student sau un profesor are un ceas liber, prefera sa implementeze o solutie pentru vreuna din probleme. Nu numai pentru ca e bine sa avem mai multe solutii pentru verificare, ci si din acea dorinta, care ne impinge pe toti la concursuri, de a ne masura fortele cu o problema noua.

Cum ti-a venit idea sa scrii "Psihologia Concursurilor de Programare"?

Domnul profesor Sorin Tudor a venit cu ideea sa-mi impartasesc cateva din experientele de la olimpiade. Pentru ca de aici nu aveau cum sa rezulte mai mult de 10-20 de pagini, m-am gandit sa adaug cateva structuri de date pe care le-am folosit destul de frecvent la concursuri si care nu erau discutate in manualele de liceu.

Cum ai ales structura cartii si problemele?

M-am gandit la cateva structuri de date, implementabile in timp de concurs, despre care elevii nu prea aveau de unde citi. Problemele alese fie exemplifica folosirea acestor tipuri de date, fie subliniaza unele alegeri care tin de psihologia fiecarui concurent. De exemplu, am gasit un algoritm greedy care merge pe toate exemplele mele, dar nu il pot demonstra matematic. il implementez sau nu? Sau am gasit un algoritm lent cu care stiu ca nu o sa iau punctaj maxim. il implementez sau caut altul mai bun?

Cat timp ti-a luat sa scrii cartea si cat de usor a fost sa o publici?

Cateva luni, dintr-o vacanta de vara pana prin noiembrie. Publicarea nu a fost o problema, deoarece ideea cartii a venit tocmai de la Sorin Tudor, care avea propria editura. Mai problematica a fost tiparirea, pentru ca la migrarea pe alt calculator si pe alta imprimanta, se dadea peste cap toata paginarea (pe vremea aceea nu auzisem de LaTeX, de PDF, sau in general de altceva in afara de Microsoft Word).

A meritat efortul?

Fara nici un dubiu! A fost una din primele mele slujbe platite, am castigat un ban facand ceea ce imi placea si a rezultat ceva palpabil si -- din cate aud -- folositor.

De ce ai inceput lista lui Francu?

In 1996 am inceput (sau mai degraba am continuat, de unde l-a lasat fratele meu) un mic cerc de informatica. Cu timpul am inceput sa corespondam si prin email. Emailurile au capatat valoare in sine si am creat o lista de discutii dedicata.

Cum a evoluat lista si discutiile de pe lista de-a lungul timpului?

La inceput, trimiteam probleme, asteptam o saptamana si corectam solutiile trimise. Perioada cea mai buna a listei, zic eu, a fost cand am introdus o notiune de "coeficient" (se numea DFCC si se masura in Dexteri). Dincolo de copilaria numelui, m-am straduit sa nascocesc un coeficient care scadea incet cu timpul, pentru a-i incuraja pe abonati sa trimita solutii la fiecare etapa.

De ce a murit?

Plecarea la MIT a fost "inceputul sfarsitului". Aveam mai putin timp liber si o vreme s-a ocupat Cristi Cadar de lista (de altfel, el a propus aproape jumatate din numarul problemelor). Ocazional au mai contribuit si alti "ilustri" ca Rodica Pintea, Valentin Gheorghita, Mihai Badoiu, Irina Dumitrascu, Bogdan Dumitru, Alex Susu...

Un alt motiv a fost ca elevii care au participat initial la cercul de informatica au absolvit liceul, ceea ce mi-a redus mie motivatia de preparator. :) si nu in ultimul rand a fost aparitia altor site-uri, romanesti si internationale, dedicate problemelor de programare, cu evaluatoare automate etc. Ma bucur mult ca infoarena.ro incorporeaza majoritatea problemelor propuse pe lista, pentru ca ne-am gandit mult la ele si ar fi fost pacat sa se piarda.

A doua parte a interviului va fi publicata in curand.

In contextul interviului cu Cata (cum ii zic prietenii), infoarena are doua proiecte unde este nevoie de ajutorul vostru. Unul este transcrierea cartii "Psihologia concursurilor de programare" in format textile. Altul ar fi cel de transformare a problemelor din Lista lu' Francu in formatul infoarena si de adaugarea lor in arhiva (au mai ramas vreo 10 probleme de adaugat). Aveti mai multe detalii aici si aici .

In poza de mai sus apar Cristi Strat , 'maestru' Catalin, eu , iar cenzurati sunt doi ilustrii necunoscuti :), se dau puncte de karma pe forum pentru cine ii identifica pe cei doi.