Cum să nu iei 0 puncte la olimpiada de informatică

Posted on Posted in Uncategorized
În data de 18 februarie am ținut un workshop despre cum să îți crești șansele de a lua un punctaj mai mare la olimpiada de informatică. Workshopul a fost filmat și se găsește pe pagina noastră de Facebook. Voi încerca să prezint mai jos conținutul. Le mulțumesc lui Alex Vasiu și lui Horea Ștefan pentru corecturi.

Despre olimpiadă

Olimpiada de informatică este printre puținele olimpiade la care evaluarea este automată. Un program evaluează programele scrise de fiecare elev și acordă un punctaj de la 0 la 100 de puncte la fiecare soluție pentru o problemă. Pentru mine lucrul acesta a fost un mare câștig întrucât profesorii se plângeau aproape la fiecare test că scriu urât și că nu îmi pot citi scrisul. Un alt mare avantaj al olimpiadei e că nu mai depinzi de profesorul corector. Toate soluțiile unei probleme sunt verificate pe aceleași date de intrare și aceiași parametri astfel toți concurenții beneficiază de condiții egale. Fiecare problemă are un număr de teste iar fiecare test un anumit punctaj. Pentru a primi punctajul pentru un test, programul trebuie să se compileze, să se încadreze în limita de timp, în limita de memorie și să afișeze răspunsul corect. Aceste lucruri fac ca indiferent ce ai scris in program, dacă afișezi răspunsul corect primești punctajul. Totuși chiar dacă ai rezolvat problema corect, poți din cauza unor greșeli de neatenție să iei 0 puncte. De-a lungul timpului au fost mai multe cazuri de olimpici, unii dintre ei chiar și cu medalii la competiții internaționale, care nu au trecut de faza județeană din cauza greșelilor.

Cum mă pregătesc acasă

Pentru a elimina măcar o parte din stresul de dinaintea probei, e foarte important să cunoaștem regulile pe care trebuie să le respectăm. Ele se găsesc pe site-ul olimpiada.info și în general sunt publicate de asemenea de către inspectorate. Unul dintre cele mai importante lucruri precizate în regulament este versiunea compilatorului. Pentru a reduce riscul de surprize neplăcute, e bine să folosim acasă aceeași versiune de compilator (o găsiți aici) cu cea de la olimpiadă. Versiunile diferite pot duce la erori de compilare la evaluare deci la obținerea punctajului nul. De ce e important să le știm:
      Avem voie să folosim standardul c++ 11 (
unordered_set
      ,
for auto
    și multe alte funcționalități utile care ne ușurează munca)
Nu avem voie să folosim alte surse de informare decât help-ul.
    În cazul unei descalificări pierzi dreptul de a participa și în anul următor
    Multe altele pe care e bine să le citești direct din regulament

La intrarea în sală

La intrarea în sală e foarte indicat să predați orice materiale pentru care ați putea fi descalificați. Aici intră telefoane/stick-uri și orice sursă de inspirație. Verificați să aveți help-ul pe stația de lucru. E foarte neplăcut să îți dai seama în timpul probei că ai uitat cum se transmite funcțiea de comparare pentru priority_queue. E și mai neplăcut să nu ai unde să cauți. Verificați buna funcționare a compilatorului și a mediului de programare. Nu vreți ca atunci când încercați să creați un fișier să nu aveți permisiunile necesare. Orice problemă ați avea, e important să o anunțați înainte de începerea probei. Supraveghetorii nu au voie să vă ajute în timpul concursului. Fiți atenți la explicațiile de la început legate de modul în care trebuie să salvați fișierele sursă. În cazul în care nu sunteți siguri că le-ați înțeles, întrebați supraveghetorii până când vă este 100% clar.

În timpul probei

Cum verifici limita de timp?

Din fericire Codeblocks afișează după fiecare rulare durata de execuție. Nu e necesar să ne batem capul cu acest lucru. Putem să scriem un program care să genereze un fișier de intrare cu testul maxim. Folosindu-ne de acest fișier, putem verifica durata de execuție a soluției.

Cum verifici limita de memorie

int matrice[50][50]; cout<<sizeof(matrice)/1024; // afișează memoria folosită în kb. cout<<sizeof(matrice)/(1024*1024); // afișează memoria folosită în mb. Deoarece programul folosește memorie în plus pe lângă variabilele declarate, e bine să împărțim la 1000.

Cum verifici limita de memorie pentru stivă

Variabilele alocate în interiorul funcțiilor sau transmise ca parametru sunt alocate pe stivă. Pentru a nu avea bătăi de cap, putem să declarăm toate matricile și vectorii globale.

Testarea automată

De cele mai multe ori este insuficient să testăm programul doar pe exemplele problemei. Un prim pas este să ne construim manual alte exemple. Totuși nu putem fi siguri că nu am ratat vreun caz în construirea exemplelor. Cel mai indicat este să scriem niște programe care să verifice pentru noi corectitudinea soluției. Pentru aceasta recomand împărțirea funcționalității evaluatorului în următoarele programe: Generator
    – va genera fișiere de intrare care vor conține date aleatoare care respectă restricțiile problemei.
Brut
      – o soluție scurtă și nu neapărat eficientă de care suntem
100%
    siguri că este corectă
Soluție
    – soluția pe care vrem să o verificăm și pe care o vom preda pentru evaluare
Verificator
    – un program care citește fișierele produse de Brut și de Soluție și verifică să coincidă
Acestea pot fi proiecte separate în codeblocks. Fiecare dintre aceste proiecte va genera câte un executabil. Executabilul îl găsim în folderul bin\debug din interiorul proiectului. Pentru a testa este nevoie să executăm generatorul, să rulăm brutul și soluția pe datele produse de generator și să le verificăm cu ajutorul verificatorului. Întrucât vrem să facem asta de mai multe ori, e nevoie să executăm pașii de mai sus automat. Astfel vom copia executabilul fiecărui proiect într-un folder unde vom face evaluarea. În interiorul folderului, vom crea un fișier eval.bat care va executa pașii pentru noi. Conținutul fișierului va fi următorul: @echo off :start Generator.exe Brut.exe Solutie.exe Verificator.exe goto start Un exemplu complet de evaluator pentru problema subsecvență de sumă maximă se găsește aici.

Ce nu putem testa automat?

Din păcate nu (chiar) toate lucrurile pot fi testate automat. Lucrurile la care trebuie să fim atenți sunt:
    Overflow – atunci când rezultatul calculelor nu încape în tipul de date folosit (de exemplu dacă îl ridicăm pe 10^9 la pătrat)
    Numele fișierelor de intrare – atenție la lucruri de genul suma.in/sume.in sau la spațiile de la finalul numelui
    Numele fișierelor sursă – trebuie să fie codificate așa cum v-au explicat supraveghetorii la început
    Timpul și memoria despre care am vorbit deja
    Dimensiunea maximă a sursei
În cazul în care aveți întrebări, completări sau păreri, vă rog să lăsați un comentariu…

Leave a Reply

Your email address will not be published. Required fields are marked *