Gruparea testelor in concurs!

[•devilkind]

Stiu ca multi concurenti la preoni finala au fost dezamagiti de gruparea testelor (inclusiv eu). Am avut o discutie cu Cristi Strat pe tema aceasta inainte de premiere si el mi-a zis ca acest lucru s-a facut ptr ca asa e si la IOI. Exista insa si alte argumente impotriva acelei grupari care nu mi-au venit in minte atunci pe moment si anume numarul de teste care se dau la IOI. E adevarat ca nu am fost niciodata si nu cred ca voi ajunge vreodata dar oricum nu cred ca sunt 6 grupari cum au fost la sate. Sau cum a fost la branza unde primele 6 teste erau in 2 grupe de cate 3. Ar trebui ca in concursuri sa fie f multe teste (25-50) si mai multe grupe (vreo 10 asa) pentru a se putea face o departajare mai klumea.

[•filipb]

La sate un grup a fost facut in asa fel incat sa cada cat mai multe bulaneli. Fiecare test dintr-un grup difera prin structura lui. Cred ca la un concurs national e corect asa: decat sa iei 80 cu o solutie greedy dupa nu stiu ce criteriu penal... O complexitate O(N^3) insa lua 45 de puncte. E mai motivant asa, sa scrieti sursa de care sunteti siguri ca e corecta chiar daca nu e optima, decat sa va duca capul la tot felul de bulaneli.
Sa incercati sa picati pe o solutie partiala e mult mai avantajos decat sa prindeti mai multe puncte din noroc.

[•devilkind]

da, dar stim cu toti ca implementari diferite aduc timpi diferiti chiar dak in mare ideea e cam aceeasi, si e cam naspa ca dintr-o grupare de 3 teste sa iei numai 2. In plus e destul de greu ptr comisie sa se gandeasca la toate cazurile particulare care pot aparea in diferitele abordari ale unei probleme si poate acea solutia lua 70-80 puncte, adica in mare parte e corecta, dar deoarece cand s-a facut gruparea nu s-a luat in calcul acel caz particular el se gaseste in majoritatea grupelor si atunci solutia ia in jur de 30 de puncte poate chiar 0. Cred ca ar trebuie date teste mai multe si implicit grupari mai multe ptr o departajare mai corecta, chiar la sate sunt numai 6 punctaje posibile, adica echivalent cu o problema data la ONI cu 6 teste bine gandite, dar ce faci cu departajarea (mai ales akum ca avem si rating, departajarea concurentilor ar trebui sa fie cat de cat o prioritate)

[•cezar305]

La sate scria la restrictii clar ca 45% din teste au n<300 ... foarte adevarat ... deci intra n^3 in mod normal in acele teste. Eu am facut sate in o(n^3) si intradevar ... am luat 9 teste ... dar nu si 45 de puncte   ... ci doar 15... si testele au avut ori non zero exit status (am folosit memorie mica este adevarat) ori TLE la primele teste... Deci sigur au fost grupate bine testele? nu cred sa fi vazut mai mult de 5 persoane cu 45 pana acu... si au fost trimise 9 pagini... Oricum ... concursul a fost extraordinar... probleme frumoase si fun... cazare nemaipomenita...    asa ca nu tre sa ne batem capul ca asta  

P.S. " Nu-i Stres "

[•filipb]

La sate, primul test pe care iei TLE are N = 60 si M = 6. Erau 11 teste care aveau N <= 300 si O(N^3) lua exact 45 de puncte.

[•Protoman]

Aha deci gresesc in alta parte... oricum nu conteaza ca o s-o duc intr-un final la capat ... Mult spor pentru concursurile viitoare

[•sima_cotizo]

Eu unul m-am gandit de la inceput la solutia (corecta) cu BF in O(N+M), dar am gresit la citire... si totusi cineva care nu imi vede sursa si vede ca am cate un test picat la 4 grupe poate trage usor concluzia ca am "bulanit"... eu unul nu sunt in masura sa ma plang, sunt unul din acele cazuri aparte de pierdut puncte la gruparea testelor... dar parca se puteau da mai multe teste, nu ?

[•svalentin]

Mie mi se pare buna ideea e a grupa testele. Aceasta idee nu trebuie neaparat sa fie folosita sa pice 'bulaneli', poti sa ai de exemplu 2 sau 3 modalitati de a genera grafuri - o metoda scoate grafuri rare, alta grafuri dense, alta le scoate gen clici conectate, etc - si fiecare generator de teste sa aiba un test dintr-o grupare de teste.
Nu uitati, ca ideea de a grupa testele se poate face direct din problema (multiple input), dar asa poti vedea mai clar ca ai picat x teste din cele y din grupa; in loc sa vezi ca ai picat toata grupa.

Intradevar, numarul de teste e frumos sa fie cat mai mare, dar la probleme cu timpi de executie de cateva secunde, incerci sa mai reduci numarul de teste ca sa nu plictisesti concurentii la evaluare

[•peanutz]

De ce nu incercati sa puneti 3-4 teste intr-un fisier de intrare.. Asa ar fi si numar de teste mare si nici n-ar mai comenta nimeni... Si eu sunt contra gruparii.

[•svalentin]

De ce nu incercati sa puneti 3-4 teste intr-un fisier de intrare..

3-4 teste intr-un fisier de intrare sau 3-4 teste pe grupa este exact acelasi lucru, doar ca in varianta cu grupa poti sa vezi care din cele 3-4 teste ti-a picat exact

[•peanutz]

La pregatire(adica in arhiva) sunt de-acord cu gruparea testelor, dar aici vorbim de concurs unde te intereseaza punctajul si nu numarul testului care ti-a picat..

[•devilkind]

nu mi se pare o idee buna faza cu mai multe teste intrun fisier, e cam greu sa iti calculezi complexitatea si sa stii daca problema iti va intra sau nu in timp, de fapt sunt total impotriva acestei idei. Faza cu gruparea e buna pana la un anumit punct, nush opinia mea ca ar trebui date mai multe teste si implicit mai multe grupari si treaba s-ar rezolva cat de cat.

[•Cosmin]

Gruparea testelor simplifica treaba pt ca, daca ai idee de un test mic care busheste o rezolvare greedy, si un test mare care busheste o rezolvare brute force, le pui in fisiere diferite si atunci bushesti si rezolvarea greedy si rezolvarea brute force. Daca le-ai pune in acelasi fisier atunci rezolvarea brute force are timp dublu pentru testul mare, si e mai greu de bushit.