Directioneaza catre noi 2% din impozitul pe venit datorat la stat.

In conformitate cu prevederile Codului Fiscal, art. 84 poti directiona 2% din impozitul pe venit datorat la stat catre o entitate non-profit (i.e. Asociatia infoarena).

Procedura este foarte simpla si nu te costa nimic!

→ Vezi cum se face

Am luat o pauza destul de lunga cu problema saptamanii. La ultima problema am primit doar doua solutii si am uitat de la cine (amintiti-mi si va trec ca rezolvitori). Gasiti textul aici .

Solutia problemei e destul de misto: Ne gandim la spatiul starilor problemei ca un patratul unitate din planul cartezian cu originea in (0, 0) si cu punctul diagonal opus in (1, 1). Abscisa unui punct din patratul acesta reprezinta pozitia normalizata pe intervalul [0, 1] a unui mobil sau un robot pe unul dintre cele doua drumuri de la A la B, iar ordonata punctului va reprezenta pozitia normalizata a celuilalt mobil respectiv robot pe al doilea drum de la A la B. Acum pentru ca ambele mobile pleaca din A si ajung in B, punctele asociate pozitiilor lor ne vor da o curba pornind din punctul (0, 0) si ajungand in punctul (1, 1). Iar punctele ce reprezinta miscarea celor doi roboti, care unul pleaca din A si ajunge in B si celalalt pleaca din B si ajunge in A, ne descriu o curba ce pleaca din punctul (0, 1) in (1, 0). Cele doua curbe trebuie sa se intersecteze si de aici rezulta ca orice doua drumuri am forma intre orasele A si B si orice itinerariu ar avea robotii, daca doua mobile pot ajunge de la A la B fiind legate cu o sfoara de lungime 10 m, atunci robotii nu pot ajunge unul din A in B si celalat din B in A fara sa se atinga.

In perioadele 18-19 decembrie 2007 si 8-9 februarie 2008 s-a desfasurat concursul national Stelele Informaticii. Rezultatele concursului le poti gasi aici si aici.
Poti gasi cele 12 probleme propuse in arhiva de probleme, impreuna cu sursele trimise.

Discutam mai demult cu Mihai Patrascu si eram curiosi ce se intampla cu medaliatii romani la olimpiada internationala de informatica dupa terminarea liceului. Am pus o pagina wiki pe infoarena cu olimpici si datele s-au adunat imediat. Mihai spera ca prin obtinerea listei sa poata incuraja pe unii profesori de la MIT sa dea o importanta mai mare rezultatelor la concursurile de programare in procesul de admitere. Ideea era sa se gaseasca o corelatie intre obtinerea unor rezultate la olimpiade si facultatea urmata sau jobul dupa terminarea facultatii. Rezultatele obtinute le puteti vedea aici . Ele sunt un set de date foarte interesante! si ne dau o fereastra spre parcursul unor oameni interesanti. Insa nu putem trage concluzia dorita de Mihai, ca multi ajung sa aiba rezultate in cercetare. 22 din totalul de 58 de olimpici romani si moldoveni medaliati la olimpiada internationala de informatica lucreaza sau au facut un internship la Google.

Pot trage concluzia (putin trista) ca multi programatori foarte buni (nu doar olimpicii) prefera sa lucreze la o firma tare din strainatate in loc sa ramana in tara. Domeniul IT trebuie recunoscut ca unul de viitor si oamenii buni ar trebui incurajati sa ramana in Romania si sa puna osul la treaba.

Gasiti aici unul dintre cele cinci posturi scrise de Mihai pe tema destinelor olimpicilor.

shameless plug: Daca esti un programator foarte bun sau daca cunosti programatori foarte buni care sunt interesati de un job la Google spuneti-le sa ma contacteze la cosminn ~ at ~ gmail.com. Si ca o paranteza finala, sunt foarte multi programatori extraordinari la Google care nu au avut in viata lor nici o treaba cu olimpiadele.

Imi place mult threadless.com . E un site unde concureaza diverse designuri de tricouri (poza din stanga luata de pe threadless.com e un exemplu al unui astfel de design). Daca un design primeste un scor bun atunci autorul ia 2000$ si cei de la threadless incep sa vanda tricouri cu designul respectiv. In 2006, creatorii siteului au castigat in jur de 6 milioane de dolari, deci pe langa ca e o idee misto are si sens pe partea financiara. O parte importanta a succesului vine din implicarea afectiva a vizitatorilor. Designurile ce ies castigatoare au fiecare ceva deosebit si nu se produc in masa iar asta ataseaza cumparatorul de tricoul cumparat. Lumea se implica, comenteaza pe forumuri, voteaza, blogheaza si isi fac poze cu tricourile respective.

Alt site de succes ce se bazeaza pe concursuri este topcoder.com. Dar nu ma refer la concursurile de algoritmica, care au fost gandite ca o metoda de a aduce oameni buni pe site si apoi sa fie recrutati pentru joburi. M-am gandit la concursurile de componente, unde diversi programatori concureaza pentru realiza o componenta software. Succesul siteului e datorat pe de o parte faptului ca programatorii ce concureaza sunt din tari unde salariile de programatori sunt mici. Dincolo de acest aspect, procesul folosit de topcoder pentru crearea unei componente este foarte bine pus la punct si elementul de competitie intre programatori face ca rezultatul final sa fie destul de bun. Probabil este mai bun decat ceva scos de o firma care face outsourcing, dar nu pot sa imi dau cu pararea pentru ca nu am lucrat in Romania la niciuna.

Concursul organizat de Netflix e alt exemplu. Netflix e un serviciu care trimite DVD-uri cu filme in posta. Ei au lucrat la un sistem de recomandari personalizate de filme, pe baza filmelor vazute de clienti. Au transformat problema interna de imbunatatire a algoritmul cu 10% in una deschisa publicului larg cu un premiu de un milion de dolari. La prima vedere premiul de un milion de dolari pare unul foarte mare, dar el reprezinta doar salarul a 10 programatori in state timp de un an. Alta problema este ca nu se stia daca pragul de 10% este usor sau nu de trecut. Ideea de a organiza un concurs pentru a rezolva problema a fost foarte buna, pentru ca multi cercetatori au muncit intens la ea si cei de la Netflix platesc premiul doar daca cineva obtine rezultatul cerut. Deocamdata nimeni nu a reusit sa atinga pragul fixat.

Faptul ca concurenta aduce dupa ea calitate este clar, dar mi s-au parut interesante abordarile acestiu principiu pe cateva siteuri ce imi plac.

Mai multe despre cei de la threadless puteti vedea in prezentarea lor presarata de glume si idei misto de aici

Am vazut urmatorul puzzle pe un site cu intrebari de interviu Microsoft. Daca nu il stiti deja, incercati sa il rezolvati singuri fara a cauta indicii pe net. E un test interesant de intelegere a operatiilor pe biti.

Ce returneaza functia foo, cand x e un intreg fara semn pe 32 de biti?

unsigned int foo(unsigned int x) {
  x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1);
  x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2);
  x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4);
  x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8);
  return (x >> 16) | (x << 16);
}

Mircea a terminat implementarea proiectului IAP5 . Si Adrian Diaconu a selectat 50 de probleme care sa faca parte din proiect. Acum orice vizitator al siteului va putea vedea toate sursele trimise la oricare dintre cele 50 de probleme selectate. Problemele din arhiva cu "surse deschise" au cate o carte desenata in dreptul lor. Pentru a vedea o sursa puteti intra la monitor, de acolo la evaluare completa, iar apoi la vezi sursa.
Problemele au fost alese de Adi pentru diversitatea lor. Sper ca acest pas facut de infoarena sa fie urmat si de alte proiecte legate de olimpiadele de informatica. Tin minte cum in liceu invatam foarte mult citind din sursele elevilor mai mari. Cred ca problemele cu sursele deschise de pe infoarena se vor dovedi un material foarte bun de pregatire.

Mai avem inca o initiativa interesanta, si cred ca impreuna cele doua proiecte vor spori cu mult utilitatea siteului.

Va astept cu comentarii si sugestii!

Se apropie olimpiada judeteana si ma gandeam de ceva vreme sa scriu un articol despre diverse metode de antrenament. Am exagerat putin cu lungimea articolului, probabil am avut in minte postul Size matters a lui Steve Yegge, dar va incurajez cu caldura sa il cititi in totalitate. Sper sa va placa sa il cititi in aceiasi masura in care mi-a placut mie sa il scriu.

Tin minte senzatiile de la olimpiadele de mate din gimnaziu, cand ajungeam la concursuri regionale sau nationale si nu prea intelegeam despre ce vorbeau unii elevi de exemplu "principiul cutiei" sau "media patratica". Un elev era foarte nervos ca nu facuse "problema cu musca" la clasa. Stiind trucul respectiv ar fi rezolvat toate patru problemele la olimpiada nationala, fara acel truc a ramas doar cu trei probleme rezolvate perfect. Eu eram foarte fericit ca anul ala rezolvasem o problema si un subpunct de la alta si mergeam cu capul sus acasa cu un premiu.

Alta amintire este ca in clasa a 8-a rezolvasem o problema de distanta in spatiu de care eram foarte multumit si la o tabara de pregatire un elev din Arad, si el pe clasa a 8-a, mi-a zis ca a rezolvat problema respectiva in 5 metode, una dintre ele folosind integrale. La aceiasi tabara nu imi iesise o problema de geometrie in plan care cerea minimizarea unor distante si acelasi elev din Arad mi-a aratat o cartulie ce trata acel gen de probleme si mi-a zis ca daca studiam cartea inainte ma prindeam de problema. Eu abia daca rezolvam o culegere de probleme intr-un an de zile ...

Era o problema de standarde diferite, cum inca nu eram copt, credeam ca ideile apar din aer si e de ajuns sa stii la nivel de clasa matematica si apoi sa te "scremi" tare ca sa reusesti sa rezolvi problemele.

In liceu am trecut pe info, unde mi se parea mai usor. Erau doar vreo doua culegeri de probleme nu mii ca la matematica prin care sa filtrezi pana sa gasesti una ca lumea. L-am cunoscut pe Adi Carcu cu care si acum sunt foarte bun prieten. Mergeam la el acasa destul de des si povesteam probleme pana se facea tarziu ... cred ca parintii lui se intrebau cand o sa plec :).

Pana in clasa a 11-a aveam idei pe la probleme dar nu imi iesea implementarea la nici una. Atunci a inceput concursul Bursele Agora la care am participat serios facand la fiecare problema solutii diferite, evaluator, generatoare de teste aleatoare si soltuii brute force. Abia dupa ce am facut 15 probleme de la Bursele Agora ca lumea am inceput sa am incredere in abilitatile mele de implementare. Atunci am dat si peste Cormen, si eram tare entuziast pentru ca inainte nu aveam de unde invata si deodata aveam o carte in care erau explicate toate chestiile despre care auzisem.

Cred ca atunci a fost momentul cand am devenit pasionat de informatica. Citeam in fiecare zi cate ceva mai si implementam si ma gandeam la probleme, si asa mi-am dat seama ce inseamna sa fii olimpic. Cand esti pasionat faci un lucru din placere in fiecare zi. Nu tragi tare cu o saptamana sau doua inainte de judeteana sa acoperi ceva material din programa. Pentru un elev pasionat nu exista programa ci doar placerea de a rezolva probleme si de a invata ceva nou.

Mi-am dat seama cum la matematica eram un pigmeu fata de cei care se pregateau serios. Nu se poate compara munca de un an cu cea de cateva saptamani sau doua luni.

In facultate am meditat de cateva ori un elev care obtinea rezultate destul de bune, dar cand a venit la pregatire am vazut rapid ca nu avea baze teoretice aproape deloc, facea totul dupa intuitie si se descurca bine. A venit cu vreo doua luni inainte de olimpiada si apoi a doua data cu 2 saptamani, si i-am zis ca are o gramada de gauri in cunostinte. El mi-a replicat ca in astea doua saptamani trage tare. Mi-a venit sa rad si i-am zis ca nu are rost sa se chinuie sa acumuleze multa informatie ci sa foloseasca aceiasi metoda care i-a mers si pana atunci. Problema e ca dupa ce faci un salt in cunostinte, la inceput nu rezolvi probleme mai usor, ci iti dai seama ca abordarile tale sunt gresite. Astfel in loc sa mai incerci o abordare gresita cu care ai putea castiga 60-70 de puncte vei astepta ideea care rezolva perfect problema. Dar ideea respectiva s-ar putea sa nu vina si tu sa ramai cu 0 puncte. Invatarea si evolutia e un maraton nu un sprint (am furat expresia asta de la Emanuel, colegul de apartament ;)).

Radu Berinde imi povestea cum intr-o vacanta de vara facea probleme pe acm.timus.ru toata ziua, in vremea aia era al 4-lea in clasamentul rezolvitorilor de pe site. Programul lui zilnic era: antrenamente la sala, iesire seara la bere, si probleme pe timus in restul zilei. Mi se pare o vacanta destul de misto :)

Adi Carcu nu se antrena mai deloc pentru concursuri, inainte de judeteana facea una sau doua probleme ca sa fie sigur ca nu si-a iesit din mana si cam atat. Dar el intrase in lot din clasa a 9-a si acolo facuse antrenamente serioase unde luptai pentru locul la un concurs international. Mihai Patrascu zicea ca o tabara de antrenament ar fi durat o luna in vremea cand participa Adrian.

Pe langa asta, Adi avea tot timpul proiecte personale de programare la care lucra (printre care un chat listener pentru reteaua din camin :)), si cred ca ele ajuta chiar daca nu sunt de algoritmica. Adi dupa fiecare lot trecea prin problemele ce s-au dat si incerca sa le rezolve astfel incat codul sursa sa fie eficient, foarte inteligibil si foarte scurt. Tot timpul programele lui mi se pareau foarte simple si lizibile in comparatie cu cele ale altor concurenti. Simplitatea, lizibilitatea si faptul ca codul sursa e scurt ajuta mult la viteza de depanarea a bugurilor.

In clasa a 11-a, in seara dinaintea probei citisem intr-o gazeta de info cum se gasesc componentele biconexe intr-un graf neorientat. A doua zi la concurs am primit o problema care cerea determinarea componentelor biconexe intr-un graf neorientat. Nu mai imi aminteam toate detaliile dar, naiv, m-am apucat de lucru. Dupa trei ore nu am reusit sa fac nimic si nu am implementat nici macar solutia evidenta.

Este important sa va antrenati implementarea cum facea Adi pentru a va da seama cum puteti transforma solutiile in cod cat mai simplu, de asemenea orice algoritm netrivial care credeti ca il veti folosi intr-un concurs gen componente biconexe, flux, infasuratoare convexa, subsir crescator de lungime maxima in O(n log n), arbori echilibrati, trebuie sa il implementati de doua sau trei ori pentru a fi sigur ca il faceti corect si rapid cand aveti nevoie de el. Problemele cele mai dificile sunt cand trebuie sa combinati mai multi algoritmi sau structuri de date, iar in concurs se adauga stresul, limitele de timp si nu ar trebui sa mai aveti si probleme de implementare a algoritmilor ce i-ati studiat deja. E bine sa implementati algoritmii pe care ii considerati clasici de mai multe ori si pentru a putea estima mai bine timpul necesar pentru a rezolva o problema. Partea de "time management" e si ea una importanta in concursuri.

Daca vreti sa va antrenati implementarea la problemutze simple puteti incerca cu incredere practice rooms de la topcoder, acolo sunt de la probleme simple la mai grele si aveti acces la codul sursa al unor concurenti care au incercat si ei problemele respective. Puteti vedea o gramada de variante de rezolvare a aceleiasi probleme si va puteti decide care e cea mai buna varianta pentru stilul vostru. La probleme mai grele puteti incerca cu incredere infoarena. Sper ca proiectul in care sharuim sursele si proiectul cu arhiva de invatare va fi folositor in acest sens.

Cu Mircea Pasoi si Silviu Ganceanu vorbeam cand erau ei pe a 10-a respectiv a 12-a aproape in fiecare zi probleme pe messenger si ei lucrau arhiva problemelor de pe acm.sgu.ru , Silviu se si mutase la ICHB si il avea pe Mihai Stroe profesor. Mie mi se pare ca i-a ajutat foarte mult pe amandoi faptul ca discutau si lucrau in paralel.

Silviu imi zicea de trei elevi din clasa a 10-a care lucrasera inainte de ONI toata arhiva de pregatire de la USACO si iesisera pe primele trei locuri la clasa a 10-a la ONI, cred ca primul a fost Valentin Stanciu, daca tin bine minte. Lui Silviu ii placea cum cei trei elevi ai lui se ambitionasera unul de la altul si au evoluat mult.

Nu stiu daca ati urmarit anul trecut evolutia clasamentului arhivei de probleme, dar eu vedeam cum wefgef, gcosmin si btataroiu se luptau intre ei si in fiecare zi isi mareau numarul de probleme rezolvate din arhiva.

Este foarte bine sa ai un prieten sau un grup de prieteni pasionati si ei de concursuri. Concurenta te ambitioneaza iar comunicarea cu alti pasionati de algoritmica te ajuta sa aflii tot felul de trucuri mai repede. In general profesorul de la clasa e depasit de nivelul problemelor de olimpiada, daca nu l-ai depasit inca ar trebui sa iti faci probleme. Rolul profesorului este doar sa zgandare pasiunea in tine la inceput, dupa aia esti pe cont propriu si de aceea comunicarea cu un grup de pasionati e vitala. Pe forumul infoarena sau pe cel de la topcoder va puteti face prieteni pe care ii veti pastra si mai tarziu in viata.

Ar ajuta daca gasiti pe un fost olimpic de la care sa luati meditatii, in Bucuresti cel mai simplu e sa mergi la ICHB, in Iasi sau Suceava gasiti relativ usor fosti olimpici puternici, in Ardeal in schimb mai rar, probabil ati putea vorbi cu Patcas Csaba (coleg cu mine de an) care pregateste echipa Babesului pentru ACM si pe cativa baieti din Cluj pentru ONI. Cineva cu experienta in concursuri va poate ghida inspre anumite tipuri de probleme, spre siteuri sau carti utile.

Pregatirea psihica si controlarea stresului in timpul concursului sunt si ele importante. Mircea a preluat o idee de la echipa de ACM a universitatii Waterloo, si inainte de un concurs important face o pauza de programare de o saptamana ca sa se linisteasca. Abordarea asta s-ar putea sa nu fie buna pentru cei ce "ingrasa porcu in ajun". Puteti sa incercati sa aflati din timp care sunt conditiile in care trebuie sa participati in concurs si sa va antrenati in acele conditii pentru a avea un mediu familiar cand ajungeti la fata locului.

Alta modalitate de pregatire e participarea la cat mai multe concursuri pe internet. Pentru mine Bursele Agora a insemnat destul de mult si cred ca nu numai pentru mine, poate ne zice si Mugurel ceva aici. De asemenea cand organizam concursul "Algoritmus" impreuna cu Ciprian Cana, am vazut un nume nou prin clasamente, Radu Marin. Facea destul de bine pe problemele care eu cu Cipri ne chinuisem sa fie destul de grele. I-am zis lui Mircea la misto ca va avea un concurent puternic anul ala. Predictia s-a transformat in realitate si Radu a luat medalie de bronz anul respectiv la IOI.

Sumarizez putin elementele importante ce ajuta la obtinerea unor rezultate bune la olimpiade :

• munca individuala ghidata de pasiune
• antrenarea modalitatii de codare a algoritmilor
• gasirea unui grup de prieteni pasionati
• gasirea unui mentor cu experienta
• participarea la cat mai multe concursuri online

Cu proiectul infoarena incercam sa va ajutam sa atingeti performanta in informatica cat mai usor. Avem o arhiva cu un numar impresionant de probleme frumoase, o sectiune de articole interesante, o lista de trucuri care ar trebui stiuta pentru concursuri si doua proiecte pe care le gasiti aici si aici care vor mari si mai mult utilitatea siteului.

Va astept cu comentarii! Sunt curios si de stilul vostru de antrenament!

Daca mai vreti si alte sfaturi puteti citi ghidul pentru concursuri al lui Mircea, sau articolul lui Mugurel.

Facultatea de Matematica si Informatica si Centrul de Cercetare in Modele de Calcul, Algoritmi si Criptografie (MOCALC) anunta:

Conferinta •Mihai Patrascu
Perspective Geometrice in Dezvoltarea Algoritmilor
Joi 31 ianuarie si vineri 1 februarie, ora 15:00, sala 220

Rezumat

Cum ajuta o constructie Cantor pentru cardinalitatea numerelor rationale la obtinerea unor structuri de date eficiente? De ce estimarea normelor in dimensiuni inalte este necesara la optimizarea cautarilor in baze de date? Cum pot progrese in intelegerea geometriilor ne-euclidiene sa ajute la constructia microprocesoarelor? Perspectiva geometrica s-a dovedit din ce in ce mai utila in progresele recente in dezvoltarea algoritmilor. In acest curs, vom discuta cateva idei matematice reprezentative, si cativa algoritmi frumosi care se obtin. Cursul este la nivel introductiv si speram ca va contine idei interesante si pentru informaticieni care urasc matematica si pentru matematicieni care urasc informatica.

Despre

Mihai Patrascu •mpatrascu este student la doctorat la MIT si are printre cele mai bune rezultate la olimpiadele internationale la informatica dintre romani. Poti afla mai multe despre el din interviul (partea 1 si partea 2) luat de Cosmin Negruseri, din pagina lui personala sau de pe blog-ul lui.

Imagine Cup este o competitie internationala pentru studenti pasionati de tehnologie si de arte digitale. Concursul contine inclusiv o sectiune de algoritmi. Puteti afla mai multe detalii din mesajul de mai jos din partea Microsoft Romania.

Stimati studenti,
Va incurajez sa participati la Imagine Cup 2008. Este o sansa foarte buna de afirmare si de dezvoltare a unor abilitati cum sunt cele de comunicare si de lucru in echipa sau de aprofundare a unor tehnologii ce va pot folosi azi si pe viitor. Competitia este un excelent prilej de inovare si Microsoft Romania in parteneriat cu Autoritatea Nationala pentru Cercetare Stiintifica sunt initiatorii programului Innovation Accelerator, adresat studentilor cu performante deosebite la Imagine Cup 2008:
• finantarea proiectelor pentru dezvoltarea accelerata a prototipurilor inainte de finala (cu pana la 4000 de RON) si
• sesiuni de dezvoltare a competentelor de prezentare si cunostinte de business utile viitorilor antreprenori in tehnologia de varf. Obtineti mai multe detalii de pe www.microsoft.ro/educatie/studenti (consultati paginile dedicate sectiunii Software Design).

Aveti de ales intre urmatoarele 9 sectiuni:
• Software Design, Embedded Development, Game Development - proiecte complexe, inovatie, lucru in echipa
• Algorithm, IT Challenge, Project Hoshimi - probe dinamice, in general competitii individuale
• Photography, Short Film si Interface Design - arte digitale

Tema generala a competitiei este legata de rolul tehnologiei in ocrotirea mediului inconjurator. Puteti lua contact cu cateva idei de participare foarte pertinente de pe forumurile competitiei, de exemplu legate de Biroul Unesco pentru Educatie si Dezvoltare Durabila. Daca sunteti interesati de impresiile unor finalisti romani de anul trecut in Seul, va recomand 4 interviuri publicate pe www.msevents.ro (prezentare Silverlight), www.techready.tv/imaginecup (format WMV) sau www.trilulilu.ro/microsoft (prezentare Flash).

Finala mondiala va avea loc in iulie 2008, in Paris. Aveti timp suficient pentru o participare de calitate cu care mai tarziu sa ne mandrim in facultatea noastra. Primul pas este sa va inregistrati pe www.imaginecup.com. Inregistrarea nu ia mai mult decat 1-2 minute si de aici mai departe veti fi indrumati in functie de sectiunea preferata si etapele pe care trebuie sa le parcurgeti in concurs.

Aveti grija, pentru 7 dintre cele 9 sectiuni termenul limita pentru participare este 1 februarie 2008. Daca sunt nelamuriri, va rog sa le adresati in scris lui Todi Pruteanu, [email protected].

Succes in sesiune si parcurs cat mai lung la Imagine Cup.