Diferente pentru ghid-complet-pentru-concursurile-de-informatica intre reviziile #22 si #38

Nu exista diferente intre titluri.

Diferente intre continut:

h1. Ghid complet pentru concursurile de informatica
(Categoria _Diverse_, autor _Mircea Pasoi_)
== include(page="template/implica-te/scrie-articole" user_id="sims_gl") ==
 
(Categoria _Diverse_, Autor _Mircea Pasoi_)
**Acest articol se adreseaza pasionatilor de informatica si celor care au de gand sa participe la concursurile si olimpiadele de informatica. Observatiile din cadrul acestui articol sunt, in mare parte, rezultatul experientei autorului.**
* **Olimpiada Judeteana de Informatica** - Incepand cu anul 2003 subiectele pentru olimpiada judeteana au fost aceleasi in toata tara; de obicei se desfasoara cu o luna dupa olimpiada locala si cu cel putin o luna inainte de olimpiada nationala; subiectele sunt de un nivel mediu in general.
* "**Olimpiada Nationala de Informatica**":http://olimpiada.info - Se organizeaza o data pe an, de obicei in prima vacanta din semestrul II al anului scolar; probele pentru liceu se desfasoara timp de 2 zile, in fiecare zi concurentii avand de rezolvat 3 probleme in 4 ore, iar probele pentru gimnaziu dureaza doar o zi, cate 2 probleme in 3 ore. De asemenea, prima jumatate din clasamentul pentru fiecare clasa de liceu participa la barajele pentru selectia lotului largit de informatica - aici, toti concurentii, indiferent de varsta, au de rezolvat aceleasi probleme. Primii ~20 selectati in urma acestei probe (care se desfasoara tot timp de 2 zile) vor forma lotul national largit; acestia vor participa la mai multe pregatiri, in cadrul carora sunt incluse baraje pentru selectarea echipelor de cate 4 elevi care vor reprezenta Romania la BOI, CEOI si IOI.
* **Balcaniada de Informatica** (BOI) - Prima editie a avut loc la Constanta in anul 1993. Standardele acestui concurs nu erau foarte ridicate, iar concurentii romani se claseaza foarte des pe primele locuri. Cel mai concludent exemplu in acest sens este faptul ca la editia din anul 2001 toate cele patru medalii de aur au fost obtinute de reprezentantii nostri, iar in 2005 ambele medalii de aur acordate au revenit iarasi romanilor. Exista si ani cand nivelul de dificultate al problemelor este mai ridicat, spre exemplu in 2003(Romania) si 2004(Bulgaria).
* **Olimpiada de Informatica a Europei Centrale** (CEOI) - Prima editie a avut loc la Cluj-Napoca in anul 1994. Editia din 2000 a acestui concurs a avut loc tot la Cluj-Napoca. Standardele acestui concurs sunt mai ridicate decat cele de la BOI, deoarece elevii din tarile participante sunt intotdeauna foarte bine pregatiti.
* **Olimpiada de Informatica a Europei Centrale** (CEOI) - Prima editie a avut loc la Cluj-Napoca in anul 1994. Editia din 2000 a acestui concurs a avut loc tot la Cluj-Napoca si foarte probabil editia din 2009 va fi tot in Romania. Standardele acestui concurs sunt mai ridicate decat cele de la BOI, deoarece elevii din tarile participante sunt intotdeauna foarte bine pregatiti.
* **Olimpiada Internationala de Informatica** (IOI) - Acest concurs reuneste anual elevi din ~80 tari ale lumii. Fiecare tara este reprezentata de cel mult patru concurenti, iar numarul tarilor participante creste in fiecare an. Organizarea concursului este asemanatoare cu cea a celorlalte concursuri internationale mentionate. Concursul este individual si se desfasoara sub forma a doua probe. La fiecare proba concurentii au la dispozitie 5 ore pentru a rezolva 3 probleme cu un grad ridicat de dificultate. Dupa fiecare proba, programele concurentilor sunt evaluate automat, cu ajutorul unor programe de evaluare. Dupa cele doua zile de concurs se stabileste clasamentul final si se acorda medaliile. Rezultatele sunt secrete pana in momentul decernarii premiilor. La aproape toate editiile acestui concurs, echipa Romaniei a avut rezultate excelente. Astfel, incepand din anul 1993, cu doar doua exceptii, toti cei patru componenti ai echipei tarii noastre au obtinut medalii; conform punctajelor individuale, s-au obtinut doua locuri I (1993 si 1998) cu punctaj maxim si un loc II (2001), iar in clasamentul pe natiuni Romania este o prezenta constanta in primele 10 locuri.
Mai exista si alte concursuri internationale, cum ar fi **Olimpiada Tarilor Baltice**, la care Romania nu participa. Puteti gasi detalii mai multe despre aceste concursuri, cat si problemele propuse, folosind "Google":http://www.google.com. De asemenea problemele si solutiile din ultimii ani pentru concursurile importante pot fi gasite la sectiunea "Downloads":http://infoarena.ro/downloads a site-ului "infoarena":http://infoarena.ro, acesta fiind actualizat periodic.
h3. Concursuri pentru studenti
* "**ACM**":http://www.acm.ro - un concurs organizat pentru studenti, de natura algoritmica. Diferentele majore fata de concursurile de liceu sunt reprezentate de faptul ca un program trebuie sa rezolve toate seturile de date de intrare prezentate pentru a se acorda puncte (nu se mai acorda punctaje partiale) si viteza cu care se rezolva problemele conteaza, iar evaluarea programelor este imediata. Concursul este pe echipe de cate 3 persoane, toate la un singur calculator. Concursul are loc pe regiuni initial (Centrul Europei, Sudul Europei, etc.) iar echipele calificate se intalnesc la marea finala.
* "**TopCoder**":http://www.topcoder.com - un site care organizeaza concursuri saptamanal, cat si turnee. Formatul este diferit fata de orice concurs intalnit pana acum, si anume fiecare concurent are de rezolvat 3 probleme in 75 de minute: o problema usoara de 250 puncte, una medie de 500 puncte si una grea de 1000 puncte. Punctajul efectiv pentru o problema se da in functie de viteza cu care aceasta este rezolvata. De asemenea, exista si o etapa de "challenge", in care concurentii pot vedea sursele celorlalti si, in caz ca determina un bug intr-o sursa, pot sa ruleze sursa respectiva, iar daca da raspuns gresit concurentul primeste 50 de puncte, altfel este penalizat cu 50 de puncte. Aceste concursuri sunt diferite fata de cele din liceu in care accentul este pe realizarea unui algoritm eficient, deoarece aici se pune accentul mai mult pe o implementare rapida si corecta a unor probleme care folosesc variatii ale unor algoritmi destul de cunoscuti, dar fiind necesara tratarea diferitelor cazuri speciale ce pot aparea. Ca avantaje, premiile la turnee sunt foarte mare (20.000$ pentru primul clasat), iar intregul sistem de punctare este mult mai complex si mai eficient. Google organizeaza impreuna cu TopCoder concursul "**Google Code Jam**":http://www.google.com/codejam.
* "**TopCoder**":http://www.topcoder.com - un site care organizeaza concursuri saptamanal, cat si turnee. Formatul este diferit fata de orice concurs intalnit pana acum, si anume fiecare concurent are de rezolvat 3 probleme in 75 de minute: o problema usoara de 250 puncte, una medie de 500 puncte si una grea de 1000 puncte. Punctajul efectiv pentru o problema se da in functie de viteza cu care aceasta este rezolvata. De asemenea, exista si o etapa de "challenge", in care concurentii pot vedea sursele celorlalti si, in caz ca determina un bug intr-o sursa, pot sa ruleze sursa respectiva, iar daca da raspuns gresit concurentul primeste 50 de puncte, altfel este penalizat cu 25 de puncte. Aceste concursuri sunt diferite fata de cele din liceu in care accentul este pe realizarea unui algoritm eficient, deoarece aici se pune accentul mai mult pe o implementare rapida si corecta a unor probleme care folosesc variatii ale unor algoritmi destul de cunoscuti, dar fiind necesara tratarea diferitelor cazuri speciale ce pot aparea. Ca avantaje, premiile la turnee sunt foarte mari (20.000$ pentru primul clasat), iar intregul sistem de punctare este mult mai complex si mai eficient. Google organizeaza impreuna cu TopCoder concursul "**Google Code Jam**":http://www.google.com/codejam.
h2. 3. Inainte de concurs
Primul si cel mai de seama lucru pe care trebuie sa il stiti este ca e important si sa participi, dar e si mai important sa participi onorabil, sa dai dovada de fair-play, iar daca se poate, sa si castigi! :) Nu trebuie sa porniti la drum cu ingamfare; modestia e buna, dar nu trebuie in nici un caz sa duca la neincredere in sine! Fiecare trebuie sa stie clar de ce e in stare si, mai presus de toate, sa se gandeasca ca la urma urmei nu dificultatea concursului conteaza, caci concursul, greu sau usor, este acelasi pentru toti. Mult mai importanta este valoarea individuala si nu in ultimul rand pregatirea psihologica. Fiecare concurs reprezinta de asemenea un prilej de perfectionare: fiecare concurent trebuie sa-si analizeze comportamentul din timpul concursului, si sa determine ce aspecte pot fi imbunatatite pentru a obtine performante mai bune la urmatoarele concursuri. Pregatirea psihologica este de multe ori neglijata si reprezinta pentru unii exact acel lucru care il impiedica sa obtina performantele dorite. Exista destui concurenti care uita faptul ca aceste concursuri sunt doar niste concursuri, si ajung sa creada ca cel mai important lucru din viata lor este performanta lor la concursuri - fapt care poate fi foarte daunator in cazul unor esecuri. Asadar, recomand tuturor concurentilor sa adopte o atitudine relaxata si optimista la concursuri, sa realizeze ca acestea reprezinta doar o mica parte din viata, si nu in ultimul rand sa se distreze!
O pregatire intensa inaintea unui concurs este foarte importanta deoarece imbunatateste viteza de implementare si reduce riscul aparitie erorilor, dar nu poate rezolva anumite lacune teoretice. Formula pentru succes poate fi descrisa ca "90% munca, 10% talent". Pentru a obtine performante mari trebuie neaparat o pregatire intensa adecvata. Exista mai multe aspecte ale pregatirii:
 
* Pregatirea teoretica
* Pregatirea psihica
* Organizarea globala a pregatirii
Unele carti isi propun sa initieze cititorul in tainele diverselor limbaje de programare, altele pun accentul mai cu seama pe tehnicile de programare si structurile de date folosite in rezolvarea problemelor. In general, cele din prima categorie contin exemple cu caracter didactic si exercitii cu un grad nu foarte ridicat de dificultate, iar celelalte demonstreaza matematic fiecare algoritm prezentat, insa neglijeaza partea de implementare, considerand scrierea codului drept un ultim pas lipsit de orice dificultate. Desigur, fiecare din aceste carti isi are rostul ei in formarea unui elev bine pregatit in domeniul informaticii. Totusi, trebuie considerata observatia ca scrierea unui program impune atat conceperea algoritmului si demonstrarea corectitudinii, cat si implementarea lui, ambele etape fiind complexe si nu lipsite de obstacole.
Cateva dintre cartile care ar trebui parcurse sunt in special cele scrise de fosti olimpici; prin intermediul acestora, autorii va impartasesc o parte din experienta acumulata. Cele mai folositoare carti (unele nu se mai gasesc) pentru pregatire sunt (unele nu sunt disponibile in Romania):
 
* **Introducere in Algoritmi (Cormen, Leiserson, Rivest)** - "Biblia" algoritmilor; mai este numita si CLR. Traducerea in limba romana a primei editii a acestei carti este disponibila la editura Agora Computer Libris si acum oricine este interesat o poate achizitiona. Contine o descriere amanuntita a tuturor algoritmilor de baza care pot fi folositi in rezolvarea problemelor de concurs.
* **Arta Programarii Calculatoarelor Vol. 1-3 (Donald Knuth)** - Donald E. Knuth este celebru datorita muncii sale de pionierat in domeniul algoritmilor si al tehnicilor de programare; "Daca te crezi un bun programator... citeste Arta Programarii Calculatoarelor de Knuth... Daca poti citi toata cartea, trimite-mi neaparat un C.V." - Bill Gates. Cartile se pot gasi la noi in tara la editura Teora
* **Proiectarea si implementarea algoritmilor (Mihai Oltean)** - aparuta la editura Computer Libris Agora din Cluj-Napoca; este o resursa foarte buna pentru programare dinamica
* **Culegere de probleme si programe PASCAL (Mihai Stroe, Cristian Cadar)** - aparuta la editura Petrion din Bucuresti, contine un capitol introductiv bun despre geometrie, cat si diverse solutii interesante la probleme din concursuri
* **Psihologia concursurilor de informatica (Catalin Francu)** - aparuta la editura L&S din Bucuresti; de asemenea contine solutii interesante la anumite probleme
* **Informatica - culegere de probleme pentru liceu (Emanuela Cerchez)** - aparuta la editura Polirom, contine diverse aplicatii pentru metodele principale de programare
* **Probelem de informatica date la concursurile internationale (Radu Berinde, Dan Ghinea, Horia Andrei Ciochina, Cornel Margine)** - aparuta la editura Fundatiei Pro, contine rezolvari pentru problemele de la principalele concursuri internationale din ultimii ani
* **Probleme de informatica date la concursurile internationale (Radu Berinde, Dan Ghinea, Horia Andrei Ciochina, Cornel Margine)** - aparuta la editura Fundatiei Pro, contine rezolvari pentru problemele de la principalele concursuri internationale din ultimii ani
* **Fundamentele programarii - Culegere de probleme pentru clasa a IX-a / clasa a X-a (Dana Lica, Mircea Pasoi)** - aparute la editura L&S din Bucuresti, ambele contin un capitol mare de probleme propuse pe la concursuri impreuna cu solutii
* **Arbori (Emanuela Cerchez)** - aparuta la editura Tara Fagilor, trateaza in detaliu arborii
* **Probleme de combinatorica si teoria grafurilor (Ioan Tomescu)** - desi este o carte in principal de matematica multe probleme de acolo au aparut la concursurile romanesti
* **Programming Challenges: The Programming Contest Training Manual (Steven Skiena, Miguel Revilla)** - o carte folositoare mai ales pentru concursurile ACM
In afara de cartile mentionate, internetul se dovedeste din nou o resursa foarte importanta. O cautare pe internet poate localiza informatii interesante: descrierea unor anumiti algoritmi impreuna cu performantele lor, tratari ale unor probleme clasice prin mai multe metode etc. Desigur pe langa carti este recomandat sa se si lucreze cat mai multe probleme de la editiile anterioare ale concursurilor principale si de pe site-urile cu evaluator disponibil 24 din 24. Astfel de site-uri sunt:
 
* "infoarena":http://infoarena.ro
* http://acm.timus.ru
* http://acm.sgu.ru
h3. Pregatirea psihica
Dupa cum s-a mai zis, este cunoscut faptul ca o atitudine mentala pozitiva este cheia succesului in cele mai multe situatii. Din nefericire, unii concurenti incep proba cu un moral nu tocmai ridicat. Iata cateva din falsele probleme cu care se confrunta anumiti concurenti:
 
* _Participa si X, care e mai bun ca mine, deci nu am nici o sansa sa castig!_
Fals! Nu s-a demonstrat ca X este mai bun, cel mult a obtinut rezultate mai bune pana acum si poate avea sanse mai mari. Problemele din concursul curent sunt aceleasi pentru toti, conditiile de desfasurare sunt aceleasi si antecedentele nu conteaza. Totul se reia de la zero. In plus, participarea la un concurs puternic poate aduce mai multa experienta pentru viitor. Pentru a ajunge la valoarea necesara castigarii unor concursuri, trebuie sa participati la cat mai multe si sa le tratati cu seriozitate.
* _Am obtinut prea putine puncte in prima zi, nu mai am nici o sansa la premii!_
h3. Discutiile cu alti elevi si profesori
Puteti invata foarte mult de la profesori, si in special de la elevi mai experimentati! Exista foarte multe exemple de elvei pentru care a contat foarte mult pregatirea individuala, dar exista unii care au fost ajutati de pregatirea organizata, in grupuri de elevi, sub indrumarea unor profesori cu preocupari de acest gen. In cadrul pregatirilor de acest tip se discuta algoritmi, se propun probleme spre rezolvare, se discuta diversele modalitati de rezolvare, se obtin mai multe informatii despre concursuri, etc. In plus, elevii aduc in discutie diverse probleme cu care s-au intalnit in cadrul pregatirii individuale. Daca doriti sa participati la astfel de pregatiri, trebuie sa luati legatura cu alti elevi interesati de concursuri, sau cu profesori care se ocupa de pregatirea elevilor pentru olimpiade. In prezent se organizeaza pregatiri la nivel de liceu, oras, judet, etc. in anumite zone. Astfel de pregatiri cresc valoarea tuturor participantilor, deci sunt foarte importanta. Pregatirile organizate au luat amploare odata cu infiintarea centrelor de excelenta. Pentru a intra in contact cu alti elevi interesati puteti folosi "forumul infoarena":http://infoarena.ro/forum si "forumul revistei GInfo":http://ba.toptalent.ro/forum.
Puteti invata foarte mult de la profesori, si in special de la elevi mai experimentati! Exista foarte multe exemple de elevi pentru care a contat foarte mult pregatirea individuala, dar exista unii care au fost ajutati de pregatirea organizata, in grupuri de elevi, sub indrumarea unor profesori cu preocupari de acest gen. In cadrul pregatirilor de acest tip se discuta algoritmi, se propun probleme spre rezolvare, se discuta diversele modalitati de rezolvare, se obtin mai multe informatii despre concursuri, etc. In plus, elevii aduc in discutie diverse probleme cu care s-au intalnit in cadrul pregatirii individuale. Daca doriti sa participati la astfel de pregatiri, trebuie sa luati legatura cu alti elevi interesati de concursuri, sau cu profesori care se ocupa de pregatirea elevilor pentru olimpiade. In prezent se organizeaza pregatiri la nivel de liceu, oras, judet, etc. in anumite zone. Astfel de pregatiri cresc valoarea tuturor participantilor, deci sunt foarte importante. Pregatirile organizate au luat amploare odata cu infiintarea centrelor de excelenta. Pentru a intra in contact cu alti elevi interesati puteti folosi "forumul infoarena":http://infoarena.ro/forum si "forumul revistei GInfo":http://ba.toptalent.ro/forum.
h3. Pregatirea de la locul desfasurarii probei
Desi ar putea parea bizar, acest aspect este foarte important, dar este neglijat de multe ori de catre concurenti. Aceasta pregatire consta in:
 
* somn odihnitor in noaptea care precede ziua concursului **(foarte important!)**
* obtinerea atitudinii mentale dorite
* prezentarea la timp in sala, cu toate obiectele necesare
* asculta muzica motivanta inaintea probelor; chiar daca pare ciudat, marii informaticieni asculta manele de calitate(Ma omoara, ma omoara, Sange de taur etc.)
Exista cateva obiecte pe care ar trebui sa le aveti la voi. In timpul concursului trebuie tinuta o evidenta drastica a timpului scurs si a celui ramas. E drept ca in general supraveghetorii anunta din cand in cand timpul care a trecut, dar e bine sa nu va bazati pe nimeni si nimic altceva decat pe voi insiva. Unii pot spune _Ei, ce nevoie am de ceas, oricum am ceasul calculatorului la indemana_. Asa e, dar e incomod sa te opresti mereu la jumatatea unei idei si sa verifici cat e ceasul schimband consola sau minimizand fereastra de lucru. In ceea ce priveste hartia de scris, ea este in mod sigur necesara. De fapt, o parte importanta a rezolvarii unei probleme este proiectarea matematica a algoritmului, lucru care nu se poate face decat cu creionul pe hartie. Pe langa aceasta, majoritatea problemelor opereaza cu vectori, matrice, arbori, grafuri, etc., iar exemplele pe care este testat programul realizat trebuie neaparat verificate "de mana". Este recomandat sa aveti mereu si hartie de matematica; este foarte folositoare pentru problemele de geometrie analitica, precum si penntru reprezentarea matricelor. Nu in ultimul rand, ar fi bine sa aveti o sticla de suc si o ciocolata; din nefericire, concursul incepe deseori cu intarziere si este bine ca foamea sau setea sa nu va preocupe in timpul rezolvarii problemelor.
Exista cateva obiecte pe care ar trebui sa le aveti la voi. In timpul concursului trebuie tinuta o evidenta drastica a timpului scurs si a celui ramas. E drept ca in general supraveghetorii anunta din cand in cand timpul care a trecut, dar e bine sa nu va bazati pe nimeni si nimic altceva decat pe voi insiva. Unii pot spune _Ei, ce nevoie am de ceas, oricum am ceasul calculatorului la indemana_. Asa e, dar e incomod sa te opresti mereu la jumatatea unei idei si sa verifici cat e ceasul schimband consola sau minimizand fereastra de lucru. In ceea ce priveste hartia de scris, ea este in mod sigur necesara. De fapt, o parte importanta a rezolvarii unei probleme este proiectarea matematica a algoritmului, lucru care nu se poate face decat cu creionul pe hartie. Pe langa aceasta, majoritatea problemelor opereaza cu vectori, matrice, arbori, grafuri, etc., iar exemplele pe care este testat programul realizat trebuie neaparat verificate "de mana". Este recomandat sa aveti mereu si hartie de matematica; este foarte folositoare pentru problemele de geometrie analitica, precum si pentru reprezentarea matricelor. Nu in ultimul rand, ar fi bine sa aveti o sticla de suc si o ciocolata; din nefericire, concursul incepe deseori cu intarziere si este bine ca foamea sau setea sa nu va preocupe in timpul rezolvarii problemelor.
h2. 4. In timpul concursului
Imediat ce primiti problemele, cititi toate enunturile si faceti-va o idee aproximativa despre gradul de dificultate al fiecarei probleme. Neaparat verificati daca se dau limite pentru datele de intrare (numarul maxim de elemente ale unui vector si valoarea maxima a acestora, numarul maxim de noduri dintr-un graf, etc.) si pentru timpii de executie pentru fiecare test. Dimensiunea input-ului poate schimba radical dificultatea problemei. Spre exemplu, pentru un vecotr cu N ≤ 200 elemente, un algoritm O(N^3^) merge rezonabil, pe cand pentru N ≤ 2000 acelasi algoritm ar depasi cu mult cele cateva sutimi de secunda care se acorda de obicei. In primele zece minute (sau mai mult) nu se atinge calculatorul. Intotdeauna, cand cititi o problema, este indicat sa intoarceti foaia pentru a vedea daca enuntul continua si pe verso. De obicei, in primele 30 sau 60 de minute ale concursului pot fi adresate intrebari comisiei, pentru a clarifica eventualele ambiguitati din enunturi. Acestea sunt redactate in scris, foile sunt preluate de supraveghetorul din sala si trimise la comisie. Raspunsul s-ar putea sa intarzie, deci este indicat sa nu irositi timpul asteptand raspunsul fara a mai face nimic altceva. Puteti fie sa va ganditi la rezolvarea unei probleme, fie sa incepeti sa implementati (daca exista ceva usor de implementat, cum ar fi o problema simpla sau o rutina pentru citirea datelor de intrare). In majoritatea situatiilor, intrebarile trebuie formulate in asa fel incat raspunsul sa fie _Da_ sau _Nu_. Daca intrebarea nu este astfel exprimata sau daca raspunsul se gaseste in textul problemei, veti primi raspunsul _Fara comentarii_, caz in care va trebui mai intai sa studiati corectitudinea intrebarii si, daca aceasta este corect formulata, sa recititi enuntul problemei. Concurentii trebuie sa profite cat mai mult de aceasta perioada, pentru a clarifica eventualele nelamuriri. Un lucru important este ca nu trebuie sa acceptati raspunsuri daca acestea nu sunt insotite de semnatura unui membru al comisiei.
Imediat ce primiti problemele, cititi toate enunturile si faceti-va o idee aproximativa despre gradul de dificultate al fiecarei probleme. Neaparat verificati daca se dau limite pentru datele de intrare (numarul maxim de elemente ale unui vector si valoarea maxima a acestora, numarul maxim de noduri dintr-un graf, etc.) si pentru timpii de executie pentru fiecare test. Dimensiunea input-ului poate schimba radical dificultatea problemei. Spre exemplu, pentru un vector cu N ≤ 200 elemente, un algoritm O(N^3^) merge rezonabil, pe cand pentru N ≤ 2000 acelasi algoritm ar depasi cu mult cele cateva sutimi de secunda care se acorda de obicei. In primele zece minute (sau mai mult) nu se atinge calculatorul. Intotdeauna, cand cititi o problema, este indicat sa intoarceti foaia pentru a vedea daca enuntul continua si pe verso. De obicei, in primele 30 sau 60 de minute ale concursului pot fi adresate intrebari comisiei, pentru a clarifica eventualele ambiguitati din enunturi. Acestea sunt redactate in scris, foile sunt preluate de supraveghetorul din sala si trimise la comisie. Raspunsul s-ar putea sa intarzie, deci este indicat sa nu irositi timpul asteptand raspunsul fara a mai face nimic altceva. Puteti fie sa va ganditi la rezolvarea unei probleme, fie sa incepeti sa implementati (daca exista ceva usor de implementat, cum ar fi o problema simpla sau o rutina pentru citirea datelor de intrare). In majoritatea situatiilor, intrebarile trebuie formulate in asa fel incat raspunsul sa fie _Da_ sau _Nu_. Daca intrebarea nu este astfel exprimata sau daca raspunsul se gaseste in textul problemei, veti primi raspunsul _Fara comentarii_, caz in care va trebui mai intai sa studiati corectitudinea intrebarii si, daca aceasta este corect formulata, sa recititi enuntul problemei. Concurentii trebuie sa profite cat mai mult de aceasta perioada, pentru a clarifica eventualele nelamuriri. Un lucru important este ca nu trebuie sa acceptati raspunsuri daca acestea nu sunt insotite de semnatura unui membru al comisiei.
Faceti o impartire a timpului pentru problemele ramase proportional cu dificultatea aparenta a fiecarei probleme. In general problemele au punctaje egale. Incercati sa nu depasiti niciodata limitele de timp pe care le-ati fixat. Daca in schimb reusiti sa economisiti timp fata de cat v-ati propus, cu atat mai bine, veti face o realocare a timpului si veti avea mai mult pentru celelalte probleme. Apucati-va de problema **cea mai simpla**. Mai bine sa duceti la bun sfarsit o problema usoara, decat sa va apucati de o problema grea si sa nu terminati nici una. Daca toate problemele par grele, alegeti-o pe cea din domeniul care va este cel mai familiar, in care ati lucrat cel mai mult. Daca va este indiferent si acest lucru, alegeti o problema unde simtiti ca aveti o idee simpla de rezolvare.
Incepeti sa va ganditi la algoritmi cat mai buni, estimand in acelasi timp si cat v-ar lua ca sa-i implementati. Faceti, pentru fiecare idee care va vine, calculul complexitatii. Nu trebuie neaparat sa gasiti cel mai eficient algoritm, ci numai unul suficient de bun. In general, trebuie ca, dintre toti algoritmii care se incadreaza in timpul de rulare, sa-l alegeti pe cel care este cel mai usor de implementat. Daca algoritmul gasit este greu de implementat, mai cautati altul o vreme. Trebuie insa ca timpul petrecut pentru gasirea unui nou algoritm plus timpul necesar pentru scrierea programului sa nu depaseasca timpul necesar pentru implementarea primului algoritm, altfel nu castigati nimic. Deci nu exagerati cu cautarile si nu incercati sa reduceti dincolo de limita imposibilului complexitatea algoritmului. Mai ales, nu uitati ca programul nu poate avea o complexitate mai mica decat dimensiunea input-ului sau a output-ului. De exemplu, daca programul citeste sau scrie matrice de dimensiune N*N, nu are sens sa va bateti capul ca sa gasiti un algoritm mai bun decat O(N^2^). Dintre toate ideile de implementare gasite (care se incadreaza fara probleme in timp), o veti alege pe cea mai scurta ca lungime de cod.
In general, pentru orice problema exista cel putin o solutie, fie si una slaba. Sunt numeroase cazurile cand nu va vine alta idee de rezolvare decat cea slaba. De regula, cand nu aveti in minte decat o rezolvare neeficienta a problemei, care stiti ca nu o sa treaca toate testele (un backtracking, sau un O(N^5^), O(N^6^), etc.) e bine sa incercati urmatorul lucru:
 
* Calculati cam cat timp v-ar trebui ca sa implementati rezolvarea slaba. In acest calcul trebuie sa includeti si un timp estimativ de depanare a programului (care variaza de la persoana la persoana) si pe cel de testare. Daca sunteti foarte siguri pe voi, puteti sa neglijati timpul de testare, dar orice program trebuie testat cel putin pe exemplul de pe foaie.
* Pentru a avea sanse mai mari sa gasiti o alta solutie, este indicat sa incercati sa ignorati complet solutia slaba, sa nu o luati ca punct de plecare. Incercati sa va "goliti" mintea si sa gasiti ceva nou, altfel va veti invarti mereu in cerc.
* Daca va vine vreo idee mai buna, ati scapat de griji si va apucati de implementare (daca aveti timpul necesar).
Din acest moment, pentru varianta aleasa veti scrie programul, fara a va mai gandi la altceva, chiar daca pe parcurs va vin alte idei. Iata unele lucruri pe care e bine sa le stiti despre scrierea unui program:
 
* Datele de intrare se presupun a fi corecte. Aceasta este o regula nescrisa (uneori) a concursului de informatica.
* Efectul optiunilor de compilare asupra vitezei este semnificativ.
* Daca se poate, evitati lucrul cu pointeri. Programele care ii folosesc sunt mai greu de depanat si se pot bloca mult mai usor.
* Salvati programul cat mai des. Daca va obisnuiti, chiar la fiecare 2-3 linii. Dupa ce o sa va intre in reflex n-o sa va mai incomodeze  cu nimic acest obicei. Au fost cazuri in care o pana de curent prindea pe picior gresit multi concurenti, iar dupa aceea nu mai este absolut nimic de facut, pentru ca nimeni nu va va crede pe cuvant ca ati facut programul si ca el mergea.
* Obisnuiti-va sa programati modular. Faceti proceduri separate pentru citirea si initializarea datelor, pentru sortare, pentru afisarea rezultatelor, etc. In general nu se recomanda sa scrieti proceduri in alte proceduri (adica e bine ca toate procedurile sa apartina direct de programul principal). Procedurile, acolo unde e posibil, nu trebuie sa depaseasca un ecran, pentru a putea avea o viziune de ansamblu asupra fiecareia in parte. Acest lucru ajuta mult la depanare.
* Rulati programul cat mai des, daca timpul va permite. In primul rand dupa ce scrieti procedura de citire a datelor. Daca e nevoie de sortarea datelor de intrare, nu strica sa va convingeti ca programul sorteaza bine, ruland 2-3 teste oarecare. E pacat sa pierdeti puncte dintr-o greseala copilareasca.
* O situatie mai delicata apare cand fisierul de intrare contine mai multe seturi de date (teste). In acest caz, atentia trebuie sporita, deoarece daca la primul sau al doilea test programul vostru da eroare si se opreste din executie, veti pierde automat si toate celelalte teste care urmeaza. Daca in fisierul de intrare exista un singur set de date, atunci pierderea din vedere a unui caz particular al problemei nu putea duce, in cel mai rau caz, decat la picarea unui test. Asa insa, picarea unui test poate atrage dupa sine picarea tuturor celor care il urmeaza. Pe langa corectitudinea strict necesara, programul trebuie sa se incadreze is in timp pentru orice fel de test. Daca la primul sau al doilea test din suita programul depaseste timpul (sau, si mai rau, se blocheaza), e foarte probabil sa fie oprit din executie de catre comisie, deci din nou veti pierde toate testele care au ramas neexecutate.
* O situatie mai delicata apare cand fisierul de intrare contine mai multe seturi de date (teste). In acest caz, atentia trebuie sporita, deoarece daca la primul sau al doilea test programul vostru da eroare si se opreste din executie, veti pierde automat si toate celelalte teste care urmeaza. Daca in fisierul de intrare exista un singur set de date, atunci pierderea din vedere a unui caz particular al problemei nu putea duce, in cel mai rau caz, decat la picarea unui test. Asa insa, picarea unui test poate atrage dupa sine picarea tuturor celor care il urmeaza. Pe langa corectitudinea strict necesara, programul trebuie sa se incadreze si in timp pentru orice fel de test. Daca la primul sau al doilea test din suita programul depaseste timpul (sau, si mai rau, se blocheaza), e foarte probabil sa fie oprit din executie de catre comisie, deci din nou veti pierde toate testele care au ramas neexecutate.
* Tot in situatia in care exista mai multe seturi de date in fisierul de intrare, daca iesirea se face intr-un fisier, este bine ca dupa afisarea rezultatului pentru fiecare test sa actualizati fisierul de iesire. In felul acesta, chiar daca la unul din teste programul se blocheaza sau da eroare, rezultatele deja scrise raman scrise. Altfel, e posibil ca rezultatele de la testele anterioare sa ramana intr-un buffer in memorie, fara a fi "varsate" pe disc.
Tot la partea de implementare, este bine ca codul sa fie cat mai scurt si cat mai optimizat - dar, despre scrierea unui cod cat mai eficient se poate face un articol cam la fel de mare cat acesta, deci nu se va trata acest subiect aici - metoda cea mai buna in acest sens este sa invatati din sursele altora. Puteti incepe cu articolele "_12 ponturi pentru programatorii C/C++_":http://infoarena.ro/12-ponturi-pentru-programatorii-CC si "_Multe smenuri de programare in C/C++... si nu numai!_":http://infoarena.ro/Multe-smenuri-de-programare-in-CC-si-nu-numai si sectiunea "Links":http://infoarena.ro/links.
Mai ramane doar partea de depanare. O metoda buna de depanare este urmatoarea:
* Incepeti cu un test nici prea simplu, nici prea complicat (si usor de urmarit cu creionul pe hartie) si executati-l de la cap la coada. Daca merge perfect, treceti la teste mai complexe (se recomanda **minim** 4 test si maxim 7-8). Daca le trece si pe acestea, puteti zambi. Totusi, daca programul vostru a mers perfect pe 7-8 teste date la intamplare, exista sanse (dar nu extrem de mari!) sa mearga pe majoritatea testelor comisiei, sau chiar pe toate.
 
* Incepeti cu un test nici prea simplu, nici prea complicat (si usor de urmarit cu creionul pe hartie) si executati-l de la cap la coada. Daca merge perfect, treceti la teste mai complexe (se recomanda **minim** 4 teste si maxim 7-8). Daca le trece si pe acestea, puteti zambi. Totusi, daca programul vostru a mers perfect pe 7-8 teste date la intamplare, exista sanse (dar nu extrem de mari!) sa mearga pe majoritatea testelor comisiei, sau chiar pe toate.
* Exemplul dat in enunt nu are in general nici o semnificatie deosebita (de fapt, are mai curand darul de a semana confuzie printre concurenti), iar daca programul merge pe acest test particular, nu inseamna ca o sa mearga si pe alte teste.
* Daca la unul din teste programul nu merge corespunzator, rulati din nou testul , dar de data aceasta procedura cu procedura. Dupa fiecare procedura evaluati variabilele si vedeti daca au valorile asteptate. In felul acesta puteti localiza cu precizie procedura, apoi linia unde se afla eroarea. Corectati in aceasta maniera toate erorile, pana cand testul este trecut.
* In acest moment, luati de la capat toate testele pe care programul le-a trecut deja. In urma depanarii, s-ar putea ca alte greseli sa iasa la suprafata si programul sa nu mai mearga pe vechile teste.
* Repetati procedeul de mai sus pana cand toate testele merg. Daca va obisnuiti sa programati modular si ingrijit, depanarea si testarea n-ar trebui sa dureze mai mult de 5-25 minute. Din acest moment, nu mai modificati nici macar o litera in program, sau daca o faceti pastrati-va in prealabil o copie. Nu va bazati pe faptul ca puteti sa tineti minte modificarile facute si sa refaceti oricand forma initiala a programului in caz ca noua versiune nu va fi buna.
* Daca totusi nu-i puteti "da de cap" programului, iar timpul alocat problemei respective expira, aduceti programul la o forma in care sa mearga macar pe o parte din teste si treceti la problema urmatoare.
 
Feriti-va ca de foc de criza de timp. E mare pacat sa ratezi o problema intreaga pentru ca n-ai avut timp sa scrii procedura de afisare a solutiei, sau lucruri asemanatoare. Rezervati-va intotdeauna timpul pe care il socotiti necesar pentru implementare si depanare. De asemenea, chiar daca concursul este usor, nu e recomandat sa iesiti din sala de concurs inainte de expirarea timpului. Oricat ati fi de convinsi ca ati facut totul perfect, mai verificati-va; veti avea de furca cu remuscarile daca descoperiti dupa aceea ca ceva, totusi, nu a mers bine. Puteti face o multime de lucruri daca mai aveti timp (desi acest lucru se intampla rar). Iata o serie de metode de a exploata timpul:
 
* Verificati-va programul cu cat mai multe teste de mici dimensiuni. Sa presupunem ca programul vostru lucreaza cu vectori de maxim 10.000 de elemente. E o idee buna sa il rulati pentru vectori de unul sau doua elemente.
* Treceti la polul opus si creati-va un test de dimensiune maxima, dar cu o structura particulara, pentru care este usor de calculat rezultatul si de mana. De exemplu, vectori de 10.000 de elemente cu toate elementele egale, sau vectori de forma (1, 2, ..., 9999, 10000). Daca nu puteti sa editati un asemenea fisier de mana, copiind si multiplicand blocuri, puteti scrie un program care sa-l genereze.
* Daca inca v-a mai ramas timp, creati-va un program care sa genereze teste aleatoare. Spre exemplu, un program care sa citeasca N si sa creeze un fisier in care sa scrie N numere aleatoare. Intr-o prima faza, puteti folosi aceste teste pentru a verifica daca nu cumva la valori mai mari programul nu da eroare, nu se blocheaza (la alocarea unor zone mari de memorie) sau nu depaseste limita de timp, caz in care mai aveti de lucru.
* Daca tot nu va da nimeni afara din sala, puteti scrie un alt program auxiliar care, primind fisierul de intrare si fisierul de iesire produs de programul vostru, verifica daca iesirea este corecta. Aceasta deoarece, de obicei, este mult mai usor de verificat o solutie decat de produs una. Folosind "generatorul" de teste si "verificatorul", puteti testa programul mult mai bine. De altfel, la multe probleme chiar testele rulate de comisia de corectare sunt create tot aleator.
 
h2. 5. Dupa concurs
 
Dupa ce ati terminat problemele (se intampla destul de rar) nu iesiti din sala! Este momentul ultimelor teste. La iesirea din sala trebuie sa fiti convinsi ca ati facut tot ce era posibil in conditiile date. Concursul nu s-a terminat inca! Urmeaza corectarea. Va trebui sa verificati punctajul obtinut si sa fiti pregatit sa depuneti o contestatie daca aveti impresia ca ceva nu este in regula. La unele concursuri, corectarea se face in prezenta concurentului; aici aveti ocazia sa solicitati sa vi se arate testele si iesirile furnizate de programul vostru, sa cereti testarea din afara mediului de evaluare, etc. La alte concursuri, comisia ofera, mai tarziu, testele si raspunsurile corecte pentru autoevaluare. Nu ratati ocazia de a va evalua rezolvarile si nu depuneti contestatii decat daca in urma autoevaluarii obtineti un punctaj mai mare. Fiecare concurs este o experienta in plus! Discutati, dupa proba, cu alti concurenti, aflati cum ar fi trebuit rezolvate problemele pe care nu le-ati stiut aborda si ce au gresit ceilalti (este bine sa invatati si din greselile altora).
 
De multe ori, primul an de participare la olimpiada se soldeaza cu un rezultat cel mult mediu, deoarece, oricat ar spune cineva _Ei, nu-i asa mare lucru sa mergi la un concurs_, experienta acumulata conteaza mult. De aceea, abia de la a doua participare si uneori chiar de mai tarziu incep sa apara rezultatele. Intentia autorului a fost sa va usureze misiunea si sa va dezvaluie cateva din dificultatile de toate felurile care apar la orice concurs, pentru a nu va da ocazia sa le descoperiti pe propria piele. Speram ca aceste ponturi va vor fi de folos!
 
h2. Bibliografie
 
# **Psihologia concursurilor de informatica**, Catalin Francu, Editura L&S Bucuresti
# "**Despre Concursuri**":http://www.ginfo.ro/revista/13_4/babel.pdf, Mihai Stroe, Gazeta de Informatica, numarul 13/4, anul 2003
# "infoarena":http://infoarena.ro
# "Google":http://www.google.com

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3680