infoarena

Va multumim ca ati participat la ONIS 2015 Runda 1.

Stim ca am avut foarte multe probleme sub forma deficientelor in enunturi. Ne cerem scuze. Consideram ca toate problemele au iesit destul de bine mai putin Por Costel si Invazia Extraterestra.

La problema aceasta, testul final a fost generat in graba pe ultima suta de metri iar N-ul era 3 * 10^5, nu 10^5 asa cum spunea enuntul. Ne-am dat seama foarte tarziu de ast. O alta problema este faptul ca a intrat brute-ul de M^2, care ne-a scapat din vedere cand am coneput testul. Solutia intended presupune mentinerea unui arbore de intervale cu stiva in fiecare nod.  In timp ce unii dintre voi se munceau si nu le intra multiset-ul, altii luau 100 cu brute. E un lucru inacceptabil si o greseala pe care ne-o asumam. "The least we can do" este sa reevaluam sursele de la problema asta cu un test care respecta cerintele initiale N <= 10^5, si toata lumea va lua 100 cu prima submisie corecta care respecta restrictia, inclusiv cei cu solutia brute. Nu ar fi cinstit fata de ei sa le doboram solutiile.

Cu toate acestea vrem sa auzim si ce aveti voi de spus despre runda. Asteptam feedback aici :)

Problemele au fost prea grele pentru o runda de calificare!

Problema Meciul = Varianta usoara a http://codeforces.com/gym/100513/problem/A.

Meciul se facea cu paduri de multimi? Care era complexitatea oficiala la livada?

Mie mi s-au parut ok problemele.La invazie, nu ma prind cum vine cu stiva in aint dar banuiesc ca intra si tractrul cu aint persistent pe care n-am avut timp sa-l bag :)).La cenzura, m-am prins ca era ceva de genul n-are rost sa iei decat capatul unui cuvant, dar n-am apucat sa ma gandesc mai mult la ea, desi parea cea mai interesanta.Mi-a placut, de asemenea foarte mult si bujor.Felicitari pentru runda, in rest, si prin asta ma refer la faptul ca a intrat brute-ul pe invazie, ceea ce ma oftica.daca stiam bagam si eu brut :))

In primul rand,felicitari pentru runda ! In al doilea rand,speram doar ca sursele sa obtina 100 la invazie ( cele cu persistence tree ).Cat mai dureaza pana cand clasamentul va fi oficial ?

 @CompilationTerror: Pare rau, de obicei sunt la curent cu ce se da. Nu ma uitasem pe NEERC inca anul asta.

Inca ceva, mi s-ar parea mai ok sa nu se numere si sursele cu eroare de compilare sau de exemplu care n-afiseaza nimic(adica am folosit alte fisiere sau deloc).Eu am luat fisier lipsa la prima doar pentru ca am comentat freopenul din obisnuinta

Complexitatae oficiala la livada este N*M^2 intr-adevar. Sursele oficiale au timp 1.1 respectiv 1.4 secunde asa ca 2.4 secunde ni s-a parut un timp bun. Se pare ca ne-am inselat.

Salut!
am cateva intrebari:
la problema meciul se putea face si online?
la bujor, un gauss mergea in o(n^3), dar am observat ca trebuie calculata inversa matricei, pentru care nu am gasit un algoritm mai bun de o(n^4), (fara gauss). Puteam sa ma folosesc de observatia asta?

La bujor, eu am facut gauss fara coloana cu rezultatele(pe care ai un 1 si multi de 0 in general) si practic aia era forma generala a matricei iar tu chimbai doar coloana cu rezultate.Retineai ce operatii faceai la gauss-ul normal si cand voiai pentru o configuratie fixa de rezultate sa vezi solutia, simulai mai intai toate operatii(doar pe coloana aia) si apoi le gaseai.Mi s-a parut mega-smechera ideea :)

cu gauss am facut-o pana la urma, fix pe ideea pe care ai descris-o.
dar ma gandeam ca daca coloana termenilor liberi este: un element 1 iar celalate zero, atunci matricea pe care vreau sa o calcluez este chiar inversa matricei citite (matricea B este inversa matricii A daca si numai daca A*B=B*A=In (In=matricea unitate, cu 1 pe diagonala principala si 0 in rest)).

Daca am inteles bine ce zici, e inversa doar cand ai elementul de 1 pe undeva pe diagonala ceea ce e dubios ca e matrice de N pe N + 1

eu ma refeream la inversa matricii citite, care e N*N, nu la matricea de la gauss.

Da, intr-adevar inversa matricei B e unul din raspunsurile posibile.
Se poate rezolva in O(N^3) cu o variatie de Gauss: http://en.wikipedia.org/wiki/Gaussian_elimination ceea ce este similar cu ce ati facut amandoi.

Clasamentul a fost dezghetat. Puteti vizualiza rezultatele finale!

No bine, problemele o fost destul de ferchese, si a fost o placere pentru noi sa mai luam o pauza de la cantat pe la nunti si botezuri si sa participam la aist concurs de mare amploare. Salutari din Finteusu Mare! Asteptam runda 2!

La Pinball, de ce era limita de timp asa mare? Se putea face in O(N + M) :) Also, ati avut o idee buna sa nu dati elemente egale, altfel problema devenea foarte jegoasa si plina de cazulete.

Pentru cine e suficient de masochist sa rezolve problema in cazul cu elemente egale, puteti incerca aici: http://www.spoj.com/problems/HILO/

Au fost dragute problemele, mi-au placut in special cea cu livada si cea cu meciul. Felicitari pentru runda!

+1 corul_barbatesc

Da, si solutia noastra e O(N+M) la pinball. Dar ,vezi , unii ne acuza ca punem timpi prea mari, unii ca punem timpi prea mici. :)) E greu sa satisfaci pe toata lumea.

Felicitari pentru runda, a fost reusita :) cand se adauga problemele in arhiva?

Exista o discrepanta intre cei care au facut problema invazie cum trebuie si cei ce au bagat brut.
Ideea este ca poate o faceau mai multi cu brut, dar cei mai incercati se chinuiau sa gaseasca o structura de date care sa optimizeze operatiile.

Dupa parerea noastra, ar trebui sa se puncteze doar solutiile corecte.

Nu ar fi corect nici fata de cei care au rezolvat-o sa se trezeasca cu ea nefacuta. Oricum cei care au facut-o cu brut sunt destul de jos in clasament si nu cred ca vor afecta clasamentul pe parcursul turneului. Si da, stiu ca sunt un prost. :))

Felicitari pentru runda si pentru enunturile simpatice!

PS: Poza nu era pentru tine :D

Problemele se gasesc acum in arhiva ACM. Probabil o sa schimbam testele la Invazia ca macar in arhiva sa fie trecuta cu teste bune.

Care-i treaba cu porcul?

https://www.facebook.com/profile.php?id=100006026297750&fref=nf

Eu zic ca nivelul rundei a fost prea ridicat.
Ar prinde bine surse libere si articol cu solutii.

A fost mult mai bine decat anul trecut, unde de cele mai multe ori doar trebuia sa scrii cod, nu aveai de ce sa te prinzi. Cred ca e mai important sa se dea probleme care pun accentul mai mult pe gandire decat pe scris cod si suntem de parere ca autorii rundei de astazi au reusit acest lucru.  :peacefingers:

EDIT Silviu: Draga comisie, ne-au placut mult problemele, dar acum aveti responsabilitatea sa mai faceti runde din astea!! Pana atunci, de la noi aveti 3 DA  :winner1:  :winner1:  :winner1:

Pot sa spun ca ideile de rezolvare au fost destul de originale si foarte variate. Cred ca un astfel de concurs nu trebuie sa fie usor, deoarece pana la urma scopul sau este de a simula lucrul in echipa la un posibil viitor concurs pe echipe (ACM), deci din acest punct de vedere si-a atins scopul. Ok, poate au fost cam grele problemele, si ce? Un concurs este cu atat mai util, cu cat sunt mai multe probleme pe care nu le stii face, deoarece astfel vei avea lucruri noi de invatat din ele. Singura obiectie ar fi la problema Invazie, la care ma bucur ca autorii s-au sesizat si si-au cerut scuze, si este putin pacat ca problema nu a mers cum trebuie dar din 12 probleme una sa aiba cateva greseli mi se pare complet rezonabil, sa nu uitam ca cei ce au propus runda nu sunt veterani in acest domeniu. Cu alte cuvinte, felicitari pentru runda si tineti-o tot asa!  =D&gt;

Voi priviti din perspectiva unui olimpic care e top 5 din generatia lui. Din 100 de participanti la olimpiada o sa fie stimulati sa participe doar cei foarte buni, restul se vor demoraliza.
Intr-adevar e o ocazie buna sa se pregateasca top 5% dintre studentii din tara, dar pentru ei exista si codeforces, topcoder si probleme date la regionala.
Ma uit pe clasament si vad ca aproape jumatate din echipe au rezolvat 0 probleme. In plus in fiecare an la regionala au fost minim 2 probleme care au fost mai simple decat oricare problema de aici.

Mici critici legate de setul de probleme:
http://www.infoarena.ro/problema/cenzura -> http://www.infoarena.ro/problema/ahocorasick
http://www.infoarena.ro/problema/algoritm -> puteau fi lasate limite de timp mai lejere ca sa intre si bellman ford

Intr-adevar majoritatea  problemelor au fost misto, o sa rezolv cat mai multe dintre ele si ma bucur ca am avut ocazia sa vad idei noi.

Mda, din punctul asta de vedere, ai dreptate. Chiar daca azerah si semipalindrom au fost mai usoare, clasamentul spune ca nu au fost chiar asa usoare. In schimb, mai intervine si faptul ca la regionala nu participa toate echipele care au intrat la ONIS, ci doar cateva din fiecare facultate, si asta schimba multe.
Pe langa asta, avand in vedere ca Romania nu face extraordinar la regionala, cu exceptia echipelor de la UNIBUC care reusesc in mod constant sa se califice la finala, o crestere de nivel pt celelalte echipe e bine venita.
Faza cu demoralizarea e o problema ce tine de fiecare in parte, pe unii ii ambitioneaza sa lucreze si sa ajunga mai buni, iar pe altii ii face sa renunte.

Cred ca erau o multime de participanti care stiau Aho, si totusi nu au putut rezolva problema :) Asta inseamna ca mai trebuia ceva pe langa Aho.

@Petru:

Intr-adevar problemset-ul a fost dificil. Ne-am luat dupa modelul diferitelor concursurilor de tip regionala ACM, cum sunt cele de pe Codeforces Gym unde chiar si cea mai usoara problema are o chichita si nu prea vezi probleme de genul "numarati cate aparitii are litera A in urmatorul sir" desi aici poate ar fi fost necesar. Cred ca participantii pot sa zica acum ca stiu cu ce se mananca un concurs de tip regionala ACM si credem ca sunt destule de invatat din acest problemset. In lumina feedback-ului primit insa, nivelul de dificultate probabil va scadea pentru urmatoarea runda.

Articolul cu solutii va fi publicat in cursul zilei de Duminica.

Problema Por Costel si Comisia de Cenzura nu implica numai Aho-Corasick ci si programare dinamica. Plus ca trebuie sa intelegi bine Aho ca sa il adaptezi de la a numara aparitii la a scoate efectiv pozitiile aparitiilor.
Legat de limitele de timp, e discutabil. S-a discutat si pe marginea problemei Por Costel si Livada. Pentru unii limitele au fost mai mult decat suficiente dar altii s-au poticnit in ele cu o solutie de complexitate buna. Concluzia este ca si constanta conteaza.

La Por Costel si Algoritmul, in particular, nu inteleg de ce lumea se incapataneaza sa bage Bellman-Ford. E neoptim pe un graf cu muchii pozitive. E O(N*M) si in articolul de solutii voi da si testul pe care CHIAR face O(N*M) cu tot cu coda si parent-checking.

Singura problema pe care o consideram inadmisibila, v-am spus, e Invazia.

@Radu, Stefan si Silviu:

Multumim ! Din pacate, componenta comisiei se va schimba cel mai probabil pentru urmatoarea runda (vrem si noi sa participam). :))

@Denis:

Multumim ! Nu ne consideram veterani :))

Avand in vedere ca Algoritmiada ne-a cam dat reject prin faptul ca se califica doar 5 studenti, ar trebui sa nu scada dificultatea prea mult la rundele urmatoare, pentru a mentine concursul la un nivel mai inalt. Daca tot e singurul concurs special pentru studenti, macar sa fie ca lumea :D

Testele la problema invazia au fost refacute astfel incat doar solutia buna sa ia 100 de puncte (asa cum am fi dorit noi initial sa fie departajate solutiile).  De asemenea N-ul a fost ridicat la 3*10^5.

Articolul cu solutii este gata !! http://www.infoarena.ro/onis-2015/solutii-runda-1 Lectura placuta !

Anul trecut la Algoritmiada la categoria Open (Studenti) au venit la finala doar 4 sau 5 oameni. Acesta a fost principalul motiv pentru care am scazut numarul de locuri pentru studenti. Desigur, asta nu inseamna ca Algoritmiada a dat reject, inseamna ca trebuie sa va ambitionati mai mult avand o provocare mai mare. :)

@Petru: Sunt de acord ca problemele trebuie sa fie accesibile pentru cat mai multi, dar sa nu facem confuzia intre o problema de implementare si una de idee. Ambele pot fi accesibile atata timp cat sunt alese cum trebuie. Diferenta e ca trebuie sa ne concentram mai mult pe idei decat pe implementare. Sunt peste 1500 de probleme pe acest site, sunt suficiente probleme din care poti sa lucrezi, sa castigi experienta si sa devii mai bun. Scopul concursurilor remane sa exploateze cat mai multe idei noi :) . Nivelul nu cred ca a fost atat ridicat. Nu ne-am apropiat inca de o regionala de ACM. Oricum, a fost o runda reusita. Multumim baietilor pentru tot efortul depus.

daca la rundele urmatoare o sa fie mai usoare problemele nu o sa mai fie deloc amuzant concursul, nu o sa mai aiba miza

Runda 2 este sambata?  :D