Blog infoarena

Problema saptamanii

Cosmin
Cosmin Negruseri
11 noiembrie 2007

A venit din nou timpul pentru problema saptamanii. Va propun o problema interesanta ce mi-a zis-o colegul meu de clasa Radu Cebanu acum vreo trei ani.

Se dau doua puncte A si B. Exista doua drumuri(curbe infinit de subtiri) intre ele si aceste drumuri au proprietatea ca doua mobile punctiforme legate cu o sfoara de lungime 10 m pleaca din A si ajung in B fara a rupe sfoara. Nu exista vreo restrictie asupra miscarii mobilelor, decat ca ele se deplaseaza fiecare pe unul din drumuri. De exemplu viteza lor poate fi diferita, ele pot sa se miste chiar in sensul opus de la B la A, sau un mobil poate sta pe loc in timp ce al doilea se misca. Avem doi roboti in forma de discuri de raza 5 metri, unul cu centrul in A si celalalt cu centrul in B. Intrebarea este daca acesti roboti pot folosi cele doua drumuri pentru a ajunge din A in B si respectiv din B in A, fara a se ciocni. Robotii se misca fiecare cu centrul discului pe unul din drumuri.

Va reamintesc ca puteti folosi formul pentru clarificari ale enuntului, si mesajele private pentru solutii complete. Have fun!

 Comentarii (0)

Categorii: potw probleme

CAPTCHAuri pentru matematicieni

Cosmin
Cosmin Negruseri
11 noiembrie 2007

Sunt interesante CHAPTCHAurile bazate pe matematica. Ele pe langa ca pot diferentia intre oameni si calculatoare, pot separa si oameni pe diverse nivele de abilitati matematice.

Cateva exemple:

2 + 2 = ?

 Comentarii (0)

Categorii:

Human Computation

Cosmin
Cosmin Negruseri
10 noiembrie 2007

In cel mai tare tech-talk de pe google video (350.000 de vizionari), Luis Von Ahn ne prezinta o metoda ingenioasa de a folosi oameni pentru a rezolva problemele dificile pentru un calculator. Metoda aleasa e inspirata din o practica a hackerilor. Acestia ii pun pe utilizatorii unui site deochiat sa scrie ce text contine un CAPTCHA inainte de a vedea urmatoarea imagine. Ei reusesc astfel sa treaca de protectia siteurilor de mail, obtinand astfel o gramada de casute din care pot trimite spam. Acum ii respect mai mult pe indivizi chiar daca nu respect motivatia lor.

Google a cumparat cu bani grei idea lui Luis si a implementat-o in Google Image Labeler . Poate de acuma il veti juca in loc de minesweeper :).

Aveti videoul aici. Dureaza o ora, daca nu aveti atata timp uitati-va neaparat la primele 15 minute ca nu trebuie ratat.

 Comentarii (1)

Categorii: video

Comentarii

Cosmin
Cosmin Negruseri
10 noiembrie 2007

Mircea a bagat un feature nou. De acum avem un count la numarul comentariilor de la fiecare post, ca toate blogurile respectabile, nu vivi? ;)

 Comentarii (2)

Categorii:

Noutati

Cosmin
Cosmin Negruseri
07 noiembrie 2007

Cativa reprezentanti Google au fost saptamana trecuta la Universitatea Bucuresti si la Politehnica. Au tinut niste seminarii si o serie de interviuri pentru internshipuri sau joburi. Puteti citi mai mult aici

Trei studenti romani au participat saptamana trecuta la finala concursului TopCoder Collegiate Challenge desfasurata la Disney Land. Ei au fost Mircea Pasoi (domino) la concursul de algoritmica, Vlad Dumitriu (vlad_D) la cel de webdesign si Lucian Lazar (Luca) la concursul de software design. Felicitari pentru calificarea "onsite"! Mircea a reusit un rezultat foarte bun pentru Romania, calificandu-se in primii opt pe partea de algoritmi. Ultima data cand un roman reusise aceasta performanta a fost in 2004.

Concursul Campion este o noua editie, iar anul acesta, datorita eforturilor lui Marius Andrei si Liviu Valsan , are un nou sistem de trimitere a solutiilor. Astfel sursele submitate sunt validate, fiind rulate mai intai prin niste teste simple. Acest sistem este similar cu cel da la Olimpiada Internationala si face ca unele greseli frecvente ale concurentilor care uitau detalii mici dupa un concurs intens sa fie corectate. Sa speram ca introducerea sistemului la concursul Campion este doar primul pas si ca el va fi folosit cat mai curand la olimpiedele judetene si nationale.

Infoarena organizeaza a patra editie a concursului Happy Coding. Ideea initiala a concursului era sa fie unul in care se programeaza cu zambetul pe buze, fara presiunea din majoritatea concursurilor. Astfel evaluatorul solutiilor este pornit in timpul concursului, iar durata este mai lunga decat cea standard de cinci ore. Ii multumim lui Mugurel Andreica, care propune si de aceasta data problemele. Puteti citi mai mult despre concurs aici

Zilele astea infoarena a ajuns la peste 7000 de membrii inregistrati!

 Comentarii (0)

Happy Coding 2007

domino
Mircea Pasoi
06 noiembrie 2007

Sunteti invitati sa participati la o noua editie a popularului (speram :) ) concurs Happy Coding. Perioada de desfasurare a concursului va fi sambata, 10 noiembrie, ora 10:00 - duminica, 18 noiembrie, ora 24:00. Cititi mai multe pe pagina concursului.

 Comentarii ()

Categorii: stiri

Intrebare scurta

Cosmin
Cosmin Negruseri
04 noiembrie 2007

Cat e complexitatea ca timp a Ciurului lui Erastotene? Motivati raspunsul.

Update: E interesant ca nu stim complexitatea unui algoritm pe care il invatam in clasa a 5-a. Ne gandim mai intai ca algoritmul trebuie sa fie mai rapid decat O(n^2), pentru ca facem n pasi si fiecare pas e mai eficient decat o parcurgere a celor n numere. Daca ne uitam mai atent, numerele sunt parcurse pe sarite si numarul de operatii e n/2 + n/3 + n/4 + ... + n/n = n(1/2 + 1/3 + ... + 1/n). Sirul 1 + 1/2 + ... + 1/n - log\ n este convergent, astfel deducem ca ciurul lui eratostene are complexitatea mai mica decat O(n\ log\ n). Nu am folosit faptul ca in algoritm noi vom marca doar pornind de la valori prime, sarind peste multe valori, astfel numarul de operatii al algoritmului e n (1/2 + 1/3 + 1/5 + ... + 1/pk) unde pk e cel mai mare numar prim mai mic decat n. Sirul 1 + 1/2 + 1/3 + 1/5 + ... + 1/pk - ln\ ln\ n e convergent dupa cum putem citi aici . Astfel complexitatea algoritmului Ciurul lui Erstotene este O(n\ log\ log\ n).

Am o alta intrebare pentru voi: Stiti cat e complexitatea algoritmului lui Euclid?

 Comentarii (7)

Categorii: potw probleme

Blogurile Microsoft

Cosmin
Cosmin Negruseri
04 noiembrie 2007

Cautam de ceva vreme bloguri interesante legate de programare, si am dat la un moment dat peste blogs.msdn.com si peste studentclub.ro. Primele sunt bloguri ale unor angajati Microsoft si urmatoarele sunt bloguri ale unor studenti romani, membrii de organizatii studentesti asociate Microsoft.

Pe ambele platforme apar destul de des stiri despre noile si fascinantele tehnologii M$. Pe blogs.msdn.com sunt si multe posturi interesante si inteleg ca, din cand in cand, oamenii trebuie sa isi promoveze tehnologiile si chestiile la care muncesc. Ceea ce nu inteleg este promovarea aceluiasi gen de subiecte propagandistice de catre studenti. Cei care sunt interesati de asemenea chestii, oricum le pot lua direct de la sursa. Nu inteleg inca aceasta entuziasmare la tot ce e nou, si mi se pare o incercare nereusita de a parea la fel de cool ca fratii lor mai mari care lucreaza la M$.

Nu toate blogurile, sau toate posturile de pe studentclub sunt rele, dar multe care le-am vazut m-au lasat cu o impresie proasta. Exista si posturi foarte bune cum ar fi acesta in care doi frati povestesc experienta lor la internship la Microsoft, din vara aceasta. Daca va uitati atent ii vedeti in poza pe Mircea Pasoi si pe Tiberiu Florea , care au fost si ei la internship la M$ peste vara.

 Comentarii (1)

Problema saptamanii (Solutie)

Cosmin
Cosmin Negruseri
04 noiembrie 2007

Problema a fost rezolvata de Mihai Patrascu, Radu Cebanu, Adrian Vladu, Marius Buzea, Marius Andrei, Adrian Carcu, Giurgea Mihnea, Liviu Ciortea, Adrian Sandor, Razvan Alecsandrescu, Igor Naverniouk si Csaba Patcas.

La prima vedere pare nerezolvabila, dar de fapt are o solutie destul de simpla. Ea se bazeaza pe faptul ca multimea ZxZ e numarabila. Putem verifica in fiecare secunda T cate o coordonata X0 + Y * T, parcurgand perechile (X0, Y) in spirala. Vom ajunge la un T1 pentru care teroristul este la locatia X0 + Y * T1. Inca nu am rezolvat problema, pentru ca pot exista mai multe perechi de numere pentru care teroristul sa fie la locatia X0 + Y * T1 in momentul T1. Prin faptul ca am gasit pozitia teroristului la un moment fixat T1, am redus problema la una noua determinata de parametrii X0', Y' in care in care nu il stim pe Y dar X0' = X0 + Y * T1. Aceasta subproblema se poate rezolva usor.

Alta problema cu teroristi ce mie imi place foarte mult este Lesbulan , ca dovada am si propus-o la concursul Bursele Agora.

Probleme cu tema similara sunt si Soarecele si pisica (medie ca dificultate, de pe Lista lu' Francu), Tom & Jerry (grea, nu a facut-o nimeni din cate stiu eu cand a propus-o Mugurel la lot) si tunnels (foarte grea, nu a facut-o nici o echipa in finala ACM ICPC 2006), smuggler (de pe rec.puzzles.org cu solutie). Daca sunteti curiosi de rezolvari, putem sa le discutam pe forum.

 Comentarii (3)

Categorii: potw probleme

Photosynth

Cosmin
Cosmin Negruseri
03 noiembrie 2007

Un prieten imi zicea recent ca pun prea multe referinte la Google in posturi, si ar trebui sa adaug referinte la Microsoft ca blogul sa fie mai obiectiv (el lucreaza pentru M$).

Pentru a mai echilibra scorul, am pus videoul de mai jos cu o demonstratie impresionanta a unei aplicatii Microsoft. Demonstratia a avut loc tot la TED talks. Cred ca visul oricarui programator este sa lucreze la un astfel de proiect revolutionar.

 Comentarii (1)

Categorii: video
Vezi pagina: 12345... 262728293031 323334353637383940 (393 rezultate)