Blog infoarena

O problema misto

Cosmin
Cosmin Negruseri
12 octombrie 2007

Dumitru Daniliuc mi-a zis o problema simpatica de pe vremea cand se antrena in liceu pentru olimpiadele de matematica, pe care acum vreau sa v-o zic si voua.

Problema suna asa: Se da o multime S, de puncte in plan. Aria ocupata de puncte e strict mai mica decat unu. Se cere sa se gaseasca un sistem de coordonate astfel ca punctele de coordonate intregi din acest sistem de coordonate sa nu se suprapuna peste nici un punct din multimea S.

Va rog, daca aveti solutii, sa nu le publicati pe forum ci sa mi le trimiteti ca mesaj privat. In doua zile voi publica o solutie si numele celor ce au rezolvat corect problema.

Update: Multimea S poate contine o infinitate de puncte. De exemplu S e formata din cateva pete si o dreapta. Aria dreptei e 0 si suma ariilor petelor e mai mica ca 1.

Update2: Pentru a nu complica problema si definitia a ce inseamna arie, impunem restrictia ca multimea S este formata din un numar finit de pete, fiecare avand o arie. Deci S nu va contine drepte, spirale sau mai stiu eu ce.

Update3: Sistemul de coordonate trebuie sa fie ortonormat si sa pastreze dimensiunile initiale.

 Comentarii (1)

Categorii: probleme

Three Beautiful Quicksorts

Cosmin
Cosmin Negruseri
11 octombrie 2007

Eu stiam de Jon Bentley pentru ca este autorul cartii Programming Pearls, o carte scrisa foarte bine si care se citeste foarte usor, spre deosebire de Introducere in algoritmi. Ea contine multe trucuri dragute de algoritmica si poate reprezenta o introducere foarte buna pentru cei ce vor sa invete algoritmica. Singura problema e ca nu este tradusa in romana.

Astfel am fost curios cand Jon a avut o prezentare, numita Three Beautiful Quicksorts, la Google acum doua luni. In talk apar chestii interesante cum ar fi optimizarea metodei qsort() din C (si ca paranteza Joshua Bloch mentioneaza ca implementarea din Java a functiei sort() urmareste indeaproape ideile din talk) sau o imagine in care vedem ca variante diferite ale quick sortului nu au graficul similar cu cel al functiei n\ log\ n, ci se vad trei bucati care se comporta diferit, ele corespunzand nivelelor de cache si memoriei. Sperand ca v-am deschis putin apetitul, puteti sa vizionati aici prezentarea:

 Comentarii (7)

Categorii: algoritmica video

infoarea si-a tras blog

Cosmin
Cosmin Negruseri
10 octombrie 2007

Ultimul feature adaugat la site este un blog. Va invitam sa il folositi si speram sa fie interesant si util.

 Comentarii ()

Categorii: stiri

Interviu cu Mihai Patrascu - partea intai

Cosmin
Cosmin Negruseri
09 octombrie 2007

Am avut ocazia sa il reintalnesc acum vreo doua luni pe Mihai Patrascu dupa ce ultima data cand il vazusem a fost la Olimpiada Nationala de Informatica din Bacau in 2001. Era venit in Bay Area la un internship la centrul de cercetare IBM Almaden. I-am propus atunci sa facem un interviu pentru viitorul blog de pe infoarena.

Mihai Patrascu are printre cele mai bune rezultate la olimpiadele internationale la informatica dintre romani. A luat premiul I la Olimpiada nationala de informatica din clasa a 4a (concurand la clasa a 5a) pana intr-a 12a. La olimpiada internationala la de informatica a luat doua medalii de aur si una de argint (in 2001 a fost locul doi la internationala). La Concursul Europei Centrale de Informatica a luat un aur si un argint, iar la Balcaniada de informatica un argint. In 2005 a luat premiul Outstanding Male Undergraduate Award pe Statele Unite si Canada. Are chiar si o pagina pe wikipedia

Interviul va fi impartit in doua parti. In aceasta parte Mihai discuta despre MIT, despre cercetare si despre olimpiade:

Cum ai inceput cu informatica?

In clasa a 2a, am decis sa ma duc la Palatul Copiilor si sa studiez electronica. Din pacate, cursul de electronica se umpluse, dar mai erau locuri la cursul de programare...

Ai avut pe cineva care te-a ghidat? Un mentor, o persoana de la care ai invatat?

Nu, practic niciodata. La mai sus-mentionatul curs de programare am invatat sa programez in Basic timp de cateva luni, si am fost captivat. Dar cu asta s-au sfarsit cursurile de programare care le-am luat. Am invatat Pascal dintr-o carte intr-a 4a, C din alta carte (in engleza) intr-a 6a, apoi pentru pregatire mai serioasa la olimpiada am citit GInfo, probleme de pe la concursuri, Knuth si CLR. In liceu am fost la profilul de mate-fizica.

Prin facultate a continuat cam la fel. Dupa 1 an la MIT m-am mutat in departamentul de matematica (ca protest pentru departamentul de CS care nu ma lasa in pace), asa ca n-am luat nici pana azi nici un curs de programare. Am luat multe cursuri de algoritmi, evident. Dar n-au avut niciodata legatura cu cercetarea mea :) Probabil mi-am ales domeniul de lucru dupa aceleasi criterii: un domeniu unde nu se facuse progres de peste 15 ani, si ca atare nu mai existau nici profi nici cursuri predate in mod curent...

De ce MIT si nu alte universitati din state sau din Romania?

Am facut un an la poli in Craiova, dar era o atmosfera trista. Practic lumea nu era acolo decat ca sa ia o diploma, si, partea cu adevarat trista, diploma aia nici nu prea conta...

In State, doar MIT-ul m-a acceptat :) Simplu.

Cum a fost procesul de admitere? Cat de mult conteaza o medalie la olimpiada internationala?

Pana acum cativa ani, la MIT studentii internationali erau practic 100% cu medalii la diverse discipline, si clar asta era criteriul de baza. Multe alte universitati (gen Harvard si restul de Ivy League) cautau oameni cu un profil diferit, care sa ajunga politicieni, manageri etc. In perioada aia era faimoasa bariera culturala intre studentii de la MIT si cei de la Harvard.

In zilele noastre a aparut o oarecare convergenta. Internationalii de la MIT sunt mult mai "normali" si doar putini mai au medalii, in timp ce celelalte universitati au inceput sa aprecieze mai mult oamenii cu medalii.

La MIT au fost multe proteste (spre exemplu, Leiserson s-a plans mult) si speram sa revenim la admisia mai elitista (decanul de admisii a fost concediat recent, pe alte motive, si anul asta vom vedea ce face noul decan).

Cum e viata unui roman la MIT, sunt romanii sau strainii in general priviti ca outsideri?

La MIT e foarte greu sa gasesti americani... Toti "americanii" sunt de fapt la prima generatie, fiind imigrati recent impreuna cu parintii. Asta se datoreaza educatiei la nivel de liceu in State, care orienteaza lumea spre stiinte sociale, avocatura etc. Persoanele care stiu teorema lui Pitagora la liceu sunt "buni la matematica", iar cei care Doamne-fereste iau un curs de trigonometrie sunt "geeks".

La toate capitolele, MIT-ul este mai mult decat deschis... Majoritatea oamenilor sunt foarte inteligenti, si exista o toleranta foarte mare (dupa principiul ca oamenillor destepti li se permite). Cei mai ciudati oameni i-am vazut la MIT.

Cursuri preferate in facultate?

Advanced Data Structures (care l-am si predat un an), Advanced Algorithms, Randomized Algorithms, Geometric Computing, Computer Architecture, Microeconomics, Syntax (in lingvistica, nu programare :p)

De ce cercetare si nu programare?

Cred ca mentalitatea de om de stiinta ma caracterizeaza. Imi doresc foarte mult sa aflu raspunsuri, nu numai sa fac ceva care sa mearga. Ca cercetator pot sa las ceva in urma, ceva cunostiinte noi pentru omenire. Ca programator m-as simti mult mai egoist -- fac ceva ca sa castig eu niste bani.

In plus, programarea mi s-a parut intotdeauna o unealta la ce facem noi, nu un scop in sine. Principalul este sa te gandesti, sa "te prinzi", si apoi poti sa stai cuminte si sa programezi ideea. Dar esenta e ideea. Un programator bun e unul care gandeste bine, nu unul care tasteaza repede.

Te-au influentat in vreun fel olimpiadele din liceu?

Foarte mult. Motivul evident e ca mi-au oferit o deschidere -- am vazut locuri noi, oameni noi, probleme mai grele, si apoi din cauza lor am ajuns la MIT. Motivul mai subtil dar mai important e ca olimpiadele au fost locul ideal pentru dezvoltarea spiritului competitiv. In Romania este foarte usor sa ajungi blazat si mediocru. La olimpiade descoperi ca poti sa castigi si poti sa pierzi, iar agonia si extazul sunt la un pas distanta. Odata ce prinzi gustul luptei, iti vei dori mereu sa faci mai mult in viata, si asta te face un om mai reusit.

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

Cum te antrenai in timpul liceului? Studiai din carti? Rezolvai probleme de pe siteuri cu evaluatoare automate? Discutai probleme cu colegii?

Pe vremea mea nu prea existau siteuri cu evaluare automata. N-am folosit niciodata unul, desi cred ca sunt utile.

Eu in principal citeam carti, GInfo, etc si ma gandeam la probleme. Discutam destul de mult cu ceilalti concurenti, de la care invatam idei interesante. Asta se intampla la lot, pentru ca in Craiova nu era nimeni cu care sa pot sa discut.

Ai vreun algoritm/structura de date preferata?

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

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

A doua parte din interviu va fi publicata in curand.

 Comentarii (3)

Categorii: interviu

Primul post

Cosmin
Cosmin Negruseri
08 octombrie 2007

 Salutare, sunt Cosmin Negruseri si sunt bucuros sa va anunt ca infoarena si-a tras blog.

 Vorbeam cu Cristi pe la inceputul verii de nevoia unui blog pe inforena. Am ajuns imediat la concluzia ca trebuie sa fie un blog nativ pe infrastructura infoarena si nu unul pe care doar sa il integram. Pe de o parte nu ar trebui sa reinventam roata, dar pe de alta parte sunt multe feature-uri ale siteului de care vrem sa ne folosim.

 Am discutat si cu Mircea care era interesat de partea de programare, dar a avut timp de ea doar dupa ce si-a terminat internshipul pe vara in Redmond. A terminat prima varianta vinerea asta, dar a pus noul feature pe site doar dupa concursul de duminica. Inca mai e de lucru pe partea tehnica, dar e mai bine sa incepem mai repede decat mai tarziu.

Bine ati venit pe blogul infoarena, speram sa plecati de pe el putin mai destepti de fiecare data.

 Comentarii (6)

Autumn Warm-Up 2007, Runda 1

wickedman
Cristian Strat
09 septembrie 2007

Vacanta de vara a ajuns la sfarsit. E timpul sa te revezi cu vechii tai prieteni de la concursurile de info si sa le demonstrezi ca ai ramas in forma. :)
Te invitam sa participi la runda 1 a concursului Autumn Warm Up cu probleme propuse de utilizatori infoarena.

Runda 1 se desfasoara Marti, 11 septembrie 2007, orele 1000 - 1500.

Autumn Warm Up, Runda 1

 Comentarii ()

Categorii: stiri

Summer Challenge 2007 s-a incheiat

wickedman
Cristian Strat
12 august 2007

Concursul online Summer Challenge organizat de infoarena s-a incheiat.
Felicitari participantilor si, mai ales, castigatorilor!

Clasamentul cumulat pe cele 3 runde
Pagina concursului

Speram ca a fost o experienta utila pentru lotul Romaniei la IOI 2007 (care incepe peste numai 3 zile!).
Va tinem pumnii!

 Comentarii ()

Categorii: stiri

Summer Challenge 2007, Rundele 2 si 3

wickedman
Cristian Strat
09 august 2007

Rundele 2 si 3 ale concursului Summer Challenge se vor desfasura la 2 zile distanta. Mai exact:

  • Runda 2: Vineri, 10 august 2007, intre orele 1000 - 1500
  • Runda 3: Duminica, 12 august 2007, intre orele 1000 - 1300

Ai ocazia sa concurezi cu lotul Romaniei la IOI 2007!
Succes!

Pagina concursului

 Comentarii ()

Categorii: stiri

Summer Challenge 2007, Runda 1

wickedman
Cristian Strat
30 iulie 2007

Te invitam sa participi la seria de concursuri Summer Challenge 2007. Vom organiza 3 runde online, de cate 5h fiecare, cu probleme de dificultate variata.

Summer Challenge este o ocazie buna de antrenament pentru tine (daca nu esti deja la mare :) dar si un ultim test pentru delegatia
Romaniei la Olimpiada Internationala de Informatica 2007 (Croatia).

Ai ocazia sa concurezi cu lotul Romaniei la IOI 2007!

Pagina concursului

 Comentarii ()

Categorii: stiri

Finala preONI 2007

wickedman
Cristian Strat
22 iunie 2007

Finala concursului preONI 2007 se desfasoara in perioada 24 - 26 iunie 2007 la Liceul international de Informatica din Bucuresti.

Se califica in runda finala primii 10 clasati de la fiecare grupa de varsta, in urma celor 4 runde online. Se asigura cazarea si masa integral. Castigatorii vor primi premii in bani.
Concurentii care nu s-au calificat pot participa online pe site-ul infoarena.

Multumim sponsorilor nostri!

→ Vezi pagina dedicata rundei finale

 Comentarii ()

Categorii: stiri
Vezi pagina: 12345... 293031323334 353637383940 (394 rezultate)