Vine Olimpiada

Cosmin
Cosmin Negruseri
26 ianuarie 2008

Se apropie olimpiada judeteana si ma gandeam de ceva vreme sa scriu un articol despre diverse metode de antrenament. Am exagerat putin cu lungimea articolului, probabil am avut in minte postul Size matters a lui Steve Yegge, dar va incurajez cu caldura sa il cititi in totalitate. Sper sa va placa sa il cititi in aceiasi masura in care mi-a placut mie sa il scriu.

Tin minte senzatiile de la olimpiadele de mate din gimnaziu, cand ajungeam la concursuri regionale sau nationale si nu prea intelegeam despre ce vorbeau unii elevi de exemplu "principiul cutiei" sau "media patratica". Un elev era foarte nervos ca nu facuse "problema cu musca" la clasa. Stiind trucul respectiv ar fi rezolvat toate patru problemele la olimpiada nationala, fara acel truc a ramas doar cu trei probleme rezolvate perfect. Eu eram foarte fericit ca anul ala rezolvasem o problema si un subpunct de la alta si mergeam cu capul sus acasa cu un premiu.

Alta amintire este ca in clasa a 8-a rezolvasem o problema de distanta in spatiu de care eram foarte multumit si la o tabara de pregatire un elev din Arad, si el pe clasa a 8-a, mi-a zis ca a rezolvat problema respectiva in 5 metode, una dintre ele folosind integrale. La aceiasi tabara nu imi iesise o problema de geometrie in plan care cerea minimizarea unor distante si acelasi elev din Arad mi-a aratat o cartulie ce trata acel gen de probleme si mi-a zis ca daca studiam cartea inainte ma prindeam de problema. Eu abia daca rezolvam o culegere de probleme intr-un an de zile ...

Era o problema de standarde diferite, cum inca nu eram copt, credeam ca ideile apar din aer si e de ajuns sa stii la nivel de clasa matematica si apoi sa te "scremi" tare ca sa reusesti sa rezolvi problemele.

In liceu am trecut pe info, unde mi se parea mai usor. Erau doar vreo doua culegeri de probleme nu mii ca la matematica prin care sa filtrezi pana sa gasesti una ca lumea. L-am cunoscut pe Adi Carcu cu care si acum sunt foarte bun prieten. Mergeam la el acasa destul de des si povesteam probleme pana se facea tarziu ... cred ca parintii lui se intrebau cand o sa plec :).

Pana in clasa a 11-a aveam idei pe la probleme dar nu imi iesea implementarea la nici una. Atunci a inceput concursul Bursele Agora la care am participat serios facand la fiecare problema solutii diferite, evaluator, generatoare de teste aleatoare si soltuii brute force. Abia dupa ce am facut 15 probleme de la Bursele Agora ca lumea am inceput sa am incredere in abilitatile mele de implementare. Atunci am dat si peste Cormen, si eram tare entuziast pentru ca inainte nu aveam de unde invata si deodata aveam o carte in care erau explicate toate chestiile despre care auzisem.

Cred ca atunci a fost momentul cand am devenit pasionat de informatica. Citeam in fiecare zi cate ceva mai si implementam si ma gandeam la probleme, si asa mi-am dat seama ce inseamna sa fii olimpic. Cand esti pasionat faci un lucru din placere in fiecare zi. Nu tragi tare cu o saptamana sau doua inainte de judeteana sa acoperi ceva material din programa. Pentru un elev pasionat nu exista programa ci doar placerea de a rezolva probleme si de a invata ceva nou.

Mi-am dat seama cum la matematica eram un pigmeu fata de cei care se pregateau serios. Nu se poate compara munca de un an cu cea de cateva saptamani sau doua luni.

In facultate am meditat de cateva ori un elev care obtinea rezultate destul de bune, dar cand a venit la pregatire am vazut rapid ca nu avea baze teoretice aproape deloc, facea totul dupa intuitie si se descurca bine. A venit cu vreo doua luni inainte de olimpiada si apoi a doua data cu 2 saptamani, si i-am zis ca are o gramada de gauri in cunostinte. El mi-a replicat ca in astea doua saptamani trage tare. Mi-a venit sa rad si i-am zis ca nu are rost sa se chinuie sa acumuleze multa informatie ci sa foloseasca aceiasi metoda care i-a mers si pana atunci. Problema e ca dupa ce faci un salt in cunostinte, la inceput nu rezolvi probleme mai usor, ci iti dai seama ca abordarile tale sunt gresite. Astfel in loc sa mai incerci o abordare gresita cu care ai putea castiga 60-70 de puncte vei astepta ideea care rezolva perfect problema. Dar ideea respectiva s-ar putea sa nu vina si tu sa ramai cu 0 puncte. Invatarea si evolutia e un maraton nu un sprint (am furat expresia asta de la Emanuel, colegul de apartament ;)).

Radu Berinde imi povestea cum intr-o vacanta de vara facea probleme pe acm.timus.ru toata ziua, in vremea aia era al 4-lea in clasamentul rezolvitorilor de pe site. Programul lui zilnic era: antrenamente la sala, iesire seara la bere, si probleme pe timus in restul zilei. Mi se pare o vacanta destul de misto :)

Adi Carcu nu se antrena mai deloc pentru concursuri, inainte de judeteana facea una sau doua probleme ca sa fie sigur ca nu si-a iesit din mana si cam atat. Dar el intrase in lot din clasa a 9-a si acolo facuse antrenamente serioase unde luptai pentru locul la un concurs international. Mihai Patrascu zicea ca o tabara de antrenament ar fi durat o luna in vremea cand participa Adrian.

Pe langa asta, Adi avea tot timpul proiecte personale de programare la care lucra (printre care un chat listener pentru reteaua din camin :)), si cred ca ele ajuta chiar daca nu sunt de algoritmica. Adi dupa fiecare lot trecea prin problemele ce s-au dat si incerca sa le rezolve astfel incat codul sursa sa fie eficient, foarte inteligibil si foarte scurt. Tot timpul programele lui mi se pareau foarte simple si lizibile in comparatie cu cele ale altor concurenti. Simplitatea, lizibilitatea si faptul ca codul sursa e scurt ajuta mult la viteza de depanarea a bugurilor.

In clasa a 11-a, in seara dinaintea probei citisem intr-o gazeta de info cum se gasesc componentele biconexe intr-un graf neorientat. A doua zi la concurs am primit o problema care cerea determinarea componentelor biconexe intr-un graf neorientat. Nu mai imi aminteam toate detaliile dar, naiv, m-am apucat de lucru. Dupa trei ore nu am reusit sa fac nimic si nu am implementat nici macar solutia evidenta.

Este important sa va antrenati implementarea cum facea Adi pentru a va da seama cum puteti transforma solutiile in cod cat mai simplu, de asemenea orice algoritm netrivial care credeti ca il veti folosi intr-un concurs gen componente biconexe, flux, infasuratoare convexa, subsir crescator de lungime maxima in O(n log n), arbori echilibrati, trebuie sa il implementati de doua sau trei ori pentru a fi sigur ca il faceti corect si rapid cand aveti nevoie de el. Problemele cele mai dificile sunt cand trebuie sa combinati mai multi algoritmi sau structuri de date, iar in concurs se adauga stresul, limitele de timp si nu ar trebui sa mai aveti si probleme de implementare a algoritmilor ce i-ati studiat deja. E bine sa implementati algoritmii pe care ii considerati clasici de mai multe ori si pentru a putea estima mai bine timpul necesar pentru a rezolva o problema. Partea de "time management" e si ea una importanta in concursuri.

Daca vreti sa va antrenati implementarea la problemutze simple puteti incerca cu incredere practice rooms de la topcoder, acolo sunt de la probleme simple la mai grele si aveti acces la codul sursa al unor concurenti care au incercat si ei problemele respective. Puteti vedea o gramada de variante de rezolvare a aceleiasi probleme si va puteti decide care e cea mai buna varianta pentru stilul vostru. La probleme mai grele puteti incerca cu incredere infoarena. Sper ca proiectul in care sharuim sursele si proiectul cu arhiva de invatare va fi folositor in acest sens.

Cu Mircea Pasoi si Silviu Ganceanu vorbeam cand erau ei pe a 10-a respectiv a 12-a aproape in fiecare zi probleme pe messenger si ei lucrau arhiva problemelor de pe acm.sgu.ru , Silviu se si mutase la ICHB si il avea pe Mihai Stroe profesor. Mie mi se pare ca i-a ajutat foarte mult pe amandoi faptul ca discutau si lucrau in paralel.

Silviu imi zicea de trei elevi din clasa a 10-a care lucrasera inainte de ONI toata arhiva de pregatire de la USACO si iesisera pe primele trei locuri la clasa a 10-a la ONI, cred ca primul a fost Valentin Stanciu, daca tin bine minte. Lui Silviu ii placea cum cei trei elevi ai lui se ambitionasera unul de la altul si au evoluat mult.

Nu stiu daca ati urmarit anul trecut evolutia clasamentului arhivei de probleme, dar eu vedeam cum wefgef, gcosmin si btataroiu se luptau intre ei si in fiecare zi isi mareau numarul de probleme rezolvate din arhiva.

Este foarte bine sa ai un prieten sau un grup de prieteni pasionati si ei de concursuri. Concurenta te ambitioneaza iar comunicarea cu alti pasionati de algoritmica te ajuta sa aflii tot felul de trucuri mai repede. In general profesorul de la clasa e depasit de nivelul problemelor de olimpiada, daca nu l-ai depasit inca ar trebui sa iti faci probleme. Rolul profesorului este doar sa zgandare pasiunea in tine la inceput, dupa aia esti pe cont propriu si de aceea comunicarea cu un grup de pasionati e vitala. Pe forumul infoarena sau pe cel de la topcoder va puteti face prieteni pe care ii veti pastra si mai tarziu in viata.

Ar ajuta daca gasiti pe un fost olimpic de la care sa luati meditatii, in Bucuresti cel mai simplu e sa mergi la ICHB, in Iasi sau Suceava gasiti relativ usor fosti olimpici puternici, in Ardeal in schimb mai rar, probabil ati putea vorbi cu Patcas Csaba (coleg cu mine de an) care pregateste echipa Babesului pentru ACM si pe cativa baieti din Cluj pentru ONI. Cineva cu experienta in concursuri va poate ghida inspre anumite tipuri de probleme, spre siteuri sau carti utile.

Pregatirea psihica si controlarea stresului in timpul concursului sunt si ele importante. Mircea a preluat o idee de la echipa de ACM a universitatii Waterloo, si inainte de un concurs important face o pauza de programare de o saptamana ca sa se linisteasca. Abordarea asta s-ar putea sa nu fie buna pentru cei ce "ingrasa porcu in ajun". Puteti sa incercati sa aflati din timp care sunt conditiile in care trebuie sa participati in concurs si sa va antrenati in acele conditii pentru a avea un mediu familiar cand ajungeti la fata locului.

Alta modalitate de pregatire e participarea la cat mai multe concursuri pe internet. Pentru mine Bursele Agora a insemnat destul de mult si cred ca nu numai pentru mine, poate ne zice si Mugurel ceva aici. De asemenea cand organizam concursul "Algoritmus" impreuna cu Ciprian Cana, am vazut un nume nou prin clasamente, Radu Marin. Facea destul de bine pe problemele care eu cu Cipri ne chinuisem sa fie destul de grele. I-am zis lui Mircea la misto ca va avea un concurent puternic anul ala. Predictia s-a transformat in realitate si Radu a luat medalie de bronz anul respectiv la IOI.

Sumarizez putin elementele importante ce ajuta la obtinerea unor rezultate bune la olimpiade :

  • munca individuala ghidata de pasiune
  • antrenarea modalitatii de codare a algoritmilor
  • gasirea unui grup de prieteni pasionati
  • gasirea unui mentor cu experienta
  • participarea la cat mai multe concursuri online

Cu proiectul infoarena incercam sa va ajutam sa atingeti performanta in informatica cat mai usor. Avem o arhiva cu un numar impresionant de probleme frumoase, o sectiune de articole interesante, o lista de trucuri care ar trebui stiuta pentru concursuri si doua proiecte pe care le gasiti aici si aici care vor mari si mai mult utilitatea siteului.

Va astept cu comentarii! Sunt curios si de stilul vostru de antrenament!

Daca mai vreti si alte sfaturi puteti citi ghidul pentru concursuri al lui Mircea, sau articolul lui Mugurel.

Categorii:
remote content