**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 <tex>O(nlg^2 n)</tex>, si s-au prins cativa oameni. Apoi m-am mai gandit la problema, am gasit o rezolvare in <tex>O(n lg n)</tex> 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 <tex>O(n)</tex>, care l-a publicat la European Symposium on Algorithms. Bineinteles ca asta m-a motivat, si i-am imbunatatit algoritmul la <tex>O(n^{2/3})</tex> -- deci recordul revine la Romania :)

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 <tex>O(n\ lg^2 n)</tex>, si s-au prins cativa oameni. Apoi m-am mai gandit la problema, am gasit o rezolvare in <tex>O(n\ lg n)</tex> 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 <tex>O(n^{3/4})</tex>, care l-a publicat la European Symposium on Algorithms. Bineinteles ca asta m-a motivat, si i-am imbunatatit algoritmul la <tex>O(n^{2/3})</tex> -- 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.

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

Cred ca toata lumea stie ca se face in <tex>O(lg n)</tex> cu binary trees, si ideea e super-utila in multe probleme.

Cred ca toata lumea stie ca se face in <tex>O(lg\ n)</tex> 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 <tex>O(lg  n)</tex> 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.

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 <tex>O(lg\ n)</tex> 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 :)
h2. _(big)A doua parte din interviu va fi publicata in curand._

'Comentarii':forum/index.php?topic=2164.0

2164