Solutii Autumn WarmUp 2019

Lista de probleme
Sec
Rogvaiv
Shoturi

Problema Sec

Nu exista inca...

Solutia Problemei Rogvaiv

Solutia este prezentata de unul din concurenti,

Mihai-Cristian Popescu
•mihai50000

Solutia 1

Vom rezolva problema prin metoda programării dinamice.

Fie $d[i][j][k]$ numărul de şiruri de lungime $i$ care au pe ultima poziţie al $j$ -lea caracter şi care conţin deja sau nu şirul $ROGVAIV$ sau $VIAVGOR$ în funcţie de cerinţă.

$i = 1..n$
$j = 1..7$ (considerăm primul </tex>V</tex> diferit de al doilea $V$ )
$k = 0 / 1$ ( $0 = false$ , $1 = true$ )

Pentru cerinţa 1.

Observăm că putem să punem pe ultima poziţie orice caracter din primele 6 fără a forma $ROGVAIV$ .
Deci $d[i][j][k]$ = $d[i - 1][j][k]$ ( $i = 1...n$ , $j = 1...6$ , $k = 0 / 1$ )

Pentru $j = 7$ pot să formez şirul $ROGVAIV$ .

$d[i][7][1] =$ $\sum_{t=1}^7$ $d[i - 1][t][1] + d[i - 6][1][0]$ .
$\sum_{t=1}^7$ $d[i - 1][t][1]$ reprezintă toate şirurile care conţin deja şirul $ROGVAIV$ , iar $d[i - 6][1][0]$ reprezintă numărul de subşiruri care au caracterul $R$ pe prima poziţie şi nu conţin deja şirul dat. Deci pe poziţiile rămase voi completa cu caracterele necesare pentru a forma $ROGVAIV$ .

$d[i][7][0]$ = $\sum_{t=1}^7$ $d[i - 1][t][0] - d[i - 6][1][0]$ (scad cazurile în care se formează $ROGVAIV$ ).

Pentru cerinţa 2.

Recurenţa este asemănătoare.

De data aceasta doar caracterele cu indicii $2, 3, 4, 5, 6$ nu pot forma $ROGVAIV$ sau $VIAVGOR$ .
Deci $d[i][j][k] = d[i - 1][j][k]$ ( $i = 1..n$ , $j = 2..6$ , $k = 0 / 1$ )

Cazul $j = 7$ este identic cu cel de la cerinţa 1.

Pentru $j = 1$ recurenţa devine:

$d[i][1][1] =$ $\sum_{t=1}^7$ $d[i - 1][t][1] + d[i - 6][7][0]$
$d[i][1][0] =$ $\sum_{t=1}^7$ $d[i - 1][t][0] - d[i - 6][7][0]$

Rezultatul şi complexitatea.

Rezultatul este $\sum_{i=1}^7$ $dp[n][i][1]$ .

Complexitatea este $O(n*alpha)$ .

Solutia 2.

Considerăm următoarele stări:

Starea 1 = $''$ (nu conţine niciun caracter)
Starea 2 = $R$
Starea 3 = $RO$
.
.
Starea 7 = $ROGVAI$

Astfel putem să ne folosim de dinamica $d[i][j][k]$ = numărul de şiruri de lungime $i$ care se află în starea $j$ şi care conţin deja sau nu unul din şirurile date.

$i = 1..n$
$j = 1..7$
$k = 0..1$

Pentru cerinţa 1.

La adăugarea unui caracter nou observăm că ori transformă starea $i$ în starea $i + 1$ ori îl aduce la starea 1. Când se formeaza $ROGVAIV$ $k$ devine 1 şi starea devine 0 ( $j = 0$ ).

Pentru cerinta 2.

Adăugăm încă 7 stări care corespund şirului inversat ( $VIAVGOR$ ), iar recurenţa este la fel.

Starea 8: $''$
Starea 9: $V$
Starea 10: $VI$
.
.
Starea 14: $VIAVGO$

Răspunsul şi complexitatea.

Răspunsul este $\sum_{i=1}^7$ $d[n][i][1]$ .

Complexitatea este $O(n * alpha)$

O optimizare care nu era necesară pentru a obţine punctaj maxim.

Menţionez că soluţia a doua poate fi îmbunătăţită.
Dacă liniarizăm dinamica putem să formăm o matrice care ridicată la puterea $n$ conţine valorile din care este format rezultatul.
Astfel complexitatea devine $log_{2}(n) * alpha ^ 3$ .

Soluţia problemei Shoturi

Solutia este prezentata de unul din concurenti,

Verde Flaviu-Cristian
•verde.cristian2005

`Soluţie backtracking - 10 puncte`

Generăm toate variantele posibile ale vectorului $x$ pentru care $x[1] + x[2] + ... + x[N] = K$ . Această soluţie obţine 0 sau 10 puncte în funcţie de implementarea backtrackingului, care ar avea complexitatea $O(K^N)$ amortizat

`Soluţie N*K² - 50 de puncte`

Această soluţie presupune tehnica programării dinamice. Vom folosi matricea dp[n][k], pentru care:

dp[i][j] = suma potenţelor tuturor amestecurilor posibile ingerând j ~~shoturi~~ păhărele din primele i ~~substanţe interzise~~ sucuri

De aici deducem recurenţa: $\displaystyle \ dp[i][j]=\sum_{x=0}^{j-1} dp[i-1][x]*(j-x)*hazard[i] + dp[i-1][j]$

De ce? Pentru că, din cum am definit dinamica, dp[i-1][x] = suma potenţelor tuturor amestecurilor posibile ingerând x păhărele din primele i-1 sucuri. Cum dp[i][j] presupune ingerarea a j pahare => se vor ingera j-x pahare de tipul i, care vor inmulţi fiecare potenţă cu $(j-x)*hazard[i]$ . Adunăm dp[i-1][j] la dp[i][j] deoarece tinerii pot alege să nu bea niciun shot din cazanul i.

Observatie: $dp[i][0]=1$ , $1<=i<=n$ , ca să ne iasă calculele :)

Voi exemplifica explicaţia cu cod în limbajul C++

dp[1][0]=1;
    for(j=1; j<=k; j++)
        dp[1][j]=(1LL*j*hazard[1])%MOD;
    for(i=2; i<=n; i++)
    {
        dp[i][0]=1;
        for(j=1; j<=k; j++)
        {
            for(x=0; x<=j-1; x++)
                dp[i][j]=(dp[i][j]+1LL*dp[i-1][x]*(j-x)*hazard[i])%MOD;
            dp[i][j]=(dp[i][j]+dp[i-1][j])%MOD;
        }
    }

Obs: MOD=269 696 969 Nice

`Solutie NK, memorie NK - 80 de puncte`

Trecerea de la O(N*K²) la O(N*K) se face cu ajutorul sumelor parţiale.
Observăm că, dacă atunci când parcurgem cu j-ul ţinem o variabilă suma = $\displaystyle \ \sum_{x=0}^{j-1} dp[i-1][x]$ pe care o updatăm adăugând $dp[i-1][j]$ şi o variabila suma_de_suma pe care o updatăm cu suma, acestea vor arata aşa:

j	suma	suma_de_suma
1	`1dp[i-1][0]` `1dp[i-1][j-1]`	`1dp[i-1][0]` `1dp[i-1][j-1]`
2	`1dp[i-1][0]+1dp[i-1][1]` `1dp[i-1][j-2]+1dp[i-1][j-1]`	`2dp[i-1][0]+1dp[i-1][1]` `2dp[i-1][j-2]+1dp[i-1][j-1]`
3	`1dp[i-1][0]+1dp[i-1][1]+1dp[i-1][2]` `1dp[i-1][j-3]+1dp[i-1][j-2]+1dp[i-1][j-1]`	`3dp[i-1][0]+2dp[i-1][1]+1dp[i-1][2]` `3dp[i-1][j-3]+2dp[i-1][j-2]+1dp[i-1][j-1]`

Se observă că, inmulţind suma_de_suma cu $hazard[i]$ , obţinem rezlultatul pentru dp[i][j].
Cum suma şi suma_de_suma sunt calculate in timpul parcurgerii cu j, complexitatea este $O(N*K)$

Cod c++

dp[1][0]=1;
    for(i=1; i<=k; i++)
        dp[1][i]=(1LL*i*hazard[1])%MOD;
    for(i=2; i<=n; i++)
    {
        dp[i][0]=1;
        suma=1;
        suma_de_suma=1;
        for(j=1; j<=k; j++)
        {
            dp[i][j]+=(1LL*suma_de_suma*hazard[i]+dp[i-1][j])%MOD;
            suma=(suma+dp[i-1][j])%MOD;
            suma_de_suma=(suma_de_suma+suma)%MOD;
        }
    }

`Soluţie N*K, memorie N - 100 de puncte`

Deoarece pentru a calcula $dp[i][ceva]$ avem nevoie doar de $dp[i-1][altceva]$ , folosim doar 2 linii din matrice, de aceea putem să scăpăm de ea şi să păstrăm doar 2 vectori reprezentând ultimele 2 linii in ordinea parcurgerii. Astfel, $dp[j]$ va fi fostul $dp[i][j]$ , iar $aux[j]$ va fi fostul $dp[i-1][j]$ . De aceea, memoria folosită este $N$ în loc de $N*K$ .

Cod c++

dp[0]=1;
    for(i=1; i<=k; i++)
        dp[i]=(1LL*i*hazard[1])%MOD;
    for(i=2; i<=n; i++)
    {
        for(j=0; j<=k; j++)
            aux[j]=dp[j];
        dp[0]=1;
        suma=1;
        suma_de_suma=1;
        for(j=1; j<=k; j++)
        {
            dp[j]=(1LL*suma_de_suma*hazard[i]+aux[j])%MOD;
            suma=suma+aux[j];
            if(suma>=MOD)
                suma-=MOD;
            suma_de_suma=suma_de_suma+suma;
            if(suma_de_suma>=MOD)
                suma_de_suma-=MOD;
        }
    }

NOTA: Deoarece suma, suma_de_suma şi aux sunt deja $<MOD$ , adunarea lor va fi $<2*MOD$ de aceea este necesar doar să scădem $MOD$ din ele când sunt $>=MOD$ pentru a fi, din nou, $<MOD$

j	suma	suma_de_suma
1	`1dp[i-1][0]` `1dp[i-1][j-1]`	`1dp[i-1][0]` `1dp[i-1][j-1]`
2	`1dp[i-1][0]+1dp[i-1][1]` `1dp[i-1][j-2]+1dp[i-1][j-1]`	`2dp[i-1][0]+1dp[i-1][1]` `2dp[i-1][j-2]+1dp[i-1][j-1]`
3	`1dp[i-1][0]+1dp[i-1][1]+1dp[i-1][2]` `1dp[i-1][j-3]+1dp[i-1][j-2]+1dp[i-1][j-1]`	`3dp[i-1][0]+2dp[i-1][1]+1dp[i-1][2]` `3dp[i-1][j-3]+2dp[i-1][j-2]+1dp[i-1][j-1]`

infoarena informatica de performanta

Solutii Autumn WarmUp 2019

Problema Sec

Solutia Problemei Rogvaiv

Solutia 1

Pentru cerinţa 1.

Pentru cerinţa 2.

Rezultatul şi complexitatea.

Solutia 2.

Pentru cerinţa 1.

Pentru cerinta 2.

Răspunsul şi complexitatea.

O optimizare care nu era necesară pentru a obţine punctaj maxim.

Soluţia problemei Shoturi

Soluţie backtracking - 10 puncte

Soluţie N*K2 - 50 de puncte

Solutie N*K, memorie N*K - 80 de puncte

Soluţie N*K, memorie N - 100 de puncte

`Soluţie backtracking - 10 puncte`

`Soluţie N*K² - 50 de puncte`

`Solutie NK, memorie NK - 80 de puncte`

`Soluţie N*K, memorie N - 100 de puncte`