Sigur e ok problema asta? E vre-un cuvant ascuns in enunt? nu inteleg de ce as putea lua WA pe ea.
Edit NVM.

"Tassadar are o mulţime de numere scrise în baza 2", sigur o multime, nu 2?

@AlexValeanu: Graful la Fenrir era un graf bipartit complet, cu 11 noduri in stanga si 9 noduri in dreapta.





(am albit textul ca sa nu fie spoiler pentru cei care vor sa se prinda singuri)

El se referea la probleme precum prima de azi, unde nu stiai nici macar daca ti-a compilat.

@Dani si @George: Nu facusem pe foaie, mi se parea ca dinamica aia ia destul de mult, dar, pana si matematic, mai mult de 4 secunde nu ia, ceea ce e ok.

Runda de azi mi-a placut. Problema Fenrir a fost pe atat de diferita si pe atat de interesanta de rezolvat cum multe probleme din ziua de azi nu sunt (gg Mihai, in plus, enuntul e bazat). Problema  Perioada01 se putea face si cu un Z (asa am implementat eu) in O(p). Problema disconnect are un enunt foarte dragut si imi place cu atat mai mult cu cat am inteles acum rezolvarea fara liniarizare (in concurs am implementat LCA si liniarizare cu AIB). Am fost cu 1min in urma sa trimit un O(N*M) corect la spectacole, presupun ca pentru 100  aveti o dinamica cu AIB pentru maxim (sau cu o structura de date ceva) in complexitate O(MlogN). Per ansamblu, keep up the good work. 

P.S. Am si eu o curiozitate: voi cum verificati in evaluator la Fenrir ca graful nostru sa nu aiba lant hamilton fara sa bagati ceva foarte costisitor ca timp?

Ai grija la urmatoarea restrictie din enunt:

ATENTIE! 1 ≤ N < 10¹⁰⁰. Numerele trebuie citite ca siruri de caractere!

Greseala mea cand am scris solutia la problema Suma5. Am corectat, sper ca acum e bine.

Felicitari pentru runda , problemele de azi chiar mi-au placut. Problema 4 intr-adevar era putin mai greu de implementat, dar clasica. Setul de probleme a avut o problema usoara (dar originala), deci oricine putea termina concursul cu cel putin o problema. Problema 3 a fost putin cam tehnica, dar nu mi-a displacut. In schimb, cea mai smen problema mi s-a parut Problema cu Becuri, felicitari Radu Voroneanu , foarte originala, cu idee destul de bine ascunsa si solutie elementara (chiar daca trebuia data o atentie sporita unor cazuri particulare in constructia solutiei). Keep up the good work!  

Mie mi-a intrat cu streamuri si string. Odd? As vrea un admin sa clarifice lucrurile - daca limita de timp este foarte stransa, si daca se recomanda o citire anume. Multumesc (nu vreau sa vad ca am 0 pe ea dupa concurs dintr-o cauza de genul asta). 

Ma scuzati, testele sunt grupate astfel incat o solutie nu groaznic de lenta, dar nu optima sa ia 0?  
LE. : Oricum, nu mai conteaza. 

Intra si fara parsare?

Deci altfel spus, tranzitiile calatorilor se fac FIX in paralel? (gen 2 calatori cu momentele A B si C D E: tranzitiile sunt de la A la B in timp cu de la C D)

Calatorii in timp calatoresc in paralel?
Gen daca avem 2 calatori care traiesc in anii (2,3) respectiv (4,5), atunci cand primul se afla in anul 2, al doilea in 4 si cand primul in 3, al doilea in 5. Adica cum calatoresc ei, unul dupa altul, sau in paralel?

Inductie dupa lungimea sirului nostru, N:

Cazul de baza: N=1 => Evident, algoritmul nostru e corect aici.

Cazul general: Presupunem ca am demonstrat afirmatia noastra pentru toti 1 <= k < N si acum vrem sa demonstram afirmatia noastra pentru N. In primul rand, daca nu am folosi maximul din vector, nu am avea cum sa ucidem toate testoasele (cum elementele vectorului sunt unice rezulta ca numai maximul se poate elimina pe el insusi). Apoi, daca nu am folosi maximul chiar la inceput, aratam ca am irosit mutari (deci solutia noastra nu este in general optima). Mai exact, presupunem ca maximul e pe pozitia X. Numim stanga lui X intervalul [1,X-1] si dreapta lui X intervalul [X+1,N] (cazurile cand unul din aceste intervale este vid se trateaza analog). Daca nu am folosi maximul chiar la inceput, am face cateva miscari strict in stanga lui X si cateva strict in dreapta lui X (independente fiindca X este maxim), dupa care am folosi maximul in una din directii. Maximul va elimina cu siguranta tot ce exista in aceea directie, deci mutarile facute acolo au fost inutile, iar cele facute in cealalta directie puteau fara a schimba raspunsul sa fie facute si dupa eliminarea maximului. Astfel, am demonstrat ca la pasul curent vom alege mai intai maximul. Dupa alegerea maximului, vectorul nostru se micsoreaza, si cum stim ca am demonstrat afirmatia pentru 1 <= k < N, rezulta ca in continuare vom alegem numai maxime, indiferent cum am orienta primul maxim ales.

Am incercat sa o fac cat de riguros am putut. Oricum, mare parte a demonstratiei e intuitie.  

Edit: Practic am folosit reducerea la absurd, fara insa a folosi formularile clasice.

Nu exista eps (gen precizie)?

La prima problema formula chiar era Suma^n.
Iata de ce:
Sa zicem ca avem cele n cutii: x1 x2 ... xn
Acum incercam sa enumeram toate produsele necesare: (fie a1 ... am cele m numere distincte)
a1 * a1 * ... * a1 (de n ori)
a1 * a1 * ... * a2 (de n ori)
...
a1 * a1 * ... * a2 * a1 (de n ori)

Altfel scris (notam cu S(i,a,b) sigma dupa i ia valori de la a la b):
S(i,1,m) S(j,1,m) S(k,1,m) * ... * S(p,1,m) [ai*aj*ak* ... * ap] (n sigme)
Si cum sigma produsului e produs de sigme, ajungem la formula (Suma totala)^n

Pot sa detaliez daca e cineva interesat.

Felicitari pentru runda, foarte reusita .  Problema 1 era cum trebuie sa fie prima - simpla si "ok", sa nu fie plina de cazuri particulare. A doua a fost parca prea mult mate (trebuia sa stii putin despre teorema lui Bezout + Euclid extins + ecuatii pell ca sa o faci, poate m-am complicat, dar oricum demonstratia solutiei e destul de matematica). Rog sa puneti problemele in arhiva cat de curand (vreau sa vad daca CE-ul din ultima secunda la problema 2 era de 100). A treia a fost cam "scarboasa" adica ideea iti venea imediat dar trebuia sa fii foarte dibace sa nu gresesti nimic. Ultima ma duce cu gandul la FFT (nu m-am gandit mult prea mult la ea). Felicitari autorilor + tuturor celor care au participat la crearea si desfasurarea rundei.

P.S. : "Rating is a lie." (ca raspuns la cea a zis Narcis mai sus, mi-a luat ceva sa ma prind dar a meritat ).

Mult succes!

Da, de acord, caci daca acum dati permisiuni sa vedem subiectele pierdem cateva puncte (pentru aceste 5 minute).

Nu se vad problemele. 

Felicitari! Va tinem cu totii pumnii si in ziua 2. 

Mult succes! 

Nu la asta ma refeream. Eu voiam doar sa subliniez faptul ca nu toate solutiile care au luat 70 sunt bulaneli, unele sunt doar putin mai incete din cauza constantei.

Nu chiar toate solutiile de 70p sunt bulaneli. Unele sunt doar mai proaste din punctul de vedere al constantei (hash-uri).

Citez din pagina cu intrebari destinata problemei "potriveala" (http://www.infoarena.ro/forum/index.php?topic=9987.0) intrebarea:

Se garanteaza ca al doilea sir din input este cea mai mica perioada a sirului B, nu una oarecare?

si raspunsul:

NU