Echipa infoarena vă mulţumeşte pentru sprijinul acordat şi în 2009 prin direcţionarea a "2%" din impozitul pe venit! Înseamnă foarte mult pentru noi ajutorul şi implicarea directă a comunităţii - e o dovadă că munca noastră are un impact crescând in rândul utilizatorilor!

În 2009 fondurile primite prin sistemul "2%" au însumat 7.892 RON, ceea ce reprezintă o contribuţie cu peste 70% mai mare decât cea din 2008, când am înregistrat un total de 4.620 RON. Creşterea spectaculoasă ne bucură cu atât mai mult cu cât strângerea fondurilor necesare pentru organizarea concursurilor şi activităţilor infoarena a reprezentat întotdeauna o dificultate. Ajutorul vostru este deosebit de important deoarece bugetul infoarena este format din banii primiţi prin sistemul "2%", prin sponsorizari şi prin donaţii. În ultimii ani, sumele obţinute prin programul "2%" au fost printre cele mai importante două contribuţii primite anual de Asociaţia infoarena.

Faptul că programul "2%" prevede confidenţialitatea contribuabililor ne-a împiedicat să obţinem o listă nominală a acestora, însă le mulţumim tuturor cu sinceritate şi ne bucurăm că ne-au fost alături!

În acest weekend are loc AI-MAS Winter Olympics, un mare eveniment destinat inteligenţei artificiale organizat de laboratorul AI-MAS din cadrul Universităţii Politehnice din Bucureşti. Pentru a înţelege mai bine despre ce e vorba, vă invităm să citiţi prezentarea evenimentului:

Vroiam pe vremea cand postam pe blog mai des sa scriu un post despre avantaje si dezavantaje sa faci universitatea in afara tarii.

Recent a aparut un thread pe forum pe acea tema si am rugat cativa fosti olimpici sa comenteze pe threadul respectiv.

Printre altii, au participat la discutie Mihai Patrascu (researcher AT&T pe algoritmica si structuri de date, 2 medalii de aur si una de argint la IOI), Radu Grigore (doctorand UCD Dublin), Mugurel Ionut Andreica (medaliat cu argint la ioi, bronz la finala ACM ICPC, proaspat doctor la Poli Bucuresti), Stefan Ciobaca (argint la IOI, fost intern Microsoft, masterand MPRI, doctorand ENS Cachan), Octavian Costache (mare blogger, antreprenor si senior software engineer la Google), Catalin Francu (medalie de argint la IOI, a terminat facultatea la MIT, fost inginer Google, creator dex online).

Cu atata materie cenusie concentrata intr-un loc a iesit o discutie foarte interesanta pe care va recomand sa o cititi si la care va rog sa contribuiti.

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.