*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.

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.

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?*

*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.

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?*

*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.

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?*

2502