In aceasta serie de interviuri povestim despre concursurile de pe TopCoder cu cei trei romani care au participat la finala concursului TopCoder Collegiate Chalenge din aceasta toamna. Puteti citi celelalte doua interviuri aici si aici . Pe Mircea probabil il stiti deja si nu cred ca mai are nevoie de prezentare. In acest interviu el ne povesteste despre formatul competitiilor de algoritmica. Cred ca va fi interesant sa cititi opinia romanului cu cel mai mare rating la algoritmica despre aceste concursuri.

Mircea Pasoi

Povesteste-ne putin despre formatul concursului de algoritmica.
Formatul general Topcoder este urmatorul: ai 75 de minute sa faci 3 probleme, una usoara de 250 de puncte, una medie de 500 de puncte si una grea de 1000 de puncte. Cand trimti o problema punctajul pe care il primesti depinde de cat de repede ai rezolvat-o. Dupa cele 75 de minute ai inca 15 minute de "challenge", moment in care te uiti in sursele celorlati concurenti si incerci sa gasesti greseli. La sfarsit se evalueaza probleme si primesti puncte pentru o problema doar daca ai trecut toate testele.
Deaorece la o finala problemele sunt mult mai grele decat la un SRM obisnuit, faza de "coding" este de 85 de minute.

E a doua oara cand te califici la faza finala a concursului TopCoder Collegiate Challenge. Se simte vreo diferenta fata de anul trecut?
Cred ca rating-ul si rezultatul de anul asta dovedesc ca fost am mult mai bine pregatit ca anul trecut, si stiam si la ce sa ma astept de data asta. Chiar si asa, mai am mult de lucrat pana cand sa ma pot pune cu cei mai buni.

Cum se compara acest concurs cu celelalte concursuri internationale la care ai participat? Ca timp, stres, tipuri de probleme, strategie in concurs, concurenti sau locatie?

Topcoder este foarte diferit de concursurile de liceu. In primul rand cand treci de la concursuri de 5 ore la concursuri de 75 de minute diferenta e dramatica , si iti ia ceva sa te acomodezi. Un lucru foarte important la Topcoder este sa scrii cod corect, scurt si fara bug-uri. Poate pentru multa lume suna trivial, dar este mult mai greu decat pare! Concursurile de liceu nu te ajuta prea multe la chestiile astea, fiindca daca ai 5 ore iti permiti sa scrii incet, sa faci debug si mult testing. Plus ca uneori nu conteaza daca ai bug-uri ca tot iei puncte. Asa ceva nu merge la Topcoder. Eu unul am fost de mult ori surprins de solutiile altora care erau mult mai scurte si mai clare decat ceea ce faceam eu. Asta m-a ajutat mult sa-mi imbunatatesc implementarile. E surprinzator cate de usor e sa te complici sau sa faci chestii redundate cand scrii o sursa. Cred ca asta e si diferenta dintre cei din varf si restul lumii. Nu sunt mai buni pentru ca stiu sa scrie cod mai repede si mai mult, sunt mai buni pentru ca gandesc mai eficient si stiu sa scrie cod cat mai simplu.
Experienta de asemenea conteaza foarte mult. Cand ai 4-5 ore iti permiti sa incerci sa explorezi mai multe idei de rezolvare, lucru care rareori se intampla la Topcoder. Stai intre 5 si 15 minute sa te gandesti si apoi te apuci sa implementezi. Daca n-ai plecat pe ideea buna, de obicei nu mai sanse sa rectifici greseala. Mai bine treci la alta problema. Citeam pe undeva ca marii maestri la sah sunt mai buni decat restul nu pentru ca pot analiza mai multe posiblitati decat majoritatea lumii, ci pentru ca stiu sa analizeze cele mai bune posibilitati. Ceva de genul asta e valabil si la Topcoder.
O alta chestie destul de diferita sunt problemele, care de obicei sunt ceva mai simple decat cele pe la concursurile de liceu (ma refer in principal la 250 si 500, deoarece 1000le de obicei e comparabil cu problemele grele de liceu). Mindset-ul pe care trebuie sa-l ai cand rezolvi la Topcoder este destul de diferit de cel din liceu unde trebuie sa stai ceva timp sa te prinzi de solutia cea mai eficienta, de obicei trecand prin mai multe solutii din ce in ce mai eficiente. Aici trebuie sa te gandesti din prima care e solutia pe care o pot implementa cel mai repede si care se incadreaza in timp! Eu la inceput mereu aveam tendinta sa ma complic in rezolvari, sa optimizez unde nu era cazul sau sa ma gandesc direct la idei mai complicate decat era nevoie.
Per total, eu consider Topcoder ceva mai distractiv decat concursurile de liceu si o provocare mult mai mare in acelasi timp. Un lucru foarte important este ca oamenii cu care concurezi chiar sunt cei mai buni din lume, nu cei mai buni elevi de liceu (diferenta e ceva de genul ONI vs. IOI).

Cum te-ai pregatit pentru concurs?
Din pacate nu m-am mai pregatit deloc in ultimul an in mod special pentru Topcoder. Prin asta ma refer sa intru in arena si sa fac SRM-uri vechi. In schimb m-am pregatit pe infoarena si pentru ACM si se pare ca a fost destul de folositor pana acum.

Este greu sa te calfici in finala?
Da, este destul de greu. Cum am zis concurezi cu cei mai buni din lume pentru 48 de locuri. Poate parea mult, dar pe masura ce Topcoder devine din ce in ce mai popular e din ce in ce mai greu sa te califici Acum 2-3 ani nu erau mai deloc rusi la finale deoarece nu stiau de Topcoder, iar acum sunt in jur de 15 oameni din Rusia in mod constant. Cu China e aceeasi poveste si mai sunt si alte tari. Din fericire incepand cu TCO 2008 vor fi 72 de locuri. Oricum, oricat de bun ai fi, fara un pic de noroc n-ai cum sa te califici :)

Ce abilitati trebuie sa aiba un concurent puternic la algoritmica?
In mare parte ar fi ce am mentionat si mai sus:

• sa gandesti repede si sa stii ce idei de rezolvare sa incerci (experienta ajuta mult in cazul asta)
• sa scrii cod scurt si fara bug-uri intr-un ritm decent (nu trebuie sa-ti zboare degetele pe tastatura)
  O chestie deseori neglijata este cat de bine iti controlezi emotiile. Este foarte important sa fii cat mai relaxat la astfel de concursuri, si mai ales la TC unde stresul este ceva mai mare din cauza timpului putin.

Care a fost problema ta favorita din concurs?
Problema de 1000 din Room 3 pe care am facut-o doar eu si inca o persoana si cu ajutorul careia m-am calificat in cei 8 din finala.

Ce ti-a placut la DisneyLand?
Parcurile Disney :) Ar fi fost si mai tare daca ne lasau 2 zile in loc de 1 sa vedem toate parcurile. Daca cineva vrea sa vada poze pe care le-am facut la Disney si la TCCC poate sa intre aici .

Ce iti place la TopCopder?
Cam tot ce am explicat mai sus :) Trebuia sa te ascult si sa ma fi ocupat inca din liceu serios de Topcoder. :P

Cu acest post am terminat seria de interviuri despre concursurile topcoder. Sper ca acestea v-au motivat sa incercati competitiile care sunt foarte misto si pe toate gusturile. Ca liceean sau ca student este o modalitate foarte buna sa inveti ceva nou, sa cunosti oameni foarte buni, sa faci un ban in timpul liber si sa intrii in contact cu recruiteri pentru companii puternice ca Google, Microsoft, NVidia, Yahoo, AMD, Intel, City Group, UBS si altele. Paul a anuntat deja pe forum , dar vreau sa reamintesc si eu elevilor de liceu ca se apropie turneul TopCoder pentru liceeni. Anul trecut s-au calificat doua echipe din Romania. Una de la Colegiul national "Liviu Rebreanu" - Bistrita (liceul meu :) ) si alta de la ICHB, a doua echipa nu a putut sa participe pentru ca turneul era in conflict cu alt concurs. Sper ca anul asta sa se califice si mai multe echipe din Romania. Bafta!

via Mircea

Continuam seria de interviuri cu romanii ce au participat la finala concursului TopCoder Collegiate Challenge din toamna asta. Puteti citi prima parte aici . In aceasta parte Lucian Codrut Lazar ne va povesti despre concursurile de componente software si in special despre concursul de design software la care el s-a calificat in finala. Lucian are multa experienta cu aceste concursuri, a participat la 49 de competitii, a fost reviewer (membu al comisiei de corectori) la mai mult de 50 de componente, si a fost de doua ori reviewer la faza finala a concursului. In toamna asta a participat ca si concurent.

Lazar Codrut Lucian

Poti sa ne spui cate ceva despre concursul de software design? In ce consta el? Care sunt criteriile de notare, si care e partea dificila la un asemenea concurs?
In fiecare saptamana (de obicei joi) sunt puse mai multe componente (Java sau C#) pentru care trebuie facut design (sau development) intr-o saptamana. La design se da un document cu cerinte si trebuie facuta diagrama de clase, o diagrama de use case si diagrame de secventa pentru metodele mai complexe. Diagrama de clase contine toate clasele de care e nevoie pentru a implementa cerintele, cu toate metodele si campurile folosite. Toti pasii si toate constrangerile trebuie documentate (documentatia e orientata spre developeri). Mai trebuie un document Word, cu diverse discutii: thread-safety, algoritmi, demo, ... Design-urile sunt corectate de 3 review-eri. Sunt sectiuni pentru abordarea folosita (sabloane folosite, componente reutilizate, class scope, easy-to-use) - asta e partea faina dintr-un design; sectiuni pentru documentatie - aici e mai multa munca patriotica; si sectiuni pentru modul de prezentare. Sa gandesti strucura componentei poate fi mai greu la inceput, dar asta e partea faina a concursului. Apoi intervine partea de documentatie, care ia mult timp si devine enervanta, fiindca stii ce vrei sa faca fiecare entitate sau ce sa scrii in documentul Word, doar ca trebuie sa explici complet si asta ia mult timp.
La development sunt implementate design-urile de pe locul 1. Se face unit testing si se scrie documentatie orientata utilizator.

De ce software design si nu oricare dintre celelalte sectiuni (algoritmica, software development, marathon ...)?
Imi erau familiare sabloanele de proiectare si lucram la un framework pentru desenare de diagrame UML, deci stiam destul de bine UML. Sa incep la development mi-ar fi fost mai greu fiindca trebuia sa invat JUnit (sau NUnit) si parca nici nu prea am spor la implementare. La algoritmica am cam renuntat de cand am intrat la facultate, si oricum eram mult in urma ca nivel de cunostinte (plus ca tastez incet).

Cum ai recomanda cuiva sa inceapa sa participe la aceste competitii?
Sa citeasca GoF (cateva sabloane trebuie stiute: Strategy, Template Method, Abstract Factory, Observer, Adapter, Facade, Decorator). Trebuie intelese diagramele UML de care am zis mai sus. Un tutorial cred ca ajunge. Apoi intervine practica. In plus mai sunt forumuri publice, sau private pentru fiecare componenta. E bine sa intrebi orice nu e clar (despre sistem, despre componenta, despre diagrame, ...), fara frica de a parea penibil. In principiu, daca intrebi ceva cat de cat rezonabil, iti raspunde cineva repede si treci peste neclaritati.

Cum se ajunge la nivelul la care te poti califica la o faza finala pentru un asemenea concurs? Citesti carti? Proiecte facute de altii? Care e metoda de invatare?
Inceputul e mai greu - asta poate e valabil la orice tip de competitie. Pe masura ce faci mai multe componente devii mai sigur pe tine, plus ca inveti pe parcurs si din greseli. E bine sa te uiti pe componentele facute de altii. Cel mai bine e sa alegi componente facute de cei cu rating mare, ca sa nu dai peste abordari dubioase, care mai mult te baga in ceata. In cateva luni ajungi aproape de potentialu propriu, si poti incerca oricand sa te califici la turnee. Doar ca trebuie mai multa munca.

Ce programe software se folosesc in software design in general si la topcoder in particular?
Se lucra in Poseidon, dar acum se trece pe TC UML Tool - utilitar UML facut de TopCoder special pentru concursurile lor. Si un editor de documente in format .rtf.

Care a fost proiectul facut la TopCoder care ti-a placut cel mai mult?
TC UML Tool ;-)
Daca e vorba de componente, nu stiu ce sa zic. Mai recent - Graph Framework de la TCCC a fost interesanta, fiindca am avut libertate. Componentele in care sunt constrangeri de interfete sunt urate, fiindca nu prea e loc de o alta abordare si se rezuma doar la munca pentru documentatie.

De cate ore crezi ca ai nevoie pentru a face un design bun pentru o asemenea competitie?
16-20 ore efectiv. Plus mult timp petrecut citind cerintele, intreband pe forumuri si gandindu-te la componenta in timp ce mergi pe strada sau stai la o cafea.

Stiu ca in primavara ai fost in comisia ce evalua proiectele concurentilor la sectiunea software design pentru concursul TopCoder Open in Las Vegas. Cum e sa fi de partea cealalta a baricadei?
E aproape ca si cum ai face munca acasa, doar ca mergi acolo. Proiectele sunt mult mai de calitate (cel putin cele din top) decat ce vezi de obicei. Si iti ia mult mai mult timp sa la corectezi. Plus ca exista presiunea de a nu face vreo pozna sa dai scor prea mare sau prea mic si sa influentezi rezultatele. Asa ca trebuie sa insisti mai mult sa fii sigur ca ce au facut bine e intr-adevar bine si ce greseli ai gasit sunt intr-adevar greseli. Mie mi-a fost mai mult frica sa nu dau scor prea mare, fiindca la appeal-uri nu poti micsora scorul. Pe review-eri ne-au izolat de concurenti, intr-o camera. Ne-a dat cafea si ceva de rontait. Deci a fost bine.

Ce caracteristici crezi ca trebuie sa aiba un designer bun?
Mi-e cam greu sa raspund la intrebarea asta. Sa poata sa transforme cerinte textuale intr-o structura de clase care lucreaza impreuna pentru a atinge un scop. Nu stiu cum se numeste abilitatea asta. Trebuie sa ai o viziune de ansamblu, sa intelegi cum comunica mai multe componente, sa poti depista ce anume introduce limitari intr-o componenta, la fel cum ai depista unde se produce dead-lock intr-o aplicatie multi-threaded, doar ca lucrezi numai cu diagrame si nu cu cod, deci nu poti scrie teste.

Mersi Luci ca ti-ai facut timp sa raspunzi la intrebari. Maine voi pune online interviul cu Mircea Pasoi.

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.

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?

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

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 Bogdan-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!

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.

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!

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:

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