[Linux]Cum sa-ti testezi programele la ONI

Recent am invatat niste chestii foarte misto la faculta care pot fi aplicate cu succes la ONI pentru scrisul rapid al generatoarelor si evaluatoarelor. Provocare pentru cei care n-au ce face: faceti aceleasi chestii pe windows.

Prima chestie pe care e bine s-o aveti in minte e ca nu trebuie sa memorati pasii/comenzile pentur scrierea unui generator, fiecare comanda are pe linux un manual complet de folosire. Puteti sa-l accesati asa:

man comanda

.

Prima data incepeti prin a genera un numar de teste(de ex 100):

//generator pentru problema max square
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <cstdio>
using namespace std;

int n;

int main() {
	for(int t=1; t<=100; ++t) {
		char in[55];
		ofstream g(in);
		sprintf(in,"%d.in",t);
		n=rand()%50+1;
		g<<n<<'\n';
		for(int i=1; i<=n; ++i) {
			for(int j=1; j<=n; ++j) g<<rand()%100-rand()%100<<' ';
			g<<'\n';
		}
	}
}

Acum trebuie sa generam .ok-urile cu un program brut si pe urma sa verificam daca outputul programului bun coincide cu cel din ok. In bash putem redirectiona fisiere catre stdin si stdout catre un fisier(ca si la freopen).

g++ brut.cpp#compilam programul, va genera executabilul a.out
for i in {1..100}; do
	./a.out < $i.in > $i.ok
done

Avand fisierele .ok trebuie sa verificam ca programul sa produca acelasi output.

g++ bun.cpp
for i in {1..100}; do
	echo $i #ce test a fost verificat
	./a.out < $i.in > output
	diff $i.ok output#in caz ca fisierele difera va aparea un mesaj
done

In caz ca vrem sa afisam doar testele pe care pica putem modifica scriptul in felul urmator:

g++ bun.cpp
for i in {1..100}; do
	./a.out < $i.in > output
	if ! diff -q $i.ok output
	then echo "testul $i pica"
	fi
done

 

Oni 2013 si nu numai

La fel ca în fiecare an și anul ăsta a fost înca un oni. Nu sunt supărat din cauza rezultatului meu, ci sunt chiar bucuros pentru că subiectele de la 11-12 au fost cu mult mai reușite decât cele de anul trecut, iar eu nu mă așteptam la prea mult de la oni-ul de anul ăsta.

Deși România are rezultate foarte bune la competițiile internaționale mie mi se pare că sunt destule probleme în sistemul de selecție.

Cea mai mare problema cred eu că este selecția participanților la olimpiada județeană. Cunosc multi oameni care s-au apucat de informatică după ce s-au calificat la ONI. În multe județe locurile sunt distribuite neuniform. De exemplu in Bucuresti la clasa a 11-a au fost prea puține locuri în timp ce clasa a 9-a a avut 10 locuri.

Părerea mea e că problema s-ar putea rezolva destul de simplu aplicându-se același algoritm un algoritm asemănător (nu sunt de acord cu algoritmul folosit in prezent deoarece fiecare judet poate crește/scădea doar cu un loc) doar că independent pentru fiecare clasă. De exemplu dacă anul trecut un județ a avut rezultate bune la a 10-a, anul următor clasa a 11-a va avea locuri in plus. La clasa a 9-a cred că ar trebui sa fie făcută o medie a rezultatelor județului din anii trecuți de la clasa a 9-a. Din câte știu eu în ultimii doi ani dintre cei care au fost in lot in anul precedent cel putin doi oameni nu au mai trecut de oji. De aici ne dăm seama că selecția pentru oni sau selecția loturilor (sau ambele 🙂 ) nu sunt făcute cum ar trebui.

Din moment ce la olimpiadele și concursurile internaționale exista feedback parțial mi s-ar părea normal ca și la selecția pentru ele să existe feedback. Mi se pare o prostie sa iei 0 puncte pe o problemă pentru că ai MLE sau pentru că nu ai respectat cu strictețe formatul fișierului de ieșire. Totuși aici sunt subiectiv pentru că am fost în ambele situații.

Cred că problema asta s-ar putea rezolva destul de ușor la oji din moment ce toate calculatoarele dintr-o școală sunt conectate la o rețea. La oni ar exista două soluții: Evaluator local care ar cripta(hashui)  fișierul .out si verificator in caz că sunt mai multe răspunsuri posibile sau o rețea de calculatoare la oni. Rețeaua ar necesita o investiție dar pe urmă ar putea fi folosită la mai multe ediții.

O problemă destul de mare mi se pare că e selecția lotului. În ultimii doi ani după noua metodă de selecție în care se ține cont și de rezultatul de la oni mulți de clasa a 9-a sau a 10-a îi depășesc pe cei mai mari datorită coeficientului. Mi se pare nedrept să departajezi elevi după subiecte diferite și relativ față de ceilalți din generația lor. Cred că ar fi mult mai potrivită înlocuirea zilei de pauză cu o probă de baraj sau un set de probleme mai numeros.

Totuși chiar și cu 3 probleme s-ar putea face o departajare bună dacă comisia ar prezenta un set de probleme cu teste bine realizate și cu probleme bine calibrate ca și dificultate.

În plus atât timp cât nu exista feedback nu sunt de acord cu problemele interactive deoarece nu prea ai cum să-ți dai seama că interacționezi corect cu programul comisiei. De exemplu anul ăsta au fost foarte multe punctaje de 0 (http://oni2013.info.tm/r_b.pdf) la o problemă la care era destul de simplu sa iei 40 puncte din cauză că uita să citească un 1 afișat de programul comisiei, iar exemplul de pe foaie nu era prea cuprinzător.

 

Cum sa testezi programele la OJI

Sa zicem ca ai terminat de rezolvat problemele si acum vrei sa le testezi sa vezi daca sunt corecte. Pentru fiecare problema ar trebui sa ai 3 surse: generatorul de teste, solutia propriu zisa si un brut care sa verifice daca solutia e curecta.

In continuare o sa exemplific o metoda destul de buna de testat cod

 

Cum sa furi puncte la OJI

Incep o serie de articole despre olimpiade care sper sa fie folositoare.

La oji fiind doar doua probleme diferentele de punctaj sunt destul de mici in general, iar deseori unele mici “optimizari” fac departajarea intre  concurenti, diferentele intre calificare si necalificare fiind cateodata mai mici de 10 puncte. Deseori unii concurenti pierd timpul cu probleme peste nivelul lor in loc sa incerce sa-si imbunatateasca punctajul deja obtinut sau sa ia puncte pe solutii proaste sau neoptime. Cateodata acest lucru ii face sa rateze calificarea, iar judetul sa trimita la ONI concurenti mai slab pregatiti care si-au folosit timpul in mod util in timpul probei.

Sa presupunem ca esti la OJI si nu te prinzi de probleme

1. Nu te nelinisti, cel mai probabil nimeni nu s-a prins de toate problemele
2. Implementeaza solutii ineficiente din punct de vedere al timpului.
3. Tratati cazuri particulare: n=1, n=m. La multe probleme se specifica formatul testelor si puteti lua puncte tratand cazurile particulare.
4. Rezolvati cerintele partiale (pentru afisarea corecta a primului numar se acorda 10% din punctaj)
5. Citirea fara streamuri merge mai bine la oji din cate stiu eu

Banuiesc ca astea sunt  stiute de multa lume. Totusi mai exista cateva trucuri prin care iti poti mari si mai mult punctajul.

1. In caz ca algoritmul tau e ineficient din punct de vedere al timpului, nu il lasa la evaluare sa ia tle. Opreste-l dupa 2 000 000 calcule(n=min(n,2 000 000)). Asa nu vei pierde punctajele partiale pentru celelalte cerinte si ai sanse destul de mari sa mai prinzi teste.
2. Poti sa iei puncte cu greedy-uri gresite. Totusi incearca sa le imbunatatesti. De exemplu pentru siruri poti rula si de la inceput la sfarsit un algoritm si de la sfarsit la inceput pentru a gasi mai bine optimul. Incearca sa combini mai multe strategii, totusi nu pierde timpul cu tratarea multor cazuri particulare pentru ca pierzi mult timp pe care l-ai putea folosi la rezolvarea altor probleme.
3. Optimizeaza solutiile ineficiente. Cauta liniile care se executa cel mai des si incearca sa optimizezi continutul lor.  Nu uita sa dai break acolo unde programul se executa degeaba. Incearca sa nu faci nici un calcul in plus.
4. Parseaza citirea(fread citeste TOATE caracterele din fisierul de intrare(inclusiv ‘\n’) de aceea merge mai rapid decat functiile obisnuite de citire):

   //
   FILE* fin=fopen("color4.in","r");
   const unsigned maxb=30000192;
   char buf[maxb];
   unsigned ptr=maxb;
   
   inline unsigned getInt(){
       unsigned nr=0;
       while(buf[ptr]<'0'||'9'<buf[ptr])         if(++ptr>=maxb)
               fread(buf,maxb,1,fin),ptr=0;
       while('0'<=buf[ptr]&&buf[ptr]<='9'){         nr=nr*10+buf[ptr]-'0';         if(++ptr>=maxb)
               fread(buf,maxb,1,fin),ptr=0;
       }
       return nr;
   }
   //

   Pentru a citi

   n=getInt()

5. In putine cazuri daca programul e ineficient din punct de vedere al memoriei, poti sa citesti fisierul de mai multe ori (fseek pt citire fara streamuri si f.close(), f.open() ) pentru streamuri.
6. Daca ai o dinamica in n^2 in care scoti minimul de la 0 la i si nu intra in timp, scoate-l de la i-200 pana la i. Deseori se pot obtine 100 puncte asa.
7. Incearca sa eviti folosirea stl-ului daca esti la limita cu timpul. Chiar daca compexitatea operatiilor pe set e log N, in multe cazuri merge foarte rau.

Sper sa ajute 😀