Sir5

[•dushmi]

Aici se pot pune întrebări legate de problema Sir5 de la Runda 11 a concursului Infoarena Monthly 2012.

Timpul alocat întrebărilor este de 1 ora. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.

[•roots]

Sirul va fi dat sub forma unei vector de M

Schimbati si voi "unei" cu "unui" )

[•roots]

intervalele vor fi complet incluse in sir (capetele nu au voie sa depaseasca extremitatile sirului);

Asta inseamna ca nu pot sa am '[' inainte de primul element din sir ?

[•vladii]

Spre exemplu, amplasamentul (pe exemplul din enunt):

[111]0011000

este valid.

(Incepe in sir pe pozitia 1 si se termina pe pozitia 3).

[•geniucos]

Cum se facea problema asta m-am chinuit cu niste porcarii de dinamici 3D dar nu mergea.Puteti sa imi spuneti si mie?
Multumesc anticipat.

[•deneo]

Probabil dinamica cu inmultire de matrici

[•veleandu]

Cred ca poti sa o iei asa ..

Consideri Ca inlantuiesti bitii aia ..

Daca ai 3 3 3 4

o sa iti faci 1110001110000 .. smenul e ca l < 30 ..
Deci poti sa o iei ca fiind 111000[ inca multi de 0 ] 0000111100000[multi de 0]00111111[multi de 1]111100

etc.
Sper ca te-ai prins de idee ..
Daca ai un "sir" de 1 .. il iei ca 1111 ( 30 maxim .. ( L adica ) ) .. MULTI DE 1 .. 111 ( 30 maxim ).

De ce faci asta?
Pentru ca daca ai 001111 ( sa zicem la pasul x ) ca sa treci la pasul x+1 iti scoti tu acolo o dinamica.

Si la dinamica aia iti trebuie doar 30 de pasi din recurenta. Sau L .. sau ceva de genu.

Si cand ai 1111111 ( multi ) ultimi 30 sunt 1 .. si la pasul x+1 .. x+2 .. etc o sa fie aceeasi recurenta.
Si poti scoate acolo dinamica cu inmultiri de matrici, cum a zis Adi..


Daca desfasori tot pe acolo o sa ai cam 100 de caractere + ceva inmultire de matrici care merge repede 
Sper ca ai inteles ^^
Succes in continuare ><

[•lmihai]

Cum se facea problema asta m-am chinuit cu niste porcarii de dinamici 3D dar nu mergea.Puteti sa imi spuneti si mie?
Multumesc anticipat.

Salut,

Nu am rezolvat-o, dar cred ca ar putea ajuta ideile urmatoare:
- daca la un moment-dat numarul de 0-uri consecutive e mai mic decat L, atunci acele 0-uri pot fi considerate tot 1-uri.
- daca la un moment-dat numarul de 0-uri consecutive e >= L, atunci trebuie combinate 'cumva' grupurile  11..1, 0..0, 1..1 (bazandu-ne pe faptul ca 0-urile sunt cel putin L, deci nu exista segment care sa treaca din primul grup de 1-uri pana la celalalt grup de 1-uri), poate folosind ceva de genul N[ i ][ j ] = numarul de pavari in care primul segment incepe de la pozitia -i (minus i), iar ultimul se termina la lungime_sir+j - daca am avea aceste valori pentru cele doua siruri de 1-uri, atunci cred ca s-ar putea calcula aceste valori si pentru sirul cu 0-uri la mijloc. (s.a.m.d., iar la final de tot interesandu-ne solutia cu i=j=0)
Mi-ar placea sa vad idei mai simple.