Î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%
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…