In exemplu, de ce nu poti folosi 1-4 si 4-5 ca sa ajungi la 3? Fac parte din alt subarbore.

LE: Am inteles. Nu poti ajunge la ele.

Sunt doua locuri de actualizat.

Deci nu exista testul N=2, M=1, si radacinile cuplate printr-o muchie?

Un storyline care se termina in nodul i se considera bun daca ultimul element al storylineului e si ultimul element al secventei de P prieteni?

Deci feedback-ul la aceasta problema este complet ?

Evaluatorul este blocat de peste o zi iar submisiile de la Blas din timpul concursului sunt trecute ca fiind "in asteptare". Care este explicatia ?

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

@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 )

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

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

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. )

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.

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.

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.

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

No comment.

Aici puteti pune intrebari la problema Por Costel si Invazia Extraterestra de la concursul ONIS 2015 Runda 1.

Aici puteti pune intrebari la problema Por Costel si Cifrul de la concursul ONIS 2015 Runda 1.

Aici puteti pune intrebari la problema Por Costel si Livada de la concursul ONIS 2015 Runda 1.

Aici puteti pune intrebari la problema Por Costel si Comisia de Cenzura de la concursul ONIS 2015 Runda 1.

Aici puteti pune intrebari la problema Por Costel si Meciul de la concursul ONIS 2015 Runda 1.

Aici puteti pune intrebari la problema Por Costel si Bujor de la concursul ONIS 2015 Runda 1.

Aici puteti pune intrebari la problema Por Costel si Perechile de la concursul ONIS 2015 Runda 1.

Aici puteti pune intrebari la problema Por Costel si Algoritmul de la concursul ONIS 2015 Runda 1.

Aici puteti pune intrebari la problema Por Costel si Pinball de la concursul ONIS 2015 Runda 1.