Î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:

Te-ai întrebat vreodată pentru ce înveţi toţi aceşti algoritmi? Olimpiadele sunt fun, concursurile de informatică îţi dau adrenalină, dar asta nu e totul! Cunoştinţele pe care le dobândeşti te pregătesc pentru a ataca cele mai dificile probleme nerezolvate din Computer Science.
AI-MAS Winter Olympics este un eveniment dedicat Inteligenţei Artificiale. Organizat de laboratorul AI-MAS al Universităţii Politehnica Bucureşti, acest eveniment vrea să îţi arate că inteligenţa artificială nu este numai în filme SF sau în laboratoare avansate, ci este ceva care există şi care deja îţi face viaţa mai uşoară. Mai mult de atât, este o direcţie pe care o poţi urma şi în care pregătirea ta de olimpic poate face o diferenţă!
Componenta principală a evenimentului este Workshop On Real Life Applications, o serie de prezentări în care companii mari îţi vor arăta cum inteligenţa artificială le oferă un avantaj competitiv. Ingineri din partea Facebook vin pentru prima oară în România, alături de membri ai Academiei Române şi reprezentati ai unor companii importante: IBM, BitDefender, Thales, Kaspersky, Ropardo. Suntem siguri că subiectele discutate îţi vor deschide apetitul pentru inteligenţă artificială.
În plus vei putea vizita AI-MAS Village, un loc cu aplicaţii interesante care folosesc tehnici de AI, cu roboţi de tip line-follower şi alţii mai inediţi. În pauzele workshop-ului vom proiecta finala competiţiei Crafting Quest -- meciuri AI vs AI între agenţi inteligenţi. Vei putea discuta cu vorbitorii de la workshop, cu companiile prezente şi cu alţi pasionaţi de acest domeniu.
Evenimentul are loc sâmbătă, 27 februrarie, în holul EC al Facultăţii de Automatică şi Calculatoare, UPB. Pentru a participa este nevoie să te înregistrezi pe site-ul AI-MAS Winter Olympics. Evenimentul se termină în jurul orei 18.00 şi este urmat de un after-party cu karaoke.
Te aşteptăm!

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, •Mihai Gheorghe a reuşit să obţină 230 de puncte cu care şi-a asigurat primul loc. Locul al doilea i-a revenit lui •cont cu nume gresit sau fals care a obţinut 150 de puncte, iar pe locul al treilea s-au situat •FII Filimon Marta Diana, •liana tucar şi •Murtaza Alexandru, toţi cu câte 140 de puncte.

La clasele 9-10, primul clasat a fost •Serban Andrei Stan cu 245 de puncte, fiind urmat de •Cezar Mocan cu 230 de puncte si •Adrian Budau cu 200 de puncte.

La grupa 11-12, punctajele au fost net mai mari decât în runda precedentă şi acest lucru s-a datorat unui set de probleme mai uşor. Primul loc a fost ocupat de •Ionescu Victor Cristian cu 260 de puncte, fiind urmat de un grup de 4 elevi: •perticas catalin, •Tache Alexandru, •Cazacu Alexandru şi •Andrei-Bogdan Antonescu, toţi cu câte 220 de puncte.

La grupa de studenţi, primul clasat a fost •Teodorescu Andrei-Marius care a reuşit să obţină cel mai mare punctaj din această rundă: 280 de puncte. În urma lui s-au clasat •Mugurel-Ionut Andreica cu 250 de puncte şi •Jurca Razvan cu 180 de puncte.

Runda a fost, din păcate, marcată de câteva probleme de natură tehnică. În primul rând, în ultima oră de concurs, a căzut conexiunea la internet a calculatorului pe care se află evaluatorul timp de 20 de minute. Acest lucru, le-a creat concurenţilor neplăceri majore, deoarece nu au mai putut vedea în timp util dacă soluţiile trimise de ei au întâmpinat probleme la compilare, iar rezultatele la evaluarea parţială au apărut cu întârziere. Tot din acest motiv, evaluarea a durat mai mult timp, rezultatele finale nefiind disponibile chiar la finalul concurslui. În al doilea rând, site-ul s-a comportat destul de prost în ultimele minute ale concursului. Pentru a evita o înrăutăţire a lucrurilor, comisia a luat decizia de a face rezultatele publice doar după ce toate sursele au fost evaluate. Cu toate acestea, au exitat reclamaţii cum că unii concurenţi n-au putut să mai submiteze soluţiile terminate în ultimele minute. Ne pare rău că au apărut astfel de probleme şi vom încerca să le remediem pe viitor. Probleme de natură ştiinţifică nu au fost sesizate, comisia pregătind subiectele cu rigurozitatea obişnuită. Doar articolul cu soluţii s-a lăsat ceva mai mult aşteptat faţă de runda precedentă, dar acest lucru s-a strecurat neobservat, probabil concurenţii au aşteptat cu mai mult interes sărbătorile decât soluţiile oficiale. :)

Următoarea rundă va avea loc cel mai probabil în a doua jumătate a lunii februarie. Am luat această decizie, pentru a evita perioada algomerată pentru studenţi din timpul sesiunii. Mai mult, elevii de liceu vor avea o ocazie în plus să-şi verifice cunoştinţele înainte de Olimpiada Judeţeană ce va avea loc la începutul lunii martie.

În încheiere, echipa infoarena vă doreşte sărbători fericite şi un an nou cu cât mai multe realizări deosebite!

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.

Judecând după rezultate, gradul de dificultate a fost, în general, unul potrivit, obţinându-se o distribuţie bună a punctajelor. În fruntea clasamentului de la gimnaziu, avem o surpriză: •liana tucar reuşind să obţină punctajul maxim (singurul din această rundă). Ne bucură să constatăm că sunt şi fete interesate de performanţă în informatică. Felicitări, la cât mai multe rezultate frumoase pe viitor! Pe podium au mai urcat •Eugenie Daniel Posdarascu şi •Mihai Gheorghe, ambii cu câte 230 de puncte.

La grupa 9-10, runda a fost adjudecată clar de •Adrian Budau cu 290 de puncte, fiind singurul care a reuşit să rezolve aproape corect problema vrejuri. El a fost urmat de •Serban Andrei Stan (200 de puncte) şi •Gavrila Vlad (170 de puncte).

La grupa 11-12 au fost punctaje mai mici ca la celelalte grupe, fapt care îl punem pe seama absenţei unei probleme mai accesibile. Vom încerca să remediem acest lucru începând de runda viitoare. La aceasta grupă, primul clasat a fost •Andrei-Bogdan Antonescu cu 210 puncte, fiind urmat de •Andrei Misarca cu 170 de puncte şi •Andrei Poenaru cu 120 de puncte.

La grupa de studenţi, în fruntea clasamentului îl găsim pe veteranul infoarena •Mugurel-Ionut Andreica cu 260 de puncte. El este urmat de un grup compact format din 9 studenţi: •Duta Vlad, •Paul Diac, •UPB - Andrei Homescu, •Tudose Vlad, •Mihai Leonte, •Florea Mihai Alexandru, •Marin Radu, •Flaviu Pepelea şi •Teodorescu Andrei-Marius, toţi cumulând câte 200 de puncte. La această grupă mai notăm un rezultat remarcabil: 38 de participanţi au reuşit să depăşească pragul de 100 de puncte.

Judecând după punctajele apropiate din clasament, se pare că vom avea o luptă acerbă pentru calificare şi în acest an. Cu toate acestea, cei care au obţinut rezultate mai puţin bune nu trebuie să vă simţiţi descurajaţi deoarece în trei runde nu este dificil să recuperaţi diferenţa care vă separă de plutonul fruntaş.

Pe partea ştiinţifică fost sesizată o singură imperfecţiune: testele de la problema studenţi nu au fost suficient de bine construite şi astfel, unele soluţii incorecte au obţinut 100 de puncte. Problema a fost corectată imediat, unul din teste fiind înlocuit când problema a fost adaugată în arhiva de probleme. În rest, comisia ştiinţifică s-a mobilizat exemplar, reuşind să organizeze un concurs interesant şi atractiv. Site-ul s-a comportat şi el bine pe aproape toată durata concursului, cu mici excepţii la final, când a cedat puţin presiunii numărului mare de utilizatori nerăbdători să-şi vadă rezultatele.

În vederea selectării concurenţilor pentru finală, vă recomandăm să vă completaţi/updataţi profilul cu date despre clasa/anul în care sunteţi, precum şi informaţii despre instituţia de învăţământ. De fapt, am fi bucuroşi dacă toţi utilizatorii şi-ar completa profilul, aceasta fiind una din modalităţile prin care putem să ne cunoaştem între noi. Exemple de profile completate puteţi găsi la mai toţi membrii echipei infoarena.

Închei prin a vă reaminti că în acest weekend are loc Olimpiada Balcanică de Informatică pentru Juniori şi Seniori. Membrii echipelor ce reprezintă România la această competiţie sunt, bineînţeles, utilizatori activi infoarena, unii dintre ei reuşind performanţe deosebite chiar în această rundă de concurs. Ei sunt: •Gavrila Vlad, •Radu Voroneanu, •Petcu Marius, •Mihai Gheorghe, •Andrei Parvu, •Serban Andrei Stan şi •Savin Tiberiu, •perticas catalin. Le dorim mult succes şi să obţină medalii cât mai strălucitoare!

Vouă cum vi s-a părut concursul? Ce a mers bine şi ce a mers rău pentru voi? Este important pentru noi să ne lasaţi impresiile voastre despre concurs, pentru a reuşi o organizare şi mai bună în continuare.

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.

Solutia mea este urmatoarea: Numarul total de triplete este egal cu 20. Voi incerca sa demonstrez ca pot fi maxim 18 triplete care nu sunt monocromatice. Pentru a numara cate astfel de triplete sunt, putem sa folosim jmenul de la problema Color. Pentru fiecare nod vom inmulti numarul de muchii albastre incidente cu numarul de muchii rosii incidente. Adunand aceste valori si impartind la 2, obtinem numarul de triplete nemonocromatice. Va voi lasa pe voi sa demonstrati aceasta afirmatie :P. Numarul maxim de triplete nemonocromatice se obtine atunci cand pentru fiecare nod in parte produsul dintre numarul de muchii albastre si rosii este cat mai mare. Cum gradul unui nod este egal cu 5, rezulta ca produsul poate fi maxim 6. Deci, numarul maxim de triplete ce nu sunt monocromatice este 6 * 6 / 2 = 18.

Rezolvarea poate fi generalizata pentru grafuri mari.

Solutii corecte constructive au fost oferite de: Alex Mosoi, Andrei Dragus, Daniel Anghel.

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 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:

• Algoritmiada -- •Paul-Dan Baltescu
• Content (arhivă, concursuri online, articole) -- •Stefan Istrate
• Development -- •Bogdan-Cristian Tataroiu

Bogdan, Ştefan şi Paul s-au remarcat prin contribuţii substanţiale la infoarena încă de când s-au alăturat echipei.

Să le urăm cu toţii cât mai multe realizări pe parcursul următorului mandat!

În final aş vrea să subliniez că orice vor întreprinde ei, în calitate de lideri infoarena, poate avea un impact mult mai mare dacă vă implicaţi şi voi. Nu uitaţi că oricine contribuie consistent poate ajunge în echipa şi chiar preşedintele 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.

Cei ce au rezolvat corect problema sunt urmatorii: Stefan Istrate, Andrei Marius Teodorescu, Adrian Vladu, Marius Pungaru, Marius Buzea, Daniel Pasaila si Alexandru Mosoi.

Va dau si solutia:
Pastram un sir A in care avem cele mai mici k numere din stream pana la momentul curent. Apoi la fiecare pas citim k noi elemente din stream in sirul B. Acum in sirul C punem elementele din ambele siruri si aplicam algoritmul de gasire a medianei care are complexitate O(k), vom pastra in A elementele din C mai mici sau egale cu mediana. Astfel obtinem un algoritm de complexitate O(n) timp si O(k) spatiu.

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