Pe data de 20 decembrie a avut loc cea de-a doua rundă a concursului Algoritmiada 2010. Abia intraţi în vacanţă, concurenţii şi-au mai amânat câteva zile excursiile la munte pentru a participa la o nouă rundă a celui mai prestigios concurs infoarena.

Să aruncăm o privire asupra statisticilor acestei runde:

În primul rând, observăm o scădere a numărului de participanţi faţă de prima rundă. Din statistici se mai observă o creştere a punctajelor faţă de runda anterioară, ceea ce denotă fie că subiectele au fost ceva mai uşoare, fie că participanţii au fost mai bine pregătiţi. :) Uitându-ne atent şi la clasament, vom vedea că subiectele propuse au reuşit să-i departajeze bine pe concurenţi.

Elevii de gimnaziu au avut de înfruntat în această rundă un set de probleme ceva mai dificil, având o problemă comună cu clasele 11-12. Cu toate acestea, •Gheorghe Mihai a reuşit să obţină 230 de puncte cu care şi-a asigurat primul loc. Locul al doilea i-a revenit lui •Anghel Daniel care a obţinut 150 de puncte, iar pe locul al treilea s-au situat •Filimon Marta Diana, •liana tucar şi •Murtaza Alexandru, toţi cu câte 140 de puncte.

Prima runda a concursului Algoritmiada a avut loc pe 22 noiembrie, marcând astfel debutul celei de-a doua ediţii a celei mai importante competiţii organizate de infoarena. Anul acesta am început concursul mai devreme cu gândul de a vă oferi 4 runde de calificare în loc de 3. Sperăm ca această decizie să ne ajute la obţinerea unui clasament general mai exact, în urma căruia să putem selecta cei mai bine pregătiţi concurenţi pentru finală.

După cum v-am obişnuit până acum, vom arunca o privire asupra statisticilor acestei runde:

Se observă o scădere semnificativă a numărului de participanţi faţă de anul trecut. O justificare posibilă a acestui fenomen este faptul că Algoritmiada şi-a creat un "brand", rămânând cu noi doar acei tineri care au găsit în concursul nostru ceea ce căutau. Sperăm, totuşi, că aceştia se vor dovedi temeinici, luptându-se pentru şansa lor până la sfârşitul competiţiei.

Voi reformula problema in termeni de grafuri pentru a usura intelegerea explicatiei:

Se da un graf complet cu 6 noduri in care fiecare muchie este colorata sau in rosu, sau in albastru. Spunem ca un triplet de noduri (a, b, c) este monocromatic daca muchiile (a, b), (b, c) si (a, c) au acceasi culoare. Se cere sa se demonstreze ca exista cel putin 2 triplete monocromatice.

Recent am aflat urmatoarea problema draguta de la •Cosmin Negruseri:

Sa se demonstreze ca intr-un grup de 6 persoane, exista cel putin un subgrup de 3 persoane in care toti membri subgrupului se cunosc intre ei sau niciun membru nu ii cunoaste pe ceilalti doi.

Eu va propun urmatoarea varianta modificata:

Sa se demonstreze ca intr-un grup de 6 persoane, exista cel putin doua subgrupuri de 3 persoane in care toti membri subgrupului se cunosc intre ei sau niciun membru nu ii cunoaste pe ceilalti doi.

Astept solutiile voastre la adresa andrei.grigorean at gmail.com

Că tot se apropie alegerile prezendiţiale, avem veşti bune pentru voi: infoarena şi-a ales deja preşedintele :) El este: •Gheorghe Cosmin!

Cosmin a preluat ştafeta de la •Cristian George Strat, care a fost preşedintele infoarena încă din 2003. Sub mandatul lui Cristi s-au realizat multe lucruri, dar aşa cum a spus chiar el, cel mai important este faptul că infoarena este un proiect viu! În jurul site-ului şi al Asociaţiei v-aţi adunat voi, tinerii pasionaţi de informatică din România. Acest lucru ne dă încredere ca infoarena va exista pentru multe generaţii de acum încolo şi că va rămâne o sursă importantă în pregătirea voastră, a viitorilor specialişti IT ai României.

Începând cu anul acesta, conducerea infoarena este aleasă în fiecare an conform procedurii descrise aici. Noi sperăm că acest lucru să asigure continuitate şi, în acelaşi timp, o infuzie de idei noi şi de energie în proiectele întreprinse de echipa infoarena.

La primele alegeri "prezidenţiale" infoarena, Cosmin a câştigat mandatul în unanimitate. El ne-a convins prin seriozitate şi prin iniţiativă pe tot parcursul anului trecut.

Cosmin a ales 3 vicepreşedinţi care sunt responsabili de cele 3 mari "direcţii" infoarena:

Cum numarul de rezolvari atat bune cat si rele a fost mare la problema anterioara, va mai zic o problema cu statistici de ordine pe care am auzit-o de la Mihai Patrascu.

Se dau n numere intregi scrise pe disc. Se cere sa se detemine mediana lor in timp O(n), citind fiecare numar de pe disc de O(1) ori si folosind O(sqrt(n)) memorie totala. Mediana unui sir de numere cu n elemente e elementul de pe pozitia n/2 din sirul rezultat in urma sortarii sirului initial.

Ca de obicei imi puteti trimite solutii pe adresa cosminn at gmail.com

Am gasit problema in cartea "Introduction to Algorithms: A Creative Approach" de Udi Manber. Udi e VP of engineering la Google si daca stiti de suffix arrays, el a publicat o metoda eficienta pentru a determina LCP (longest common prefix) a doua sufixe. Cartea imi place mai mult decat Cormen-ul pentru ca partea de teorie e orientata mai mult spre intelegerea lucrurilor decat spre demonstratii matematice stufoase si pe langa asta fiecare capitol are foarte multe probleme interesante la sfarsit. Eu cred ca problemele sunt esentiale cand inveti un subiect tehnic, pentru ca intelegi bine ideile din un domeniu cand esti obligat sa le aplici in contexte diverse.

Pana sa vad cerinta din cartea respectiva credeam ca problema selectiei celor mai mici k numere din un stream se poate face doar in O(n log k) daca esti obligat sa folosesti O(k) memorie, dar citind-o mi-am dat seama ca nu e greu sa scoti o solutie in O(n) timp si O(k) spatiu. E o diferenta mare intre a sti ca o problema e rezolvabila sau nu :), de aceea munca de cercetare e foarte dura.

Daca tot am inceput sa scriu, am o problema draguta ce s-ar potrivi la un interviu tehnic:

Se da un stream de n numere intregi. Sa se gaseasca un algoritm ce determina cele mai mici k numere din acest stream in timp O(n) si memorie O(k). Streamul are urmatoarele doua metode int getNext() si bool hasNext().

Ca de obicei, puteti trimite solutiile pe adresa cosminn at gmail.com

Nu am mai scris de mult si v-am ramas dator cu solutia problemei Monede, daca ati uitat cerinta, puteti citi enuntul:

Pe o masa dreptunghiulara punem monede de raza 1 pana cand nu mai putem adauga o noua moneda fara ca ea sa se suprapuna cu altele. Unele monede pot fi partial inafara mesei. Daca numarul total de monede este n, sa se demonstreze ca toata suprafata mesei poate fi acoperita de 4n monede de raza unu care se pot suprapune.

Daca inlocuim cele n monede de raza unu cu monede centrate la fel dar care au raza doi, ele vor acoperi total masa, pentru ca in configuratia initiala, orice punct neacoperit era la o distanta mai mica decat unu de o moneda (in caz contrar am fi putut plasa inca o moneda de raza unu centrata in punctul respectiv).
Asta inseamna ca, cu n monede de raza unu putem acoperi un dreptunghi cu aria un sfert din aria mesei. Cu patru astfel de dreptunghiuri acoperite, putem obtine o configuratie a 4n monede ce acopera intreaga masa.

Singurul rezolvitor a fost Andrei Dragus, felicitari.

După cum o parte din voi aţi aflat la finala Algoritmiada, echipa infoarena s-a îmbogăţit cu un nou membru: Marius Stroe. Pentru cei care nu au fost acolo, Marius a primit din partea echipei infoarena un mini-tort cu cifra 0 pe post de lumânare. Explicaţia a fost că are 0 ani de infoarena şi este cea mai nouă achiziţie a echipei.

În ciuda acestui fapt Marius are deja multe contribuţii în proiectele infoarena în calitate de voluntar. Puteţi vedea acest lucru chiar pe pagina sa de profil. Îmi place cum şi-a enumerat Marius contribuţiile cele mai importante pe pagina sa de pe infoarena. Aş vrea să văd mai mulţi voluntari că îşi actualizează profilul cu realizările lor în cadrul comunităţii.

Marius a fost invitat în echipa infoarena tocmai datorită contribuţiilor sale consistente. El este dovada că oricine poate ajunge în echipa infoarena în urma unei implicări constante şi productive în proiectele iniţiate de noi. O vorbă mai veche spune că orice soldat are în raniţă bastonul de mareşal :) Păstrând proporţiile, vreau să spun că oricare dintre voi poate fi promovat în echipă pe această cale: realizări importante pentru comunitate.