h1. 'Soluţia':warm-up-2019/solutii/shoturi problemei 'Shoturi':problema/shoturi

Solutia este prezentata de unul din concurenti, ==user(user="verde.cristian2005" type="normal")==
 

h2. $Soluţie backtracking - 10 puncte$

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

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

h2. $Soluţie N*K^2^ - 50 de puncte$

h2. $Soluţie N*K^2^ - 50 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

* $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: <tex>\displaystyle \ dp[i][j]=\sum_{x=0}^{j-1} dp[i-1][x]*(j-x)*hazard[i] + dp[i-1][j]</tex>

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 <tex>(j-x)*hazard[i]</tex>. Adunăm $dp[i-1][j]$ la $dp[i][j]$ deoarece tinerii pot alege să nu bea niciun shot **din cazanul** $i$.

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 <tex>(j-x)*hazard[i]</tex>. Adunăm $dp[i-1][j]$ la dp[i][j] deoarece tinerii pot alege sa nu bea niciun shot de tipul i.

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

    }
==

Obs: MOD=269 696 969 {**Nice**}
 
h2. $Solutie N*K, memorie N*K - 80 de puncte$

h2. $Solutie N*K, memorie N*K - 80 puncte$

Trecerea de la $O(N*K^2^)$ 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$ = <tex> \displaystyle \ \sum_{x=0}^{j-1} dp[i-1][x]</tex> pe care o updatăm adăugând <tex>dp[i-1][j]</tex> şi o variabila $suma_de_suma$ pe care o updatăm cu $suma$, acestea vor arata aşa:
 
|_. j|_. suma|_. suma_de_suma|
|1|@1*dp[i-1][0]@
@1*dp[i-1][j-1]@|@1*dp[i-1][0]@
@1*dp[i-1][j-1]@|
|2|@1*dp[i-1][0]+1*dp[i-1][1]@
@1*dp[i-1][j-2]+1*dp[i-1][j-1]@|@2*dp[i-1][0]+1*dp[i-1][1]@
@2*dp[i-1][j-2]+1*dp[i-1][j-1]@|
|3|@1*dp[i-1][0]+1*dp[i-1][1]+1*dp[i-1][2]@
@1*dp[i-1][j-3]+1*dp[i-1][j-2]+1*dp[i-1][j-1]@|@3*dp[i-1][0]+2*dp[i-1][1]+1*dp[i-1][2]@
@3*dp[i-1][j-3]+2*dp[i-1][j-2]+1*dp[i-1][j-1]@|
 
Se observă că, inmulţind $suma_de_suma$ cu <tex>hazard[i]</tex>, obţinem rezlultatul pentru $dp[i][j]$.
Cum $suma$ şi $suma_de_suma$ sunt calculate in timpul parcurgerii cu $j$, complexitatea este <tex>O(N*K)</tex>
 
**Cod c++**
==code(cpp)|
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;
        }
    }
==
 
h2. $Soluţie N*K, memorie N - 100 de puncte$
 
Deoarece pentru a calcula <tex>dp[i][ceva]</tex> avem nevoie doar de <tex>dp[i-1][altceva]</tex>, 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, <tex>dp[j]</tex> va fi fostul <tex>dp[i][j]</tex>, iar <tex>aux[j]</tex> va fi fostul <tex>dp[i-1][j]</tex>. De aceea, memoria folosită este <tex>N</tex> în loc de <tex>N*K</tex>.
 
**Cod c++**
==code(cpp)|
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;
        }
    }
==

Observăm că, dacă atunci când parcurgem cu $j$-ul ţinem o variabilă $suma$ = <tex> \displaystyle \ \sum_{x=0}^{j-1} dp[i-1][x]</tex> pe care o updatăm adaugând <tex>dp[i-1][j]</tex> si o variabila $suma_de_suma$ pe care o updatăm cu $s$, acestea vor arata aşa:

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

*$j=1 => suma = <tex>dp[i-1][0]</tex> = 1 şi suma_de_suma = <tex>dp[i-1][0]</tex> = 1$, care devin după update $suma = <tex>dp[i-1][0]+dp[i-1][j]</tex>$, respectiv $suma_de_suma=<tex>2*dp[i-1][0]+dp[i-1][1]</tex>$
*$j=2 => suma = <tex>dp[i-1][0] + dp[i-1][1]</tex> şi suma_de_suma = <tex>2*dp[i-1][0] + dp[i-1][1]</tex>$, care devin după update $suma =<tex> dp[i-1][0] + dp[i-1][1]</tex>$, respectiv $suma_de_suma=2*dp[i-1][0]+dp[i-1][1]$

protected

public