Diferente pentru concursul-de-informatica intre reviziile #9 si #14

Diferente intre titluri:

Concursul de informatica
Concursul de informatica (de la agonie la extaz)

Diferente intre continut:

(Categoria _Diverse_, Autor _Catalin Francu_, Preluat din cartea _"Psihologia concursurilor de informatica"_)
(toc){width: 37em}*{text-align:center} *Conţinut:*
(toc){width: 25em}*{text-align:center} *Conţinut:*
* 'Inainte de concurs':concursul-de-informatica#inainte-de-concurs
* 'In timpul concursului':concursul-de-informatica#in-timpul-concursului
* 'Strategii in timpul concursului':concursul-de-informatica#strategii
* 'Strategii de abordare a problemelor':concursul-de-informatica#strategii
* 'Concluzii':concursul-de-informatica#concluzii
h3. _"Cine doreste sa-si rezolve treburile la vremea potrivita, sa-si imparta cu atentie timpul"_, Plaut
bq. "Cine doreste sa-si rezolve treburile la vremea potrivita, sa-si imparta cu atentie timpul" - Plaut
Experienta demonstreaza ca, oricat de mare ar fi bagajul de cunostinte acumulat de un elev, mai e nevoie de ceva pentru a-i asigura succesul la olimpiada de informatica. Aceasta deoarece in timp de concurs lucrurile stau cu totul altfel decat in fata calculatorului de acasa sau de la scoala. Reusita depinde, desigur, in cea mai mare masura de puterea fiecaruia de a pune in practica ceea ce a invatat acasa. Numai ca in acest proces intervin o serie de factori care tin de temperament, de experienta individuala, de numarul de ore dormite in noaptea dinaintea concursului (care in taberele nationale este ingrijorator de mic) si asa mai departe.
Cu riscul de a cadea in demagogie, trebuie sa spunem ca un concurs de informatica presupune mult mai mult decat un simplu act de prezenta la locul desfasurarii ostilitatilor. Capitolul de fata incearca sa enunte cateva principii ale concursului, pe care autorul si le-a insusit in cei patru ani de liceu, atat  din experienta proprie, cat si invatand de la altii. Cititorul este liber sa respinga aceste sfaturi sau sa le accepte, filtrandu-le prin prisma personalitatii sale si alegand ceea ce i se potriveste.
Cu riscul de a cadea in demagogie, trebuie sa spunem ca un concurs de informatica presupune mult mai mult decat un simplu act de prezenta la locul desfasurarii ostilitatilor. Articolul de fata incearca sa enunte cateva principii ale concursului, pe care autorul si le-a insusit in cei patru ani de liceu, atat din experienta proprie, cat si invatand de la altii. Cititorul este liber sa respinga aceste sfaturi sau sa le accepte, filtrandu-le prin prisma personalitatii sale si alegand ceea ce i se potriveste.
h2(#inainte-de-concurs). 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, 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.
Autorul a fost peste masura de surprins sa constate ca multi elevi merg la concurs fara ceas si fara hartie de scris. Aceasta este fara indoiala o greseala capitala. 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 colegi spuneau "Ei, ce nevoie am de ceas, oricum am ceasul calculatorului la indemana". Asa e, dar e extrem de incomod sa te opresti mereu la jumatatea unei idei, sa deschizi o sesiune DOS din cadrul limbajului de programare si sa afli cat e ceasul.
Autorul a fost peste masura de surprins sa constate ca multi elevi merg la concurs fara ceas si fara hartie de scris. Aceasta este fara indoiala o greseala capitala. 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 colegi spuneau "Ei, ce nevoie am de ceas? Oricum am ceasul calculatorului la indemana.". Asa e, dar e extrem de incomod sa te opresti mereu la jumatatea unei idei, sa iesi din mediul de programare (in cazul celor sub DOS) si sa afli cat e ceasul.
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". E de preferat sa aveti hartie de matematica; este foarte folositoare pentru problemele de geometrie analitica, precum si pentru reprezentarea matricelor. Cantitatea depinde de imaginatia fiecaruia. In unele cazuri speciale, autorului i s-a intamplat sa umple 7-8 coli A4.
h2(#in-timpul-concursului). In timpul concursului
Din fericire pentru unii si din nefericire pentru altii, majoritatea examenelor iti cer sa dovedesti nu ca esti bine pregatit, ci ca esti mai bine pregatit decat altii. Aceasta inseamna ca si la olimpiada de informatica se aplica legea pestelui mai mare sau, cum i se mai spune, a concurentei. Valoarea absoluta a fiecaruia nu conteaza chiar in totalitate, ceea ce constituie sarea si piperul concursului. Intr-adevar, ce farmec ar avea sa mergi la un concurs la care se stie inca dinainte cine este cel mai bun ? Este destul de amuzant sa observi cum fiecare spera sa prinda "o zi buna", iar adversarii sai "o zi proasta".
Din fericire pentru unii si din nefericire pentru altii, majoritatea examenelor iti cer sa dovedesti nu ca esti bine pregatit, ci ca esti mai bine pregatit decat altii. Aceasta inseamna ca si la olimpiada de informatica se aplica legea pestelui mai mare sau, cum i se mai spune, a concurentei. Valoarea absoluta a fiecaruia nu conteaza chiar in totalitate, ceea ce constituie sarea si piperul concursului. Intr-adevar, ce farmec ar avea sa mergi la un concurs la care se stie inca dinainte cine este cel mai bun? Este destul de amuzant sa observi cum fiecare spera sa prinda "o zi buna", iar adversarii sai "o zi proasta".
Este usor sa fii printre cei mai buni atunci cand concursul este usor. Mai greu e sa fii cel mai bun atunci cand concursul este dur, pentru ca atunci intervine - inevitabil - dramul de noroc al fiecaruia. Niciodata insa nu se poate invoca greutatea concursului drept o scuza pentru un eventual esec. Concursul este la fel de greu pentru toti. Se poate intampla, mai ales daca probele dureaza mai multe zile (3-4) ca nici unul din concurenti sa nu acumuleze mai mult de 70-80% din punctajul maxim. Totusi, aceasta nu inseamna ca ei nu sunt bine pregatiti; mai mult, unul dintre ei trebuie sa fie primul. Asadar, niciodata nu trebuie adoptata o strategie de genul "problema asta e grea si n-am s-o pot rezolva perfect, asa ca nu ma mai apuc deloc de ea". Nu trebuie sa va impacientati daca vi se intampla sa nu aveti o idee geniala de rezolvare a unei probleme. Nu va cere nimeni sa faceti perfect o problema, ci numai sa prezentati o solutie care sa acumuleze cat mai multe puncte. Evident, prima varianta este intotdeauna preferabila, dar nu obligatorie.
Niciodata, chiar daca concursul este usor, nu e bine 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. Nu se stie cum pot sa apara erori.
 
* 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 elemente cu toate elementele egale, sau vectori de forma (1, 2, ..., 9 999, 10 000). 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 un numar $N$ si sa creeze un fisier $INPUT.TXT$ 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.
 
* 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. Nu se stie cum pot sa apara erori.
 
* 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$ elemente cu toate elementele egale, sau vectori de forma $(1, 2, ..., 9.999, 10.000)$. 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 un numar $N$ si sa creeze un fisier $INPUT.TXT$ 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 da eroare, se blocheaza (la alocarea unor zone mari de memorie) sau 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 $INPUT.TXT$ si fisierul $OUTPUT.TXT$ 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 (sau, cum spunea Murphy, "cunoasterea solutiei unei probleme poate ajuta in multe cazuri la rezolvarea ei"). 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.
 
 
* In caz ca ati dat o solutie euristica la o problema NP-completa, puteti implementa si un backtracking ca sa vedeti cat de bune sunt rezultatele gasite euristic. Apoi, puteti incepe sa modificati functia euristica pentru a o face cat mai performanta.
h2(#strategii). Strategii in timpul concursului
h2(#strategii). Strategii de abordare a problemelor
Si, ca sa nu mai lungim vorba, iata cateva strategii care par sa dea rezultate.
Si ca sa nu mai lungim vorba, iata cateva strategii care par sa dea rezultate.
h4. A)
h3. A)
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. Daca nu se dau, intrebati imediat. Dimensiunea input-ului poate schimba radical dificultatea problemei. Spre exemplu, pentru un vector cu $N = 100$ elemente, un algoritm $O(N^3^)$ merge rezonabil, pe cand pentru $N = 10 000$ acelasi algoritm ar depasi cu mult cele cateva secunde care se acorda de obicei. Fair-play-ul cere sa puneti intrebarile cu voce tare, pentru ca si ceilalti sa auda; de altfel, nu aveti nici un motiv sa va feriti de ceilalti concurenti. Cei care sunt interesati de aceste intrebari le-ar pune oricum si ei, iar cei care nu sunt interesati vor ignora oricum raspunsul.
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. Daca nu se dau, intrebati imediat. Dimensiunea input-ului poate schimba radical dificultatea problemei. Spre exemplu, pentru un vector cu $N = 100$ elemente, un algoritm $O(N^3^)$ merge rezonabil, pe cand pentru $N = 10.000$ acelasi algoritm ar depasi cu mult cele cateva secunde care se acorda de obicei. Fair-play-ul cere sa puneti intrebarile cu voce tare, pentru ca si ceilalti sa auda; de altfel, nu aveti nici un motiv sa va feriti de ceilalti concurenti. Cei care sunt interesati de aceste intrebari le-ar pune oricum si ei, iar cei care nu sunt interesati vor ignora oricum raspunsul.
Daca exista probleme care cer sa se gaseasca un optim (maxim/minim) al unei valori, intrebati daca se acorda punctaje partiale pentru solutii neoptime. Si acest fapt poate schimba natura problemei. Dupa aceasta,
Daca exista probleme care cer sa se gaseasca un optim (maxim/minim) al unei valori, intrebati daca se acorda punctaje partiale pentru solutii neoptime. Si acest fapt poate schimba natura problemei. Dupa aceasta,
== code(c) |
Nr_probleme_nerezolvate = Nr_probleme_primite;
while ((Nr_probleme_nerezolvate > 0) and  !("Timpul a expirat, va rugam sa salvati"))
{
while ((Nr_probleme_nerezolvate > 0) && !("Timpul a expirat, va rugam sa salvati.")) {
==
h4. B)
h3. B)
Faceti o impartire a timpului pentru problemele ramase proportional cu punctajul fiecarei probleme. In general problemele au punctaje egale, dar nu totdeauna. De exemplu, daca o problema e cotata cu 100 puncte, iar alta cu 50, veti aloca de doua ori mai mult timp primei probleme, chiar daca nu vi se pare prea grea. 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.
h4. C)
h3. C)
Apucati-va de problema _cea mai simpla_, chiar daca e punctata mai slab. Mai bine sa duceti la bun sfarsit o problema usoara si sa luati un punctaj mai mic, decat sa va apucati de o problema grea si sa nu terminati niciuna. 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. Daca, in sfarsit, nu aveti nici o idee la nici o problema, apucati-va de cea mai bine punctata.
Apucati-va de problema _cea mai simpla_, chiar daca e punctata mai slab. Mai bine sa duceti la bun sfarsit o problema usoara si sa luati un punctaj mai mic, decat sa va apucati de o problema grea si sa nu terminati niciuna. 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. Daca, in sfarsit, nu aveti nici o idee la nicio problema, apucati-va de cea mai bine punctata.
h4. D)
h3. D)
Cititi din nou enuntul, de data aceasta cu mare grija. Intrebati supraveghetorul pentru orice nelamurire. Daca anumite lucruri nu sunt specificate, iar profesorul nu va da nici un fel de informatii suplimentare, tratati problema in cazul cel mai general. Iata mai multe exemple frecvente in care enuntul nu este limpede:
* Daca nu se precizeaza cat de mari pot fi intregii dintr-un vector, nu lucrati pe $Integer$, nici pe $Word$, ci pe $LongInt$;
* Daca nu se precizeaza cat de mari pot fi intregii dintr-un vector, nu lucrati pe $int$, ci pe $long long int$;
* In problemele de geometrie analitica, e bine sa presupuneti ca punctele nu au coordonate intregi, ci reale;
* De asemenea, patratele si dreptunghiurile nu au neaparat laturi paralele cu axele, ci sunt asezate oricum in plan (aceasta poate intr-adevar sa complice extrem de mult problema; nu va doresc sa va izbiti de o asemenea neclaritate...);
* Daca fisierul de intrare contine siruri de caractere, sa nu presupuneti ca ele au maxim $255$ de caractere. Mai bine scrieti propria voastra procedura de citire a unui sir de caractere, care sa citeasca din fisier caracter cu caracter pana la $Eoln$, decat sa aveti surprize. Daca $S$ este o variabila de tip $String$, $ReadLn(S)$ ignora tot restul randului care depaseste lungimea lui $S$;
* Daca fisierul de intrare contine siruri de caractere, sa nu presupuneti ca ele au maxim $255$ de caractere. Mai bine scrieti propria voastra procedura de citire a unui sir de caractere, care sa citeasca din fisier caracter cu caracter pana la sfarsitul de linie, decat sa aveti surprize.
* Grafurile nu sunt neorientate, ci orientate. In principiu, enuntul nu are voie sa fie neclar in aceasta privinta, dar au existat cazuri de neintelegere.
h4. E)
h3. E)
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.
Sa presupunem ca timpul de testare este de $5$ secunde, lucrati pe un 486DX4, algoritmul vostru are complexitatea $O(N^3^)$, iar $N$ este maxim $100$. Un 486 face cateva milioane de operatii elementare pe secunda, sa zicem $4 000 000$. Aceasta inseamna ceva mai putine operatii mai costisitoare (atribuiri, comparatii etc.) pe secunda. Sa ne oprim deci la cifra de $1 000 000$. Programul vostru are timp de rulare cubic, iar $N^3^$ este maxim $1 000 000$. De aici deducem ca programul ar trebui sa se incadreze intr-o secunda. Calculul nostru este grosier, dar luand si o marja de eroare arhisuficienta, rezulta ca programul trebuie sa mearga cu usurinta in $5$ secunde, deci algoritmul este acceptabil.
Sa presupunem ca timpul de testare este de $0.5$ secunde, lucrati pe un Pentium 4, algoritmul vostru are complexitatea $O(N^3^)$, iar $N$ este maxim $100$. Un Pentium 4 face in jur de $10.000.000$ de operatii pe secunda. Programul vostru are timp de rulare cubic, iar $N^3^$ este maxim $1.000.000$. De aici deducem ca programul ar trebui sa se incadreze in $0.1$ secunde. Calculul nostru este grosier, dar luand si o marja de eroare arhisuficienta, rezulta ca programul trebuie sa mearga cu usurinta in $0.5$ secunde, deci algoritmul este acceptabil.
h4. F)
h3. F)
Daca algoritmul gasit este greu de implementat, mai cautati un 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 x N$, nu are sens sa va bateti capul ca sa gasiti un algoritm mai bun decat $O(N^2^)$.
h4. G)
h3. G)
Dintre toate ideile de implementare gasite (care se incadreaza fara probleme in timp), o veti alege pe cea mai scurta ca lungime de cod. De exemplu:
* Daca $N ≤ 1 000$ si dispuneti de doi algoritmi, unul pe care il estimati cam la $200$ de linii de program, de complexitate $O(N log N)$ si unul de $100$ de linii de complexitate $O(N^2^)$, cel de-al doilea este evident preferabil, pentru ca nu pierdeti nimic din punctaj, sau cel mult pierdeti un test prin cine stie ce intamplare, in schimb castigati timp pretios pe care il puteti folosi pentru alte probleme. Bineinteles, primul program este mai eficient, dar in conditii de concurs el este prea eficient. Este o mandrie sa faceti o problema perfect chiar daca ratati o alta, dar este un castig si mai mare sa faceti amandoua problemele suficient de bine.
* Daca $N ≤ 1.000$ si dispuneti de doi algoritmi, unul pe care il estimati cam la $200$ de linii de program, de complexitate $O(N*log N)$ si unul de $100$ de linii de complexitate $O(N^2^)$, cel de-al doilea este evident preferabil, pentru ca nu pierdeti nimic din punctaj, sau cel mult pierdeti un test prin cine stie ce intamplare, in schimb castigati timp pretios pe care il puteti folosi pentru alte probleme. Bineinteles, primul program este mai eficient, dar in conditii de concurs el este prea eficient. Este o mandrie sa faceti o problema perfect chiar daca ratati o alta, dar este un castig si mai mare sa faceti amandoua problemele suficient de bine.
h4. H)
h3. H)
In general, pentru orice problema exista cel putin o solutie, fie si una slaba. Sunt numeroase cazurile cand nici 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:
* Sa presupunem ca v-a mai ramas o ora pentru rezolvarea acestei probleme. Calculati cam cat timp v-ar trebui ca sa implementati rezolvarea slaba. Sa zicem 40 de minute. In acest calcul trebuie sa includeti si timpul 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.
 
 
* Mai raman deci 20 de minute, timp in care va puteti gandi la altceva, la alta solutie. 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 mergeti la punctul **F)**. Altfel, la expirarea timpului de 20 de minute, va apucati sa implementati solutia pe care o aveti, oricat de ineficienta ar fi (de fapt, orice solutie, oricat de ineficienta, trebuie sa ia macar o treime sau o jumatate din punctaj, daca nu apar erori de implementare).
 
 
* Puteti, ca o masura extrema, sa depasiti cu maxim 5 minute cele 20 de minute planificate, dar de cele mai multe ori acesta e timp pierdut, deoarece intervine stresul si nu puteti sa va mai concentrati.
h4. I)
h3. I)
Daca ati ajuns pana aici inseamna ca ati optat pentru o varianta de implementare. Din acest moment, pentru aceasta varianta 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. Chiar daca, prin absurd, stiti sigur ca datele de intrare trebuie verificate, mai bine n-o faceti, din mai multe motive. In primul rand, scopul cu care v-a fost data problema este altul decat sa se constate cine verifica mai bine datele de intrare. De aceea, cel mult un test sau doua vor fi cu date gresite. In al doilea rand, nu se justifica sa risipiti atata timp numai pentru cateva puncte pe care le-ati putea pierde daca nu faceti verificarea. In al treilea rand, e posibil sa gresiti oricum problema in sine, caz in care nu mai conteaza daca ati citit perfect datele de intrare. In sfarsit, legea lui Murphy spune ca "oricate teste ar efectua cineva asupra datelor de intrare, se va gasi cineva care sa introduca date gresite". Efortul este deci zadarnic...
 
* Ultimul lucru, cand sunteti convinsi ca programul este terminat si cand v-ati hotarat sa nu il mai modificati, adaugati optiunile de compilare. Puteti face aceasta apasand $Ctrl-O-O$. La inceputul programului vor aparea directivele de compilare. Setati $$B$, $$I$, $$R$ si $$S$ pe - (minus). Eventual, puteti include direct linia $I$B-,I-,R-,S-S$ imediat dupa titlul programului. Aceasta va face compilatorul sa nu mai evalueze complet expresiile booleene, sa nu mai verifice operatiile de intrare/iesire, domeniul de atribuire $(Range Checking)$ si stiva $(Stack Checking)$. Exista doua avantaje majore: in primul rand ca programul merge mai repede (se castiga cateva procente bune la viteza), iar in al doilea rand, psihologic vorbind, este preferabil ca un program sa se blocheze decat sa se opreasca printr-un banal $Range check error$. Nu va grabiti sa puneti directivele de compilare inca de la inceput, deoarece nu veti mai primi mesajele corespunzatoare de eroare si va va fi mai greu sa depanati programul.
 
* Pe cat este posibil, incercati sa convingeti juriul sa nu va ruleze sursa (Pascal sau C/C++), ci direct executabilul. Merge simtitor mai repede. Asta numai in cazul in care va temeti ca programul ar putea sa nu se incadreze in timp.
 
 
* Daca se poate, evitati lucrul cu pointeri. Programele care ii folosesc sunt mai greu de depanat si se pot bloca mult mai usor.
* Sa presupunem ca aveti de lucrat cu matrice de dimensiuni maxim $100 x 100$. Unii elevi au obiceiul sa dimensioneze la inceput matricele de $5 x 5$ sau $10 x 10$, deoarece sunt mai comod de evaluat cu $Evaluate (Ctrl-F4)$ sau $Watch (Ctrl-F7)$. Acest lucru este adevarat, dar exista riscul ca la sfarsit sa uitati sa redimensionati matricele de $100 x 100$. Decat sa faceti o asemenea greseala (care in mod sigur va va compromite toata problema), mai bine setati dimensiunile corecte de la inceput. De altfel, ideal ar fi ca depanarea programelor sa fie suprimata cu totul si programul sa mearga din prima.
 
* Evitati lucrul cu numere reale, daca puteti. Operatiile in virgula mobila sunt  mult mai lente. De exemplu, testul daca un numar este prim nu va incepe in nici un caz cu linia
 
* Evitati lucrul cu numere reale, daca puteti. Operatiile in virgula mobila sunt mult mai lente. De exemplu, testul daca un numar este prim nu va incepe in nici un caz cu linia
==code(c) |
while (i <= sqrt(N))
while (i <= sqrt(N))
==
ci cu linia
deoarece pot aparea erori, ci implementati o functie:
==code(c) |
int equal(float R1, float R2)
{
    if (abs(R1 - R2) < 1e-4)   // 1e-4 = 0.00001
int equal(double R1, double R2) {
    if (fabs(R1 - R2) < 1e-4) // 1e-4 = 0.0001
        return 1;
    return 0;
}
==
Numarul de zerouri de dupa virgula trebuie sa fie suficient de mare astfel incat doua numere diferite sa nu fie tratate drept egale (se poate lucra de pilda cu $0.000001$).
Numarul de zerouri de dupa virgula trebuie sa fie suficient de mare astfel incat doua numere diferite sa nu fie tratate drept egale (se poate lucra de pilda cu $0.0000001$).
* Tot in cazul numerelor reale, evitati pe cat posibil sa faceti impartiri, deoarece sunt foarte greoaie. De exemplu:
	$X / 5 <=> 0.2 * X$
	$X / Y / Z <=> X / (Y * Z)$
$X / 5 <=> 0.2 * X$
$X / Y / Z <=> X / (Y * Z)$
* Optimizarile de genul $X shl 1$ respectiv $X << 1$ in loc de $2 * X$ sunt niste artificii de cele mai multe ori neesentiale, care in schimb fac formulele mai lungi, greu de urmarit si pot crea complicatii. Cel mai bine este sa lucrati cu notatiile obisnuite si doar la sfarsit, daca timpul de rulare trebuie redus cu orice pret, sa faceti inlocuirile.
* Alegeti-va numele de variabile in asa fel incat programul sa fie clar. Sunt permise mai mult de doua litere! Numele fiecarei proceduri, functii, variabile trebuie sa-i explice clar utilitatea. E drept, lungimea programului creste, dar codul devine mult mai limpede si timpul de depanare scade foarte mult. Ca o regula generala, claritatea programelor face mult mai usoara intelegerea lor chiar si dupa o perioada mai indelungata de timp (luni, ani). Nu trebuie nici sa cadeti in cealalta extrema. De exemplu, nu depasiti 10 caractere pentru un nume de variabila.
 
 
* Salvati programul cat mai des. Daca va obisnuiti, chiar la fiecare doua-trei linii. Dupa ce o sa va intre in reflex n-o sa va mai incomodeze cu nimic acest obicei, mai ales ca in ziua de azi salvarea unui program de 2-3 KB se face practic instantaneu. Au fost frecvente cazurile 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.
 
 
* 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. 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 doua-trei teste oarecare. E pacat sa pierdeti puncte dintr-o greseala copilareasca.
 
* O situatie 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 ii 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. Uneori comisia este binevoitoare si accepta sa modifice fisierul de date, taind din el setul pe care programul vostru nu merge, dar acest lucru este greoi si nu tocmai cinstit fata de ceilalti concurenti, deci nu va bazati pe asta.
* 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 (fie prin comanda $Flush$, fie prin doua proceduri, $Close$ si $Append$). 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.
 
* Daca fisierul de iesire are dimensiuni foarte mari, de exemplu daca vi se cer toate solutiile, iar numarul acestora este de ordinul zecilor de mii, puteti avea surpriza ca timpul sa nu va ajunga pentru a le tipari pe toate in fisierul de iesire. Si in acest caz, este recomandat ca dupa tiparirea fiecarei solutii sa executati comanda $Flush$, sau sa inchideti fisierul de iesire si sa-l redeschideti in modul $Append$.
* O situatie 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 ii 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 evaluatorul comisiei, deci din nou veti pierde toate testele care au ramas neexecutate.
h4. J)
* 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 (prin comanda $fflush$). 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.
 
* Daca fisierul de iesire are dimensiuni foarte mari, de exemplu daca vi se cer toate solutiile, iar numarul acestora este de ordinul zecilor de mii, puteti avea surpriza ca timpul sa nu va ajunga pentru a le tipari pe toate in fisierul de iesire. Si in acest caz, este recomandat ca dupa tiparirea fiecarei solutii sa executati comanda $fflush$, sau sa inchideti fisierul de iesire si sa-l redeschideti in modul $append$.
 
h3. J)
Daca ati trecut cu bine si de faza de scriere a programului, mai aveti doar partile de depanare si testare, care de multe ori se imbina. Metoda cea mai 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 (minim 4 teste si maxim 7-8). Daca le trece si pe acestea, puteti fi mandri. Legile lui Murphy in programare se aplica in continuare: "Depanarea nu poate demonstra ca un program merge; ea poate cel mult demonstra ca un program nu merge". Totusi, daca programul vostru a mers perfect pe 7-8 teste date la intamplare, exista sanse foarte 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. In culegere nu a fost explicat pe larg algoritmul decat pe exemplul din enuntul fiecarei probleme, dar aceasta s-a facut numai pentru a nu supraincarca materialul.
 
* Exemplul dat in enunt nu are in general nicio 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. In culegere nu a fost explicat pe larg algoritmul decat pe exemplul din enuntul fiecarei probleme, dar aceasta s-a facut numai pentru a nu supraincarca materialul.
* 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.
* 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 (pe jumatate, de exemplu) si treceti la problema urmatoare.
**K)**
h3. K)
==code(c) |
Nr_probleme_nerezolvate--;
    Nr_probleme_nerezolvate--;
}
==
h2(#concluzii). Concluzii
Probabil nu veti fi de acord cu toate sfaturile date mai sus. E bine insa sa le aplicati. Scopul pentru care ele au fost incluse in aceasta carte este de a ajuta concurentii sa se acomodeze mai usor cu atmosfera concursului. 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. Poate ca aceste ponturi va vor fi de folos.
Probabil nu veti fi de acord cu toate sfaturile date mai sus. E bine insa sa le aplicati. Scopul pentru care ele au fost impartasite este de a ajuta concurentii sa se acomodeze mai usor cu atmosfera concursului. 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. Sper ca aceste ponturi va vor fi de folos.

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3719