Pot sa va povestesc despre o problema la un lot (Petrol din 2003); era despre un graf cu N noduri si M muchii si avea o solutie evidenta care folosea N BF-uri (timp N*M). Solutia care se cerea era in M*log N daca imi amintesc bine, iar solutia in N*M ar fi trebuit sa ia in jur de 30-40 de puncte. Eu am reusit sa iau 90 de puncte cu aceasta solutie. Cum? O singura linie conta - cea care definea bucla de expandare a vecinilor unui nod. Trebuia sa optimizez cat mai mult enumerarea vecinilor unui nod. Ideea a fost sa citesc mai intai intrarea doar pentru a numara vecinii fiecarui nod, sa aloc cate un vector exact de marimea necesara pentru fiecare nod, apoi sa citesc din nou intrarea si sa completez vectorii. Astfel, efortul de a enumera toti vecinii in unui nod in parcurgere este minim; vecinii sunt unul langa altul in memorie si cache-ul este folosit foarte bine. Mai era o singura decizie de luat - cum sa stii cand sa te opresti in enumerarea vecinilor; am testat in timpul concursului tot felu de metode si cea mai rapida a fost sa adaug un numar special (0) la sfarsitul fiecarui vector. Sigur, ar fi fost mai bine sa fiu mai destept si sa ma prind de solutia corecta, dar care ar mai fi fost spectacolul? :)

*Stiu ca pentru un an erai inscris la Universitatea Bucuresti si la Universitatea Politehnica, iar apoi ai plecat la MIT. Poti sa ne povestesti mai mult? Ce te-a facut sa alegi MIT?*

Stiu ca pentru un an erai inscris la Universitatea Bucuresti si la Universitatea Politehnica, iar apoi ai plecat la MIT. Poti sa ne povestesti mai mult? Ce te-a facut sa alegi MIT?

Eram deja decis sa aplic la MIT inainte sa incep facultatea in Romania. Motivul in principal a fost ca in facultatile din Romania nu prea se invata mare lucru (la informatica). In nici un caz nu cat se invata la una ca MIT. Simteam ca am totusi un talent deosebit si ca trebuie sa il folosesc/extind in continuare (ceea ce clar nu se intampla la facultate in Romania). Nu eram chitit sa plec din tara; faptul ca trebuia sa plec era un dezavantaj. Am aplicat doar la MIT, in ideea ca daca plec din tara, macar sa merite. Plus ca aici aveam si cele mai mari sanse sa fiu acceptat, pentru ca aici conteaza (sau contau..) cel mai mult medaliile.