Blog infoarena

Romanii la DisneyWorld - partea intai

Cosmin
Cosmin Negruseri
04 decembrie 2007

In fiecare an topcoder organzieaza doua turnee, unul deschis numai studentilor si altul deschis pentru oricine cu varsta mai mare de 18 ani. De anul trecut cei de pe topcoder au initiat si o competitie de programare pentru liceeni. Ei au mai multe tipuri de competitii: algoritmica, maraton, development, design si studio. La concursuri se califica si romani din cand in cand printre care Adrian Carcu a avut rezultate mai deosebite fiind de doua ori campion si o data locul doi la sectiunea de software design. De la el am luat si eu microbul. Tin minte cum participam impreuna la concursuri de algoritmica la Laboratoru de cercetare al UBB pe la 4 noaptea pentru ca acestea erau organziate in special pentru programatorii din state.

In perioada 30 Octombrie - 2 Noiembrie s-a desfasurat finala concursului TopCoder Collegiate Challenge la Disney World, iar in finale s-au calificat trei romani: vlad_d (Vlad Dumitriu ) ce a participat la partea de studio a concursului, luca (Lazar Lucian, doctorand la Babes Bolyai, Cluj) care a participat pe partea de software design si domino (Mircea Pasoi student Universitatea Bucuresti) ce a participat la concursul de algoritmica si a reusit sa se califice in finala mica a acestui concurs clasandu-se in primii 8 programatori din lume. Am vrut sa aflati mai multe despre concursurile topcoder asa ca le-am luat interviuri celor trei. In acest post public interviul cu Vlad depsre concursul de design grafic, dupa care vor urma doua posturi cu intrebari si raspunsuri pentru Luca si Mircea. Vlad e participant mai vechi pe infoarena si ne-a facut logo-ul pentru preOni. Ii multumesc inca o data din partea echipei.

Vlad Dumitriu

Cum e concursul de design grafic?
E fain. La Studio Design trebuie "desenate" diferite chestii. Apar tot felu de proiecte de la logo design pana la webdesign, printing design si tot felul. Iar daca te referi la finala e faina atmosfera, te intalnesti cu oameni de treaba si primesti un proiect care trebuie sa il termini in 8 ore.

De ce ai ales sectiunea de design?
Ah, pai am incercat Algo dar am picat din runda 1 din cauza unei '{' la MM am ajuns in runda 2 si eram in juru lui top 100, si dupaia m-a cuprins lenea. Asa ca am incercat si Studio Design.

Cum ai inceput cu designul?
Am inceput si eu sa ma joc prin Photoshop, sa editez poze si etc.

Ce tooluri sunt folosite?
La studio design ai voie Photoshop CS3, AI CS3, si GIMP. Eu folosesc numa Photoshop si AI.

Care sunt partile dificile in acest concurs?
Probabil Inspiratia iar daca ai ceva practica cam poti sa iti desenezi ideile.

Ce caracteristici trebuie sa aiba un design bun?
Sa fie bun. In primu rand sa indeplineasca conditile din proiect requirements iar dupaia conteaza foarte mult stilu, culorile folosite, fonturile folosite, elemente grafice, sunt multe.

Cum ar trebui sa inceapa cineva interesat de acest tip de concursuri?
Probabil tutoriale de pe net sau daca este la scoala de Grafic Design numa' bine.

Ce ii deosebeste pe designerii buni fata de cei medii?
Probabil practica in caz ca au acelasi talent. Cred ca trebuie si talent si practica.

Cat timp iti ia sa termini un design?
Depinde. De la cateva ore la o zi probabil. Depinde cat de mare e proiectul, iar dupa terminare mai vine si revizuirea. Pe Studio.Topcoder la proiectele mici ai voie sa faci maxim 2 concepte iar la cele mai mari numai unu.

Cum a fost la DisneyLand?
Hmm.. Fain.. de mers cu familia daca ai copii mici. In rest pentru studenti nu prea e DisneyLand-ul, ci GreatAmerica, SixFlags etc.. ceva mai serios.

Mersi pentru interviu Vlad. Revin maine cu unul din celelalte doua interviuri.

 Comentarii (0)

Categorii:

Inteligenta, nativa sau educata?

Cosmin
Cosmin Negruseri
30 noiembrie 2007

Prin scoala generala si apoi in liceu, credeam ca inteligenta unui om are un nivel maxim pana la care se poate ajunge, care prin oricata munca nu se poate depasi.

La sfarsitul liceului si inceputurile facultatii, prin 2002, m-am mai maturizat si eu si mi-am schimbat parerea. Cred ca in conditii intr-un mediu bun si cu o motivatie puternica poti progresa extrem de mult. Este mai important sa lucrezi bine si sa nu intri in rutina, decat sa lucrezi mult.

Am citit mai multe articole interesante legate de tema asta din care trei mi-au ramas in minte:

How to raise smart kids ne spune cum copiii care cred ca inteligenta poate fi antrenata evolueaza in timp mult mai bine fata de cei cu credinta ca inteligenta e o chestie nativa.

Teach yourself programming in ten years , scris de directorul pe cercetare de la Google, sustine ca performanta intr-un domeniu se atinge dupa multi ani de practica, si ne ofera ca exemple unii oameni considerati genii, cum au fost Mozart, Beatles sau Chaucer, ce au produs rezultate de nivel foarte inalt dupa mai mult de zece ani de activitate in domeniul in care erau experti.

Al treilea articol The Grandmaster Experiment este despre psihologul Polgar care si-a ajutat toate cele trei fiice ale sale sa devina maestre la sah. Polgar nu credea in notiunea de geniu, iar reusita lui demonstreaza intr-o oarecare masura acest lucru. Intr-o perioada in care se considera ca viziunea spatiala era una mai grea pentru inteligenta feminina, performantele celor trei fete au demonstrat contrariul.

Cititi toate trei articolele pentru ca merita.

Voi ce credeti? Este inteligenta o caracteristica mai mult nativa sau educata?

 Comentarii (6)

Categorii:

Alt demo de la Microsoft

Cosmin
Cosmin Negruseri
28 noiembrie 2007

Inca un demo foarte tare de la Microsoft Research. Imi plac ideile astea istete si foarte simplu de pus in practica.

 Comentarii (2)

Categorii:

Post-Happy-Coding

Cosmin
Cosmin Negruseri
24 noiembrie 2007

Concursul Happy Coding s-a incheiat, si a fost unul de succes, facand ca traficul de pe site sa se dubleze. Mugurel si restul echipei de propunatori au facut treaba buna, propunand un numar impresionant de probleme, iar acum tot Mugurel ne prezinta o analiza la rece a concursului:

A mai trecut un concurs Happy Coding si s-ar putea spune ca incepe sa devina un concurs infoarena traditional. Daca in primul an (2005) toate problemele au fost luate de la concursurile de selectie a echipelor ACM ICPC din Universitatea Politehnica Bucuresti, incet-incet Happy Coding a ajuns sa aiba parte de portia sa proprie de probleme originale si interesante ;) Editia de anul acesta a reprezentat cel mai lung concurs infoarena si a avut cel mai mare numar de probleme (25). Ca si in anii anteriori, evaluatorul a fost pornit pe toata durata concursului, dar, pentru a "contrabalansa" aceasta facilitate, am stabilit ca la fiecare problema sa se poata obtine doar 0 sau 100 de puncte. In felul acesta, Happy Coding a devenit mai asemanator cu concursurile de tip ACM ICPC decat cu olimpiadele scolare - mie personal imi plac mai mult concursurile de tip ACM ICPC, datorita clasamentului "live" si a dinamismului mai ridicat. Apropo de clasament "live", a existat un "curent de opinie" la IOI anul acesta, conform caruia ar trebui sa existe un fel de clasament semi-live si la IOI (sa vedem ce se va intampla in viitor :) ).

Problemele au avut nivele de dificultate variate, rezolvarile lor necesitand observatii, idei si smenuri simple si/sau cunoscute, precum si idei noi, complicate si dificil de gasit. Imi era clar ca, desi durata concursului era de peste 8 zile si jumatate, ar fi fost foarte greu pentru cineva sa rezolve toate problemele. De aceea consider remarcabil rezultatul lui bogdan2412Bogdan-Cristian Tataroiu bogdan2412, care a reusit sa rezolve 24 din cele 25 de probleme (oare cat timp va dura pana va rezolva cineva si problema Optic , chiar si cu solutia publicata ? :) ) si a luat concursul in serios de la bun inceput, situandu-se pe unul din primele 2 locuri inca din prima zi de concurs.

In ceea ce priveste rezultatele celorlalti concurenti, eu le-as incadra in 7 (numar magic) categorii, in functie de numarul de probleme rezolvate:

  • cat.1: 23-25 probleme rezolvate => rezultat excelent
  • cat.2: 21-22 probleme rezolvate => rezultat foarte bun
  • cat.3: 16-20 probleme rezolvate => rezultat bun
  • cat.4: 11-15: probleme rezolvate => rezultat ok
  • cat.5: 7-10 probleme rezolvate => rezultat satisfacator
  • cat.6: 3-6 probleme rezolvate => mai are mult de lucrat si multe de invatat (dar are potential ;) )
  • cat.7: 0-2 probleme rezolvate => in trecere pe la concurs :)

Desi speram ca cei mai multi concurenti (45%-50%) sa se claseze in categoriile 1-5, o scurta privire aruncata asupra clasamentului arata ca lucrurile nu au stat astfel, aproximativ 75% dintre participanti situandu-se in categoriile 6 si 7 :( . Din acest punct de vedere, sunt usor dezamagit si am incercat sa ma gandesc care ar fi motivul pentru care cea mai mare parte a participantilor a rezolvat foarte putine probleme. Mi-au trecut prin minte 3 motive posibile:

  • Au luat mult prea la propriu ideea de "programare cu zambetul pe buze" si au tratat concursul cu o foarte mare lejeritate. Presupun ca aceasta reprezinta o posibilitate, insa atunci sunt curios ce anume i-a facut sa zambeasca in timp ce programau. Pe mine ma face sa zambesc un program bine scris care obtine 100 de puncte :)
  • Au rezolvat mai multe probleme, insa nu in proportie de 100%, iar sistemul de punctare "0 sau 100" nu i-a avantajat in aceasta privinta. Este posibil ca lipsa de experienta in ceea ce priveste concursurile de informatica sa nu permita unui participant sa isi gaseasca bug-urile din surse sau sa inteleaga motivele pentru care algoritmul sau nu functioneaza nici chiar intr-un interval de peste 8 zile si jumatate.
  • Nivelul de dificultate al problemelor a fost prea ridicat (ceea ce este evident pentru o parte dintre probleme) si nu au reusit sa gaseasca o solutie corecta sau care sa respecte constrangerile de timp si de memorie impuse.

Dintre cele 3 motive mentionate, primul se poate "rezolva" tratand concursurile mai serios, iar al doilea se poate "rezolva" programand mai mult si capatand experienta. A treia cauza posibila este cea care ma ingrijoreaza cel mai mult si este si cea mai dificil de "tratat" in mod individual (fara ajutorul cuiva). Pentru a ajunge sa poti rezolva probleme grele, in afara de a te stradui mai mult de unul singur, este important sa poti invata ceva si de la ceilalti. De aceea, am incercat sa scriu un articol cu solutiile problemelor cat mai detaliat, pentru a ajuta astfel pe toata lumea sa invete cateva (sau mai multe :) ) idei noi.

In perspectiva concursurilor viitoare, intrucat nu exista o reteta sigura pentru a ajunge in situatia de a iti veni (cine stie de unde :) ) ideile necesare pentru a rezolva o problema, pot doar sa va sugerez sa luati in considerare urmatoarele posibilitati:

  • ganditi-va singuri (fara a cere ajutor) la fiecare problema, pana cand gasiti solutia sau pana cand trece o anumita perioada de timp dupa care considerati ca nu puteti gasi solutia singuri (aici depinde de fiecare.. ar trebui sa fie cel putin 1-2 saptamani, dar mie mi s-a intamplat sa ma prind cum sa rezolv o problema si dupa 6 ani :) )
  • comunicati cu ceilalti membri ai comunitatii, schimband idei, discutand algoritmi si cerand sfaturi; si tineti minte sa ii ajutati si voi pe altii atunci cand veti avea posibilitatea
  • faceti pregatire cu un profesor care se pricepe; e foarte util pentru voi sa va ofere cineva informatii si cunostinte intr-un mod structurat (sa stiti ca asta nu e o reclama la adresa mea :) va spun doar ce mi se pare mie util si ce am facut si eu cand eram elev)
  • cititi cursuri de Computer Science, Graph Theory, Computational Geometry, Data Structures, String Algorithms, etc. si articole de cercetare de pe Internet; veti gasi multe concepte si idei foarte interesante, care s-ar putea sa va "lumineze" un pic mintea :)
  • participati la cat mai multe concursuri; chiar daca va prindeti cum sa rezolvati o problema, este important sa implementati corect si repede algoritmul de rezolvare

Daca are cineva si alte sugestii (sau nu este de acord cu unele din cele mentionate), il invit sa comenteze in sectiunea de comentarii.

Mult succes la concursurile urmatoare!

 Comentarii (2)

Categorii:

Incepe preONI 2008

domino
Mircea Pasoi
23 noiembrie 2007

Incepe o noua editie preONI, concursul cu premii mari si finala live care te pregateste pentru Olimpiada Nationala de Informatica.
Anul acesta avem vesti bune pentru elevii de gimnaziu si profesorii lor: preONI 2008 are o grupa separata pentru clasele V-VIII, si locuri rezervate la runda finala. In plus, avem premii mai multe si mai mari! ;)
Runda #1 se desfasoara Duminica, 25 noiembrie 2007, orele 09:00 - 13:00, afla mai multe pe pagina concursului.

 Comentarii ()

Categorii: stiri

Membri noi

Cosmin
Cosmin Negruseri
20 noiembrie 2007

Cum v-am mai zis si in alte posturi, suntem bucurosi ca am adaugat doi oameni noi in echipa. Ei sunt Adrian Airinei si Andrei Grigorean . Ambii au avut rezultate foarte bune la concursuri de programare ca elevi si au un numar impresionant de probleme rezolvate din arhiva infoarena. Recent i-am luat la intrebari. Vedeti aici ce a iesit:

Cum ai ajuns membru al siteului infoarena?
Adrian: Cand m-am calificat prima oara la ONI, in clasa a 10a, nu stiam nimic despre site-uri de pregatire pe net. Cei din lotul judetului Iasi vorbeau atunci despre infoarena cum ca ar fi un site foarte util cu probleme si concursuri. Cand am ajuns acasa, am cautat pe google infoarena, mi-am facut un cont si am rezolvat a+b si cmmdc.

Cum ai folosit acest site?
Adrian: In continuare, am gasit site-ul ca fiindu-mi de mare folos, in primul rand am rezolvat multe probleme. Forumul a fost iarasi foarte important, gaseam constant sfaturi utile acolo iar articolele m-au ajutat si ele.

De ce ai intrat in echipa infoarena? Ce iti propui sa faci ca membru al echipei?
Adrian: In calitate de membru al echipei imi propun sa incerc sa ajut cum pot comunitatea infoarena.

Cum ai ajuns membru al echipei infoarena?
Andrei: Dupa IOI, m-a intrebat Mircea intr-o noapte pe mess daca nu vreau sa ma implic mai mult in infoarena. I-am spus ca mi-ar placea, si m-a facut admin imediat.

Cum ai folosit acest site?
Andrei: De pe infoarena m-am pregatit cel mai mult pentru olimpiade, am rezolvat majoritatea problemelor din prima jumatate a arhivei. Am invatat cateva si de pe forum, citind posturile celor mai mari. Sectiunea de downloads mi-a fost de asemenea utila (am luat concursurile internationale de acolo). Si articolele m-au ajutat. La inceput cand nu ma prea prindeam de probleme, citeam solutiile oficiale de la diverse concursuri, iar apoi implementam. Desi ideal este sa te chinui pana cand iti vine ideea, la inceput e mult mai greu si uneori trebuie sa citesti solutiile. Tot pe infoarena am auzit de tine :)).

De ce ai intrat in echipa infoarena? Ce iti propui sa faci ca membru al echipei?
Andrei: Am intrat pe infoarena pentru a-i ajuta pe cei mai mici sa se pregateasca mai bine. Sper sa propun cateva probleme interesante la concursuri. De asemenea, cred ca pot spune si punctul de vedere al unuia care in urma cu doar cateva luni concura si se pregatea pe site. Atunci cand participi si nu organizezi, vezi lucrurile altfel.

Spor la munca baieti, suntem mandrii sa va avem printre noi!

 Comentarii (1)

Categorii:

Problema majoritatii

Cosmin
Cosmin Negruseri
18 noiembrie 2007

Cum blogul ar trebui sa fie orientat spre comunitatea infoarena am zis ca voi pune cate un post cu jmenuri de algoritmica din cand in cand. Sper sa va placa.

O problema clasica dar interesanta suna asa: Se dau n alegatori si fiecare voteaza pe unul dintre ei (toti alegatorii sunt in acelasi timp si candidati). Se stie ca unul dintre alegatori a primit cel putin n/2 + 1 voturi si acesta va obtine functia de presedinte. Gasiti un algoritm eficient pentru a determina viitorul presedinte.

Pentru a face putin mai interesanta problema, sa spunem ca sunt de ajuns n/3 + 1 voturi pentru a castiga alegerile si mai impunem restrictia ca exact unul dintre participantii la vot are mai mult de n/3 voturi.

Cum putem rezolva problema asta?

O solutie naiva, dar eficienta ar fi sa luam cateva nume votate aleatoare din sir. Cum castigatorul apare ca optiunea a multi votanti, daca alegem destul de multe valori din sirul optiunilor vom da cu probabilitate mare peste castigator. Cand alegem un nume aleator avem probabilitatea p > 1/3 ca am ales numele viitorului castigator. Deci daca alegem k valori vom avea un timp de executie de ordinul O(kn) pentru a verifica daca una dintre cele k valori e cea buna si probabilitatea de a gasi peresedintele mai mare de 1 - (1/3)k.

Alta idee vine de la faptul ca in sirul sortat, elementele de valori egale vor fi pe pozitii consecutive. Astfel numele presedintelui va aparea pe cel putin n/3 + 1 pozitii consecutive. Deci numele presedintelui va aparea sigur pe cel putin una din pozitiile n/3 sau 2n/3 din sir. Astfel putem folosi un algoritm de selectie pentru a gasi in O(n) elementele de pe pozitiile n/3 si 2n/3 si apoi in O(n) putem verifica care dintre acesti doi candidati au castigat.

Daca n nu depaseste un milion, putem la fiecare pas sa incrementam pentru candidatul votat x numerele a[x / 1000] si b[x % 1000]. Acum pentru a determina candidatul castigator, gasim valoarea p cu a[p] > n/3 + 1 si valoarea q cu b[q] > n/3 + 1, iar castigatorul va fi p * 1000 + q.

O solutie ar fi sa folosim un hash map ce mapeaza numele alegatorilor la numarul de voturi castigate. Solutia aceasta este eficienta dar foloseste O(n) memorie suplimentara pentru structura de date.

Alta solutie este sa facem grupuri de cate trei alegatori cu opinii diferite asupra castigatorului, care se cearta intre ei pana pica jos. Dupa ce am facut toate grupurile de cate trei, ne mai pot ramane maxim doua optiuni de candidati, in caz contrar mai gaseam un grup de trei votanti cu optiuni diferite. E clar ca dupa ce am eliminat grupurile de cate trei, va exista unul dintre alegatori cu optiunea pentru viitorul presedinte intre alegatorii negrupati, pentru ca acesta e votat de mai mult de n/3 ori. Asa ca pentru a gasi presedintele este de ajuns sa verificam cele doua optiuni ai alegatorilor ramasi negrupati. Va prezint codul solutiei:

Merge in O(n) ca timp si O(1) ca spatiu suplimentar.
x <- -1, counter_x <- 0;
y <- -1. counter_y <- 0;
pentru i = 1,n
  daca counter_x = 0 atunci x <- a[i], counter_x <- 1;
  altfel daca counter_y = 0 atunci y <- a[i]; counter_y <- 1;
      altfel daca x = a[i] atunci counter_x++;
      altfel daca y = a[i] atunci counter_y++;
          altfel
           // am gasit un grup de trei alegatori cu optiunile
           // x, y si a[i] pe care il eliminam
           // x != a[i], y != a[i] si x != y
           counter_x--, counter_y--;
verificam daca x sau y este elementul cautat.

Problema poate parea artificiala, dar reformulata in aceea de a gasi in mod eficient queriuri foarte frecvente(ce apar de n/k ori) pentru un motor de cautare devine mai interesanta si practica. Postul a fost inspirat din articolul "Problema majoritatii votului" ce l-am publicat in Ginfo, iar partea cu cearta intre alegatori din R. S. Boyer, J. S. Moore A Fast Majority Vote Algorithm

 Comentarii (4)

Categorii:

Joburi evaluate

Cosmin
Cosmin Negruseri
18 noiembrie 2007

Evaluatorul infoarena a rulat pana acum mai mult de o suta de mii de joburi. Inaintea inceperii concursului Happy Coding erau vreo 95000 de joburi, iar acum sunt peste o suta cinci.

Spor la munca in continuare!

 Comentarii (0)

Categorii:

Jocuri pe Web

Cosmin
Cosmin Negruseri
17 noiembrie 2007

Anul trecut am jucat cateva jocuri web misto ce aveau o realizare simpla, dar te prindeau. Ideea lor e ca trebuie sa parcurgi niste pagini web ca sa ajungi pana la pagina finala. Pe fiecare pagina este cate un puzzle pe care daca il rezolvi poti sa treci la pagina urmatoare. Cele pe care le-am vazut eu sunt Hacker Puzzle , From A to craZy si unul mai complex care mi-a placut foarte mult Funny Farm . Ultimele doua siteuri sunt facute de Igor Naverniouk, un tip din Canada, si el din lumea concursurilor de programare, cu care mai discut din cand in cand. Pentru ambele jocuri el oferea ceva premii simbolice pentru a atrage vizitatori. Ele au aparut pe prima pagina a digg , lucru care mi se pare a fi o dovada de succes. Puzzleurile sunt foarte bine facute si Igor zicea ca partea de programare a luat mai putin decat partea de creere a intrebarilor. Dupa ce a aparut siteul pe digg a trebuit sa faca si cateva restructurari in cod ca sa poata primi un trafic neasteptat de mare. Funny Farm avea cateva reclame Google si eram curios cati bani a reusit sa scoata din un joc care mie mi se parea foarte popular si interesant. Raspunsul lui a fost unul sub asteptari, a zis ca a facut in jur de doua mii de dolari, care nu e o suma asa mare cand e comparata cu salarul pe luna a unui programator mediu din state sau Canada.

Totusi stiu si de jocuri mai banoase ca funny farm cum ar fi Tower of Defense pe care autorul castiga din reclame opt mii de dolari pe luna.

Moda jocurilor de tipul Hacker Puzzle a aparut si in Romania. Alex Brie face reclama pe blogul sau la Brain Tower , un joc cu potential, dar la care mi se pare ca mai are de lucru. Problemele nu sunt chiar cele mai interesante, si lipseste satisfactia de la final, in celelate jocuri te puteai semna intr-un guestbook sau luai un premiu. Dar din cate mi-a zis Alex, mai vrea sa lucreze putin la el, si pentru inceput arata bine. Multa bafta!

Update Alex a bagat de ceva vreme si un guestbook pe site.

Cati dintre voi aveti siteuri cu reclame? Cum va merg?

 Comentarii (1)

Categorii:

Muzica

Cosmin
Cosmin Negruseri
17 noiembrie 2007

Cateodata imi place sa ascult muzica in timp ce programez. In timpul liceului stiam inceputul melodiilor de la Deep Purple in ordine alfabetica, pentru ca asa erau in winamp, si cand se apropia sfarsitul uneia incepeam sa fredonez urmatoarea. Acum mi s-au schimbat putin gusturile si in timp ce lucrez imi place Daft Punk. Au o muzica interesanta, cu versuri simple fara intreruperi bruste de ton si asta e bine pentru concentrare.

Voi ce muzica ascultati cand programati?

Apropo de Daft Punk, v-am pus un video bestial de pe youtube, la inceput e mai lent dar pe la 2:00 incepe sa fie interesant.

Ideea e destul de misto, dar nu toate melodiile sunt la fel de reusite.

 Comentarii (25)

Categorii:
Vezi pagina: 12345... 252627282930 31323334353637383940 (394 rezultate)