h1(#pwca). 'Solutia':jc2021/solutii/pwca problemei 'PWCA':problema/pwca
 

Mai întâi trebuie să facem câteva observaţii legate de transformare:
h4. Observaţia 1:

Aşadar, în cazul al doilea ne-am dat seama că fie tot ce este la stânga de $S$, fie tot ce este la dreapta se va transforma în $1$. Acum vom construi o soluţie folosind programare dinamică:

* $cntAll[len][k][lval][rval] =$ numărul de şiruri de lungime $len$, cu secvenţa maximă de lungime $k$, cu primul element $lval$ şi ultimul element $rval$ ($lval$ şi $rval$ sunt valori binare).
* $cntFull[len][k][lval][rval] =$ numărul de şiruri de lungime $len$, cu secvenţa maximă de lungime $k$, cu primul element $lval$ şi ultimul element $rval$ ($lval$ şi $rval$ sunt valori binare) care se pot transforma într-un şir plin de $1$.
* $cntAllPref[len][k][lval][rval] =$ numărul de şiruri de lungime $len$, cu secvenţa maximă de lungime +maxim+ $k$, cu primul element $lval$ şi ultimul element $rval$ ($lval$ şi $rval$ sunt valori binare).
* $cntFullPref[len][k][lval][rval] =$ numărul de şiruri de lungime $len$, cu secvenţa maximă de lungime +maxim+ $k$, cu primul element $lval$ şi ultimul element $rval$ ($lval$ şi $rval$ sunt valori binare) care se pot transforma într-un şir plin de $1$.

* $cntAll[len][k][lval][rval] =$ numărul de şiruri de lungime $len$, cu secvenţa maximă de lungime $k$, cu primul element {$lval$} şi ultimul element {$rval$} ({$lval$} şi {$rval$} sunt valori binare).
* $cntFull[len][k][lval][rval] =$ numărul de şiruri de lungime $len$, cu secvenţa maximă de lungime $k$, cu primul element {$lval$} şi ultimul element {$rval$} ({$lval$} şi {$rval$} sunt valori binare) care se pot transforma într-un şir plin de $1$.
* $cntAllPref[len][k][lval][rval] =$ numărul de şiruri de lungime $len$, cu secvenţa maximă de lungime +maxim+ $k$, cu primul element {$lval$} şi ultimul element {$rval$} ({$lval$} şi {$rval$} sunt valori binare).
* $cntFullPref[len][k][lval][rval] =$ numărul de şiruri de lungime $len$, cu secvenţa maximă de lungime +maxim+ $k$, cu primul element {$lval$} şi ultimul element {$rval$} ({$lval$} şi {$rval$} sunt valori binare) care se pot transforma într-un şir plin de $1$.

$cntAllPref$ şi $cntFullPref$ sunt uşor de calculat fiind doar sume pe prefixe (ale parametrului $k$) pentru dinamicile principale ($cntAll$ şi $cntFull$).

$cntAllPref$ şi $cntFullPref$ sunt uşor de calculat fiind doar sume pe prefixe (ale parametrului $k$) pentru dinamicile principale ({$cntAll$} şi {$cntFull$}).

Pentru recurenţe va trebui să fixăm poziţia secvenţei maximale (de lungime $k$). Pentru fiecare poziţie de început $pos$ avem următoarea recurenţă (vom folosi notaţiile $lLen = pos - 1$ şi $rLen = len - (pos+k-1)$):

h2. Subtask 4 (40 de puncte)

Pentru acest subtask se va folosi soluţia anterioară pentru a precalcula răspunsul pentru toate lungimile $l$ de la $1$ la $VMAX$ (asemănător cu subtask-ul 2). Complexitate timp $O(VMAX^3^)$.

Pentru acest subtask se va folosi soluţia anterioară pentru a precalcula răspunsul pentru toate lungimile $l$ de la $1$ la $VMAX$ (asemănător cu subtask-ul 2). Complexitate timp $O(VMAX^3^)$.
 
Soluţia de 100 de puncte se găseşte "aici":job_detail/2758428?action=view-source.

public

protected