Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2019-10-14 15:19:50.
Revizia anterioară   Revizia următoare  

Soluţia problemei Shoturi

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*K2 - 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.

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 sa nu bea niciun shot de tipul 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;
        }
    }

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

Trecerea de la O(N*K2) 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 adaugând dp[i-1][j] si o variabila suma_de_suma pe care o updatăm cu s, acestea vor arata aşa:

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