Blog infoarena

Putina istorie ACM ICPC SEERC

Cosmin
Cosmin Negruseri
29 octombrie 2007

Alt titlu la care m-am gandit pentru acest post este "In cate moduri poti sa propui niste probleme busite".
In fiecare an sunt probleme cu problemele de la regionala ACM la care participa studentii romani, iar anul asta s-a vazut mai clar din rezultate si nu din studierea testelor. Va ziceam intr-un post anterior ca un set de probleme bune este unul in care fiecare problema e rezolvata de cel putin o echipa, dar nici o echipa nu rezolva toate problemele. Anul asta sapte echipe au rezolvat toate problemele, una reusind sa le rezolve in doua ore si patru minute, cand timpul total al concursului e de cinci ore.

Putina istorie a problemelor bushite de-a lungul timpului:

In 2002 problema Sly Number implica rezolvarea unui sistem de ecuatii liniare modulare. Un concurent a testat cu backtracking testele comisiei si nici unul nu ii dadea rezultatul asteptat. In timpul concursului, o echipa a rezolvat problema respectiva, facand probabil aceiasi greseala ca si solutia comisiei.

In 2004 la problema City Game, se cerea determinarea dreptunghiului de arie maxima ce contine doar caracterul F pe o matrice ce contine caractere de F si R. Intre teste era unul care specifica o matrice de 100 de randuri si 100 de coloane, dar avea doar 98 de randuri. Daca aveai norocul ca partea de citire din program sa fie implementata ca si cea a comisieri, puteai rezolva problema ... Multe echipe s-au blocat in problema asta clasica, incercand sa isi gaseasca bugul de implementare care era de fapt in testele comisiei. De asemenea in acelasi an s-a propus problema Alibaba despre care am dubii mari ca ar exista vreo solutie de complexitate mai buna decat O(n^2) desi limita de timp din concurs facea ca o asemenea solutie sa obtina mesajul Time Limit Exceeded. Testele la Alibaba sunt foarte misto, cateva teste mici ce merg cu programare dinamica in O(n^2) si doua teste mari la care merge lejer greedy.

In 2005 s-a propus rezolvarea unui puzzle Sudoku, dar toate testele puteau fi rezolvate punand o cifra in locuri fortate, pentru nici un test nu trebuia facut backtracking. Astfel echipele care fac solutia buna au un dezavantaj fata de echipele care nu isi dau seama ca exista cazuri pe care solutia lor nu merge. Problema Adventurous Driving avea ca limita in enunt n <= 100 iar in teste era un n = 1000. Autorul problemei era mandru de ea, pentru ca doar o echipa a rezolvat-o in timpul concursului.

In 2006 problema Shortest Pair of Paths cerea determinarea a doua drumuri minime disjuncte de la sursa la destinatie. Problema este clasica si se rezolva cu flux maxim de cost minim, dar testele au facut ca o solutie ce gaseste de doua ori un drum folosind algoritmul lui Dijkstra sa mearga. Din nou echipele care au stiut ca problema e mai complicata au pierdut timp implementand solutia mai grea. Alta problema bushita a fost Sherloc Holmes care era un knapsack 2d, dar nu prea incapea in memorie pentru ca n si m erau 10000. Dupa concurs s-a vazut ca testele contineau n si m-ul maxim 300.

Acestea nu sunt singurele exemple.

Sa organizezi un concurs cu multe probleme, la un nivel inalt este foarte greu. Putine regionale reusesc asta. Printre ele sunt ECNA, o regionala din Canada, NEERC, una din Rusia, CEPC, regionala Europei Centrale. Acestea au probleme de calitate, de dificultate mare, cu explicatii de solutii scrise, cu o echipa de organizatori care contin studenti care au fost concurenti. Nu e de mirare ca aceste regionale au aproape in fiecare an o echipa in primele cinci din lume.

Si la TopCoder se intampla ca un concurs sa fie bushit, desi ei isi bazeaza afacerea lor pe asta. Dar pentru a evita greselile, care, avand in vedere ca organizeaza mai mult de un concurs pe saptamana, ar fi normal sa se intample, acestia au o metodologie foarte bine pusa la punct. Fiecare problema este rezolvata de inca trei oameni, altii decat autorul, care isi dau cu parerea atat asupra problemei cat si asupra testelor alese. Un al patrulea om are grija ca textul sa nu aiba ambiguitati. Autorul trebuie sa faca enuntul, testele si un validator pentru teste.

Concursul ACM este un eveniment important care se desfasoara o data pe an, si el ar trebui organizat cu grija, astfel incat concurentii sa nu plece cu impresia ca au fost luati in bataie de joc. Ce trebuie facut pentru corectarea problemelor din trecut ar fi intinerirea comisiei stiintifice, scrierea unui validator de teste, si implementarea a mai multor solutii pentru fiecare problema. Nu pare foarte greu, dar se pare ca nu se invata nimic din esecurile anterioare.

Puteti citi si postul lui Florin Manea, antrenor al echipelor universitatii Bucuresti, despre regionala ACM aici

 Comentarii (6)

Categorii: concursuri

Demouri tari de la SIGGRAPH

Cosmin
Cosmin Negruseri
28 octombrie 2007

Pol Catalin mi-a aratat un demo de la SIGGRAPH 2007 . Demonstratia este impresionanta, si ne arata cum, cu un algoritm simplu, putem obtine o calitate foarte buna cand redimensionam imagini. Algoritmul functioneaza bine chiar daca imaginea finala e mai mare decat cea initiala.

M-am uitat pe la alte paperuri si demouri de la SIGGRAPH si am dat peste plasma pong, un joculet foarte misto care mi-a adus aminte de vremurile din liceu cand pierdeam ore in sir implementand diversi algoritmi ce generau plasme sau focuri.

Puteti vedea mai jos cele doua demouri, primul e de cinci minute, iar al doilea de doua. Enjoy!

Update Gasiti aici lucrarea care descrie algoritmul folosit.

 Comentarii (2)

Categorii: video

Interviu cu Catalin Francu - partea intai

Cosmin
Cosmin Negruseri
26 octombrie 2007

Odata cu angajarea mea la Google am avut ocazia sa cunosc multi fosti olimpici, pe care ii stiam doar dupa nume, vazandu-i in Ginfo sau in listele cu premii la diverse concursuri. Unul dintre acesti olimpici este Catalin Francu , caruia, la o cina in San Francisco, i-am smuls promisiunea ca va raspunde la cateva intrebari pentru ce avea sa fie blogul infoarena. Acum va voi prezenta prima parte a interviului, dupa o scurta prezentare a lui Catalin.
Catalin este cunoscut in lumea celor pasionati de informatica prin cartea "Psihologia concursurilor de programare", o carte plina de probleme frumoase si deschizatoare de drumuri la vremea ei, si prin "lista lu' Francu", o lista de discutii pe email, unde cativa dintre cei ce au ajuns apoi olimpici internationali la informatica ai Romaniei rezolvau si discutau probleme. Iar in lumea lingvistilor este cunoscut prin proiectul dexonline . Acesta este un wiki (inovator pentru 2001, cand Catalin a inceput proiectul) care contine intreg Dictionarul Explicativ al limbii romane si alte dictionare. In timpul liceului, Catalin a luat o medalie de argint la olimpiada internationala de informatica, iar in timpul facultatii s-a clasat pe locul 7 la etapa finala a concursului ACM ICPC cu echipa reprezentanta a MIT. De asemenea a facut parte din comisia stiintifica a Olimpiadei de Informatica a Europei Centrale din 2000 care s-a desfasurat la Cluj. Dupa terminarea facultatii Catalin a lucrat patru ani ca programator la Google inc.

In aceasta prima parte a interviului, Cata ne vorbeste de olimpiade, de cartea "Psihologia concursurilor de programare" si despre "Lista lu' Francu".

Cum ai inceput cu informatica?

Parintii mei au facut parte din primele generatii de la ICI, ceea ce si-a pus amprenta asupra mea si a fratelui meu. Prin clasa a 4-a am vazut prima oara un calculator ZX Spectrum. Mi-au placut mult jocurile, iar cu timpul am inceput sa ma intreb si cum sunt facute si daca as putea face si eu ceva asemanator. in clasa a 8-a, cand s-a pus problema sa-mi aleg un liceu, deja nu mai aveam dubii.

Erau alte discipline de care erai interesat in timpul scolii?

Da... in dictionar, langa definitia pentru "tocilar" este poza mea :) Am invatat multe prostii care acum imi dau seama ca au fost pierdere de vreme, dar unele materii chiar mi-au placut. De felul meu am fost atras de matematica si fizica. Muzica si biologia erau frumoase, dar erau predate foarte prost.

Cum si ce lucrai pentru olimpiade?

Generatia mea (promotia 1996) n-a avut foarte multe resurse la indemana. Circulau colectii de probleme din anii trecuti, dar comunicarea intre olimpici era de baza, pentru ca unul afla de un algoritm interesant si il raspandea. Manualele domnului profesor Sorin Tudor au fost multa vreme "Biblia" mea; de altfel consider ca la vremea lor au fost pur si simplu avangardiste (si nu stiu cati profesori se pricepeau sa predea notiunile pe care le contineau acele manuale).

Ce persoane au avut o influenta in formarea ta?

Parintii si fratele meu Cristi, in primul rand. Mi-amintesc ca eram prin clasa a 2-a, iar Cristi tocmai invata despre scheme logice si se chinuia sa mi le explice si mie. Mie imi placeau romburile cel mai mult, dar altceva n-am inteles. :) La liceu am avut multi profesori buni de informatica, dar in special doamna Rodica Cherciu si domnul Sorin Tudor. Este adevarat ca un profesor poate sa atraga sau sa sperie un elev, dupa cum isi preda materia. Nu in ultimul rand, la loturile de informatica au fost intotdeauna oameni deosebiti (elevi si profesori). in lumea olimpiadelor mi-am cunoscut multi dintre prietenii de astazi.

Mai tii minte probleme frumoase de la olimpiada?

Mi-a placut intotdeauna, pentru simplitatea ei, problema acoperirii tablei cu L-triominouri (Se da o tabla cu dimensiunea de 2^n \ast 2^n din care s-a eliminat un patrat. Se cere ca restul sa se acopere cu L-triominouri). Am pus de multe ori aceasta intrebare la interviuri la Google si putini au stiut sa o rezolve in 10-15 minute. Problema care m-a determinat sa ma apuc serios de studiul algoritmilor este "Se da un arbore neorientat. in fiecare nod se afla un bec. Initial toate becurile sunt stinse. Prin atingerea unui bec, el si toate becurile vecine isi schimba starea. Sa se identifice o ordine de atingere a becurilor astfel incat in final toate becurile sa fie aprinse."

Ce structura de date iti place cel mai mult?

E greu de raspuns la intrebarea asta. E mai important sa stii la ce e buna o structura de date decat sa-ti placa. De exemplu, am cunoscut oameni care nu suporta listele inlantuite si folosesc intotdeauna vectori, chiar si atunci cand au de facut insertii sau concatenari.
Cand folosesti Java si ambele structuri sunt deja implementate, si trebuie numai sa stii de ce tip sa declari variabila, aceasta reticenta este foarte daunatoare.

Pentru simplitatea implementarii, imi plac mult seturile disjuncte cu compresia caii (folosite, de exemplu, in algoritmul lui Kruskal pentru aflarea arborelui partial de cost minim). Analiza teoretica a complexitatii este foarte subtila.

Sunt olimpiadele folositoare?

Este iarba verde? :)

Cum e de partea cealalta a baricadei in concursurile de informatica, cand participi ca organizator?

Avem mai putin timp liber, pentru ca mereu e cate ceva de facut, dar satisfactiile si placerea sunt la fel de mari. Daca vreun student sau un profesor are un ceas liber, prefera sa implementeze o solutie pentru vreuna din probleme. Nu numai pentru ca e bine sa avem mai multe solutii pentru verificare, ci si din acea dorinta, care ne impinge pe toti la concursuri, de a ne masura fortele cu o problema noua.

Cum ti-a venit idea sa scrii "Psihologia Concursurilor de Programare"?

Domnul profesor Sorin Tudor a venit cu ideea sa-mi impartasesc cateva din experientele de la olimpiade. Pentru ca de aici nu aveau cum sa rezulte mai mult de 10-20 de pagini, m-am gandit sa adaug cateva structuri de date pe care le-am folosit destul de frecvent la concursuri si care nu erau discutate in manualele de liceu.

Cum ai ales structura cartii si problemele?

M-am gandit la cateva structuri de date, implementabile in timp de concurs, despre care elevii nu prea aveau de unde citi. Problemele alese fie exemplifica folosirea acestor tipuri de date, fie subliniaza unele alegeri care tin de psihologia fiecarui concurent. De exemplu, am gasit un algoritm greedy care merge pe toate exemplele mele, dar nu il pot demonstra matematic. il implementez sau nu? Sau am gasit un algoritm lent cu care stiu ca nu o sa iau punctaj maxim. il implementez sau caut altul mai bun?

Cat timp ti-a luat sa scrii cartea si cat de usor a fost sa o publici?

Cateva luni, dintr-o vacanta de vara pana prin noiembrie. Publicarea nu a fost o problema, deoarece ideea cartii a venit tocmai de la Sorin Tudor, care avea propria editura. Mai problematica a fost tiparirea, pentru ca la migrarea pe alt calculator si pe alta imprimanta, se dadea peste cap toata paginarea (pe vremea aceea nu auzisem de LaTeX, de PDF, sau in general de altceva in afara de Microsoft Word).

A meritat efortul?

Fara nici un dubiu! A fost una din primele mele slujbe platite, am castigat un ban facand ceea ce imi placea si a rezultat ceva palpabil si -- din cate aud -- folositor.

De ce ai inceput lista lui Francu?

In 1996 am inceput (sau mai degraba am continuat, de unde l-a lasat fratele meu) un mic cerc de informatica. Cu timpul am inceput sa corespondam si prin email. Emailurile au capatat valoare in sine si am creat o lista de discutii dedicata.

Cum a evoluat lista si discutiile de pe lista de-a lungul timpului?

La inceput, trimiteam probleme, asteptam o saptamana si corectam solutiile trimise. Perioada cea mai buna a listei, zic eu, a fost cand am introdus o notiune de "coeficient" (se numea DFCC si se masura in Dexteri). Dincolo de copilaria numelui, m-am straduit sa nascocesc un coeficient care scadea incet cu timpul, pentru a-i incuraja pe abonati sa trimita solutii la fiecare etapa.

De ce a murit?

Plecarea la MIT a fost "inceputul sfarsitului". Aveam mai putin timp liber si o vreme s-a ocupat Cristi Cadar de lista (de altfel, el a propus aproape jumatate din numarul problemelor). Ocazional au mai contribuit si alti "ilustri" ca Rodica Pintea, Valentin Gheorghita, Mihai Badoiu, Irina Dumitrascu, Bogdan Dumitru, Alex Susu...

Un alt motiv a fost ca elevii care au participat initial la cercul de informatica au absolvit liceul, ceea ce mi-a redus mie motivatia de preparator. :) si nu in ultimul rand a fost aparitia altor site-uri, romanesti si internationale, dedicate problemelor de programare, cu evaluatoare automate etc. Ma bucur mult ca infoarena.ro incorporeaza majoritatea problemelor propuse pe lista, pentru ca ne-am gandit mult la ele si ar fi fost pacat sa se piarda.

A doua parte a interviului va fi publicata in curand.

In contextul interviului cu Cata (cum ii zic prietenii), infoarena are doua proiecte unde este nevoie de ajutorul vostru. Unul este transcrierea cartii "Psihologia concursurilor de programare" in format textile. Altul ar fi cel de transformare a problemelor din Lista lu' Francu in formatul infoarena si de adaugarea lor in arhiva (au mai ramas vreo 10 probleme de adaugat). Aveti mai multe detalii aici si aici .

In poza de mai sus apar Cristi Strat , 'maestru' Catalin, eu , iar cenzurati sunt doi ilustrii necunoscuti :), se dau puncte de karma pe forum pentru cine ii identifica pe cei doi.

 Comentarii (8)

Categorii: interviu

TED - talks

Cosmin
Cosmin Negruseri
24 octombrie 2007

TED sunt niste conferinte tinute anual cu o serie de discursuri tinute de diversi oameni destepti despre domeniul lor, care sunt deschizatoare de ochi. In 2006 mi-a placut mult talkul despre economie a lui Hans Rosling. El avea o firma cu un produs ce facea niste grafice interactive, animate pe axa timpului. Dupa ce l-a vazut in actiune, Google i-a cumparat firma :). Anul acesta, Hans a mai avut un talk care a fost la fel de interesant, cu un final neasteptat. Fiecare talk are 20 de minute, daca nu faceti ceva important acum, urmariti-le ca merita:

Myths About the Developing World (2006)

Watch the end of poverty (2007)

 Comentarii (4)

Categorii: video

De ce sa participi la ACM ICPC

Cosmin
Cosmin Negruseri
22 octombrie 2007

Am incercat sa gasesc cateva motive pentru un student la informatica, care nu a avut contact cu olimpiadele in liceu, sa participe la concursurile ACM in timpul facultatii. Ce ar fi folositor pentru el in dorinta de a deveni un programator mai bun? Am ajuns la urmatoarea lista:

  • ca sa mai scrii o linie in CV
  • ca sa iti dai seama ca programezi foarte incet
  • ca sa vezi ce greu e sa lucrezi in echipa in conditii extreme
  • ca sa programezi ceva interesant
  • ca sa intelegi algoritmica si structurile de date la un nivel ce trece de superficialitate
  • ca sa cunosti alti oameni cu pasiune mare pentru programare
  • ca sa ti se para banale intrebarile de coding de la interviurile microsoft sau google
  • ca sa inveti chestii mai importante decat ultima tehnologie la moda, cum ar fi identificarea rapida a bugurilor, claritatea codului, proiectarea programului inainte de implementare sau metode de optimizare a timpului si memoriei
  • ca sa rezolvi o problema complet a carei solutie merge pe toate cazurile
  • ca sa inveti ca nu orice problema se rezolva cu "metoda backtracking"
  • ca sa poti scrie un post pe blog

Ce motive aveti voi pentru a participa sau pentru a nu participa la acest concurs?

 Comentarii (15)

Categorii: concursuri

Alta problema misto - solutie

Cosmin
Cosmin Negruseri
22 octombrie 2007

Problema cu lanternele a fost rezolvata de Radu Cebanu, Dumitru Daniliuc, Stefan Istrate , Catalin Francu si Stefan Ciobaca.

Va prezint in continuare solutiile. Este interesant de urmarit cum sunt gandite solutiile, care desi sunt echivalente sunt prezentate putin diferit.

Stefan Ciobaca generalizeaza problema:
Eu as fi propus generalizarea: ai 2^n triedre drepte in n dimensiuni.

Rezolvarea prin divide et impera: iei cele 2^n puncte si le separi printr-un hiperplan astfel incat jumate sa fie de-o parte, jumate de cealalta parte s.a.m.d., avand in vedere ca toate hiperplanele sa fie perpendiculare intre ele. Evident, chestia asta se poate. Apoi, fiecare triedru il orientezi spre semisemisemi...semi spatiul total opus si cu marginile paralele cu axele de coordonate q.e.d.
Imi place cum se vede defectul profesional de programator citind demonstratia.

Solutia lui Radu:

Rezolvam prin inductie dupa nr de dimensiuni.

In primul rand: fixezi o directie pt primul plan, il muti paralelel cu el insusi astfel incat sa separe punctele in 2 parti egale, 4 de o parte, 4 de alta (daca stau mai multe pe planul ala exact,nu conteaza, alegi cateva si le declari de o parte, sa fie 4 si restul de cealalta).
Apoi sa zicem ca le luam pe alea de deasupra:
proiectiile lor pe planul respectiv sunt 4 puncte care conform inductiei (pt doua dimensiuni) acopera planul. Cu diedrele din plan faci triedre cu a 3-a dreapta in jos ca sa acopere semispatiul inferior. La fel pt alea de sub plan, pui dreapta a 3-a din triedru in sus ca sa acopere semispatiul superior.
Radu a lasat demonstratia putin incompleta avand incredere ca ma prind singur de cazul 2d si 1d.

Solutia lui Catalin:
Ideea mea e sa gasesc o solutie in care triedrele au laturile orientate paralel cu axele, pentru simplitate.

- Rotim sistemul astfel incat sa nu existe doua lanterne cu coordonate X, Y sau Z egale (pentru a scapa de cazuri particulare).

- Parcurgem lanternele in ordine crescatoare a coordonatei x. Pe primele 4 le marcam cu X+, pe ultimele 4 cu X-.

- Parcurgem cele patru lanterne X+ in ordine crescatoare a coordonatei y. Pe primele doua le marcam cu Y+, pe celelalte doua cu Y-. La fel si
pentru cele patru lanterne X-.

- Parcurgem cele doua lanterne X+Y+ in ordine crescatoare a coordonatei z. Pe prima o marcam cu Z+, pe a doua cu Z-. La fel si pentru celelalte 6 lanterne marcate cu X+Y-, X-Y+, X-Y-.

Avem opt lanterne marcate cu X+Y+Z+, X+Y+Z-, pana la X-Y-Z-. Acum le pozitionam paralel cu axele Ox, Oy, Oz si in sensurile indicate de semne. De exemplu, lanterna X+Y-Z-

va lumina catre sensul pozitiv al axei Ox si catre sensurile negative ale axelor Oy si Oz; cu alte cuvinte, ea va lumina punctul de coordonate (+inf, -inf, -inf).

Dandu-se un punct P(x,y,z), trebuie demonstrat ca exista o lanterna care il lumineaza. Analizam coordonata x. Datorita constructiei, x va fi fie mai mare decat toate coordonatele x ale lanternelor marcate cu X+, fie mai mic decat toate coordonatele x ale lanternelor marcate cu X- (fie ambele, daca x este situat intre cele doua grupuri de 4 lanterne). Alegem acel set de 4 lanterne si reluam rationamentul pe axele Oy si Oz. in final, obtinem minim o lanterna care lumineaza punctul P.

Si la Catalin se vede programatorul din spatele solutiei. Se observa cum structura rezolvarii este bazata pe vectorii de cate 3 elemente in baza 2.

Stefan Istrate are o solutie foarte misto, cu desene dragute, pe care o gasiti pe forum . Merita sa o cititi!

Solutia lui Dumitru nu o am scrisa.

La solutia lui Stefan Ciobaca si cea a lui Catalin Francu nu e demonstrata ipoteza ca putem gasi un sistem de coordonate in care toate punctele au coordonatele x1, x2, .. respectiv diferite . Va incurajez sa va incercati puterile pe aceasta subproblema in sectiunea de comentarii

O problema similara a fost propusa la un ACM in regiunea din Nord Estul Europei: Se cere iluminarea planului cu n lanterne (n <= 30) de coordonate date, ce pot fi rotite, al caror fascicul emite lumina sub un unghi de marime 2pi/n. Pentru fiecare lanterna trebuie returnata orientarea ei. La aceasta problema, pe langa solutia ei, e interesant si algoritmul folosit pentru evaluarea corectitudinii unui rezultat.

Pentru mai multe probleme interesante cu lanterne puteti citi urmatoarele lucrari:

Bose, J., L. Guibas, A. Lubiw, M. Overmars, D. Souvaine and J. Urrutia, "The floodlight illumination problem"
Czyzowicz, J., E. Rivera-Campo and J. Urrutia, "Optimal floodlight illumination of stages"

 Comentarii (0)

Categorii: potw probleme

Se apropie ACMul

Cosmin
Cosmin Negruseri
21 octombrie 2007

Pe 25-28 Octombrie se va desfasura la Universitatea Politehnica din Bucuresti faza pe sud estul Europei a concursului ICPC organizat de ACM. Acest concurs este unul in care echipe de trei studenti, fiecare echipa lucrand pe un singur calculator, se infrunta pe parcursul a cinci ore sa rezolve cat mai repede intre sapte si noua probleme.

Solutia unei probleme se ruleaza pe o suita de teste si este considerata corecta doar daca obtine rezultate corecte pentru toate testele. Daca au rezolvat corect o problema, echipa primeste um balon cu culoarea corespunzatoare problemei, daca nu se primesc niste mesaje ca 'Raspuns Gresit', 'Timp de executie expriat', 'Limita de memorie depasita' etc Astfel este usor de a vedea clasamentul sau cea mai simpla problema pe care echipa ta nu a rezolvat-o inca, daca te uiti prin sala la baloanele celorlaltor echipe. Punctajul este alcatuit din suma timpilor trecuti de la inceputul concursului pana la rezolvarea corecta fiecarei probleme, la care se adauga cate 20 de minute penalizare pentru incercarile esuate de a trece testele. Aceasta modalitate de acordare a punctajelor face ca strategia cea mai buna sa fie rezolvarea problemelor simple la inceput. De obicei problemele sunt calibrate cam o treime simple, o treime medii si o treime mai grele, si se urmareste ca fiecare problema sa fie rezolvata de cel putin o echipa, dar sa nu fie o echipa care sa rezolve toate problemele.

Vor mai urma saptamana aceasta cateva posturi legate de ACM ICPC in curand.

 Comentarii (0)

Categorii: concursuri

Alta problema misto

Cosmin
Cosmin Negruseri
20 octombrie 2007

Cum v-a placut prima problema, voi continua sa postez din cand in cand probleme interesante. Din cate imi amintesc, cred ca urmatoarea este de la olimpiadele rusesti ca si prima de altfel. Rusii au pe la concursuri tot felul de probleme cretze care par simple dupa ce le vezi solutia.

Avem opt lanterne ce emit lumina in forma unor triedre drepte. Sa se demonstreze ca oricare ar fi pozitia lanternelor in spatiu (consideram lanternele ca niste puncte), exista o orientare a triedrelor de lumina astfel ca oricare punct din spatiu sa fie luminat de cel putin o lanterna.

Discutati problema la sectiunea de comentarii. In doua zile voi publica solutia mea, daca nu apare aceeasi solutie pe forum.

 Comentarii (9)

Categorii: potw probleme

Interviu cu Mihai Patrascu

wickedman
Cristian Strat
19 octombrie 2007

Cosmin a publicat un interviu cu Mihai Patrascu pe blog-ul 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).

In 2005 a luat premiul Outstanding Male Undergraduate Award pe Statele Unite si Canada.

Citeste interviul acum:

 Comentarii ()

Categorii: stiri

Interviu cu Mihai Patrascu - partea a doua

Cosmin
Cosmin Negruseri
19 octombrie 2007

Acum zece zile am publicat prima parte a interviului cu Mihai Patrascu . A venit timpul sa publicam si partea a doua. In ea Mihai ne vorbeste de olimpiade, de modul lui de lucru si de interese in afara programarii:

Cum ai recomanda cuiva sa se antreneze pentru concursuri sau sa se pregateasca pentru cercetare?

Cred ca cel mai eficient e sa ajungi sa programezi suficient de bine, si apoi sa te concentrezi pe gandirea teoretica la probleme. De prin clasa a 10a nu programam decat cateva zile inainte de olimpiada sa-mi intru in mana. Restul doar ma gandeam dar nu implementam (economiseste mult timp la pregatire).

Din cauza asta nu am fost niciodata un programator prea rapid... In plus capacitatea mea de debug este aproape nula, asa ca preferam sa scriu foarte incet si fara buguri. N-as avea niciodata sanse la un concurs ca ACM sau top coder :)

Care e secretul reusitei la concursuri sau in cercetare? caracteristicile native, educatia profunda, munca depusa?

Clar ca fara inteligenta nu se poate :), dar toti oamenii care ajung sa faca ceva la olimpiade sunt foarte inteligenti. Cred ca ce face diferenta la un nivel inalt e atitudinea personala. In mod constant erau oameni in lot pe care ii consideram mai destepti decat mine, dar eu eram mai hotarat sa castig, lucram mai mult cand trebuia sa lucrez, ma relaxam mai mult cand trebuia sa ma relaxez etc. Nici ceilalti concurenti, nici comisia nu sunt cu un cap mai sus ca tine -- daca tu ai incredere ca esti tare, atunci chiar esti mai tare.

Cum abordezi o problema, ai o reteta standard (generalizare, simplificare, trecerea prin o lista de tehnici) sau ai cate un "aha" moment?

Nu, simt ca intotdeauna imi vin idei dubioase si fara explicatie. Problemele la care ma prindeam cel mai greu erau chestii clasice ca flux, cuplaj, etc -- pana sa ma gandesc ca de fapt poate se foloseste ceva standard imi lua ceva timp.

Cum se compune o problema de olimpiada?

Foarte greu... Am un dispret pentru problemele bazate pe materie avansata. Ne trebuie probleme noi, cu o rezolvare elementara, nu bazate pe ceva care inveti la facultate. Problemele trebuie sa fie cu adevarat concurs de perspicacitate, si ar trebui sa fie la fel de grele pentru un concurent din liceu si pentru un prof care studiaza algoritmi de 50 de ani... Din pacate, e greu de gasit astfel de probleme, si nu am propus prea multe probleme.

De ce nu ai continuat cu concursurile de programare in timpul facultatii?

Concursurile mi se par prin definitie ceva pentru liceu. La nivelul ala inca inveti, si e bine ca ceva sa te motiveze sa inveti, in timp ce iti ascuti inteligenta in domeniu. La facultate stii mai multe, si pot sa faci alte chestii mai important pentru tine si pentru omenire... Poti sa te angajezi, sa lucrezi in cercetare, etc. Poti sa-ti faci un renume la inceput cu IOI, dar pana la urma succesul in viata depinde de alte chestii.

Asta gandeam inca din liceu, asa ca mi-a fost usor sa renunt. In treacat fie spus, am fost de 2 ori la ACM din inertie, o data cu Craiova, si o data la MIT. Amandoua esecuri lamentabile :) Cu echipa din Craiova problema era ca nimeni nu programa suficient de repede (in frunte cu mine). Cu MIT problema a fost interactiunea mea cu autoritatea :) -- am iesit primul la concursul individual, dar echipa s-a format din locurile 2,3,4 la decizia profilor coordonatori.
Razbunarea mea a fost ca anul ala MIT-ul nu s-a calificat la regionala ;)

La ce alte proiecte software ai lucrat?

Singurul proiect mai mare care l-am facut a fost evaluatorul pentru olimpiade (nu stiu daca se mai foloseste, dar s-a folosit la BOI la Iasi si la cateva nationale). Restul totul au fost programe mici pt olimpiade. Si cand am lucrat pentru companii, am lucrat pe directii de cercetare unde nu trebuie decat programe mici prototip care sa testeze o idee.

Ai vreo metoda dupa care iti imparti timpul sau lucrezi cand si cum ai chef?

Eu profit de libertatea din cercetare pana la punctul unde enervez pe toata lumea :) Daca n-am chef sa fac nimic saptamana asta, nu fac nimic saptamana asta. Ma duc la munte, citesc ceva, nu conteaza. Cand lumea munceste la o lucrare (care implica finalizat tot felul de detalii si scrisul propriu-zis), eu de obicei fac misto de ei :) De obicei nu reusesc nici macar sa scriu pe hartie niste calcule.

Dar daca am o idee de rezolvare in cap si vreau sa scriu o lucrare pentru o conferinta, am o reteta standard. Cu 2-3 zile inainte de deadline, imi iau periuta de dinti, 10-15 sticle de Pepsi Diet, cateva kg de prajituri, si ma duc in birou. Si acolo petrec cele 2-3 zile lucrand (am determinat ca rata optima de somn in birou e cam 2h pe zi). Adrenalina e foarte interesanta.

Citesti bloguri/frecventezi forumuri? Spune-ne cateva exemple.

Chiar am si eu un blog la http://infoweekly.blogspot.com/, in care discut probleme de cercetare in algoritmi. Cred ca unele chestii ar putea fi interesante pentru studentii la olimpiade in ani mai mari, care vor sa se decida ce vor sa faca in viitor. Pot sa vada cateva probleme si sa vada daca ii tenteaza teoria.

De citit, citesc cateva bloguri din teorie, dar nu cu prea multa pasiune (doar ca e util sa te tii la curent). La forumuri nu particip.

Ce interese, hobbyuri, pasiuni care nu sunt legate de programare ai?

A, multe... Desi intotdeauna stau rau cu timpul, asa ca fac mai putine decat as vrea. Imi place foarte mult sa calatoresc, si acum pot sa fac asta cu toate conferintele la care ma duc (am ajuns in 28 de tari pana acum). Imi place sa vorbesc cu lumea, sa descopar culturi noi, si imi place sa citesc mult despre istorie.

Periodic descopar pasiuni pt un nou sport. In liceu mergeam pe munte si jucam badmington, apoi am facut alergari (era o vreme cand alergam 16km pe seara), am jucat rugby (in Divizia 3 din State), mai recent climbing si sailing.

Pe ce te concentrezi acum?

Anul asta voi termina doctoratul... Trebuie sa scriu o teza si sa aplic pentru joburi (in pricipal, o sa aplic pentru joburi de prof la universitati). Asta ia destul de mult timp. In rest, mai lucrez la cercetare, si mai calatoresc.

Cum tii pasul cu cercetarea curenta? Sunt conferintele importante si discutiile cu ceilalti cercetatori (comunitatea din care faci parte), sau e deajuns sa citesti research paperurile ce apar?

Sunt cateva conferinte importante la care ma duc intotdeauna. Problema e ca nu pot sa stau intr-o sala si sa ascult o prezentare (lipsa de concentrare). Asa ca in timpul conferintei ma intalnesc cu prieteni vechi care de asemenea nu vor sa fie prezenti, si mergem la bere sa mai discutam probleme. Ca sa aflu ce se intampla citesc lucrari pe Net.

Cum te vezi in 5-10 ani?

Sper ca cu un job :) Planul este sa lucrez in continuare in domeniu si sa mai rezolv cateva probleme importante. Apoi as vrea sa incerc si sa fondez o companie cu o idee trasnet. Avem multe rezultate valoroase in teorie, care nu se aplica pentru ca lumea nu se gandeste suficient la impactul mai larg si nu gaseste aplicatiile bune. Daca imi vine vreo idee buna la capitolul asta nu voi ezita sa incerc o companie, in paralel cu jobul de prof.

Vrei sa le transmiti ceva celor ce acum incep cu viata competitionala?

E sansa voastra sa aratati lumii ce tari sunteti, si sa deveniti si mai tari pe parcurs. E un drum bun in viata.

Ii multumim lui Mihai pentru un interviu foarte interesant.

 Comentarii (4)

Categorii: concursuri interviu
Vezi pagina: 12345... 293031323334 35363738394041 (407 rezultate)