infoarena

Runda s-a incheiat. Clasamentul este public. Asteptam primele voastre impresii! :D

De asemenea, felicitari tuturor participantilor!  :winner1:

Se vor corecta testele la problema Tempest? Se va reevalua?

Go :banana:

Ii felicitam pe rivalii nostri, corul barbatesc din Finteusu Mare. Ati luptat strasnic, viteji cantareti ! Ne vom intalni din nou pe plaiurile de lupta !  

Cupa Berii a avut un enunt oribil. A fost una dintre cele mai usoare probleme, dar a devenit una dintre cele mai grele din cauza enuntului.  :thumbdown:
Nici la Desenand Stele n-ar fi stricat o imagine.

Pentru Corul Barbatesc: Ati uitat sa puneti date de contact :(

O runda frumoasa, cu probleme grele si interesante. GJ :thumbup: comisiei.
La problema tempest testele nu sunt gresite, doar ca enuntul e ambiguu in ceea ce priveste drumul, nezicand nicaieri ca muchiile sunt date in ordine (eu in solutie nu m-am folosit deloc de ordinea muchiilor). Si intr-adevar pacat de Cupa Berii, cu un enunt cel putin ciudat.

Asteptam adaugarea problemelor in arhiva pentru a verifica inca o data corectitudinea testelor la Tempest. Speram ca totusi comisia va verifica corectitudinea acestora si va reevalua daca sunt gresite.  :wink:
 In rest runda a fost entertaining. :)

Enuntul a fost foarte derutant, data viitoare mai bine se scrie matematic ce vrea problema, nu sa se scrie un enunt la care iti dureaza mai mult sa il intelegi decat sa te prinzi de solutie.

In rest problemele au fost foarte interesante.

Va salutam si noi de aici din Finteusu Mare. Asteptam batalia batalia finala dintre cele 2 echipe. Pana atunci, poate o sa facem un moment artistic la ONI, daca ne permit organizatorii...

Deci se pare ca testele nu sunt conform raspunsurilor date de organizatori la intrebarile puse in timpul rundei. http://www.infoarena.ro/job_detail/1408272
 :thumbdown:

@wildcard...
raspunsul meu insemna ca daca drumul este 1 -2 -3-1-2 (1-2) e parcursa de 2 ori...se pastreaza si ordinea in care sunt parcurse...

Legat de cupa berii imi imput ca nu am facut un desen astfel incat cerinta sa fie mai clara. Am modificat cerinta de cateva ori in incercarea de o face cat mai clara pentru ca stiu ca nu era usor de inteles... Intentionat nu am formalizat cerinta.
Exista probleme care sunt greu de inteles si este important sa puneti intrebari legat de ele, nu dureaza mult.
Vreau sa va atrag atentia ca nu au fost intrebari legat de aceasta problema in primele 3 ore!
De asemenea se intampla destul de des in concursuri ca lumea sa nu-si asume riscul sa atace unele probleme daca nu au fost rezolvate de alte echipe, daca va doriti sa fiti o echipa puternica atacati si probleme care nu au fost rezolvate... sau in cazul de fata sa intrebati de ele.

Repet imi imput lipsa unui desen  :readthis: :'(

Va multumim pentru partcipare si mai asteptam feedback constructiv.

Daca am inteles bine, cupa berarilor se traducea astfel:
Cate segmente (a,b) exista cu 0<=a<b<=n astfel incat sa existe un segment dat de primul tip (a,k) cu a<k<=b sau un segment dat de tipul 2 (k,b) cu b>k>=a.

corect, as zice totusi segment de tipul 2 (b,k) ca se dadeau in ordinea asta, dar da asta cerea problema.

La problema Tempest exista teste in care 2 muchii succesive nu pot face parte din drumul DAT: destinatia primei muchii nu se regaseste printre nodurile ce delimiteaza cea de-a doua muchie.
Cred ca reactia corecta ar fi verificarea testelor si, in cazul in care se constata ca acestea sunt gresite, corectarea lor. De asemenea, ar fi indicata si o reevaluare a penalizarlor.

Felicitari pentru secv10, mi-a placut cazul particular si m-am prins foarte greu de el.
Sigur se incadreaza in precizia ceruta solutia la mafia?

Un mic spoiler la Zapezi2:

Incepem prin a numara toate APM-urile grafului complet. O parte din acestea sunt proaste - cele care contin o muchie inzapezita. Iteram cate o muchie inzapezita si numaram APM-urile care contin muchia. Din numarul de APM-uri vom scadea acest numar. Acum, am scazut ceva de mai multe ori - APM-urile care contin exact 2 muchii inzapezite. Adunam deci inapoi toate APM-urile care contin 2 muchii inzapezite. Din nou, ceva este adunat de mai multe ori acum...  Suna a ceva algoritm cunoscut? :)

Pentru a numara APM-urile grafului complet putem folosi teorema lui Cayley. Acum, avem muchii inzapezite pe care suntem fortati sa le luam in APM - evident, nu vor forma niciun ciclu. Aceste muchii formeaza x componente conexe. Trebuie sa adaugam x - 1 muchii pentru a obtine un APM pentru intregul graf. Putem generaliza cumva teorema de mai devreme? :) Sper ca nu am spoilat prea mult...



Solutia oficiala se bazeaza pe aceeasi idee? :)

care era ideea la Nk?

Noi am facut asa: sortam sirul de numere, si calculam pentru fiecare element din sir solve(x, k) = cel mai mic indice din sir, fie el i, pentru care il poti scrie pe x ca produs de k numere din sir de pe pozitii <= i. Raspunsul pentru solve (x, k) este cel mai mic i pentru care solve(x/v[ i ], k-1) < i. Am memoizat rezultatele acestei functii intr-un unordered_map.

Calculam toti divizorii celor N numere, faceam graful muchiilor si dupa niste hashuri faceam dinamica pe divizorii tuturor numerelor
D[div][nr] = cel mai mic factor astfel incat div poate fii scris ca produs a nr numere din sir mai mici egale cu D[div][nr]

Ce caz particular era? Noi parca am facut KMP + dinamica simpla, fara a trata vreun caz particular.

La mafia trebuia pur si simplu calculata acea formula cu combinari (cu break-urile de rigoare), sau era ceva mai destept ca sa intre in precizie/complexitate?

In loc sa calculezi P(X, K) = probabilitatea sa se aleaga X de K ori calculai !P(X) => probabilitatea sa nu se aleaga X deloc din M extrageri.
Aceasta probabilitate este C(S - vx, M) / C(S, M) , unde S = v1 + v2 ... + vn iar C(n, k) = combinari de N luate cate K. Raportul ala se simplifica intr-un produs de vx termeni pe care il calculai si aveai O(vx) pe test.

Urasc sa fiu din nou acela care spune ca lipseste articolul cu solutii, dar chiar ar fine bine sa fie postat in intregime.
Cel putin runda trecuta s-au postat.  :?

Se scriu solutiile, o sa apara maine sper!

@Cristy94 trebuia sa te asiguri ca sufixul tau nu era mai lung decat prefixul. Vezi cat iti da pe
ababab
ab
ababab

Consider ca la dstar ar trebui sa intre si solutiile care folosesc multset.

PS. Ar trebui mutate unele subiecte in Arhiva concursuri deoarece sunt de multa vreme si nu se mai posteaza acolo

Dadea bine , ca am facut cu o coada in care adaugam pozitia de la care poate sa inceapa urmatorul sufix (just for the lolz).
(am facut problema, am intrebat doar pentru ca am crezut ca mai era vre-un alt caz pe care nu l-am tratat dar a mers)

S-au schimbat testele pentru tempest si s-a facut reevaluare? Pentru ca duminica problema ne-a fost acceptata, iar acuma nu mai este ^^