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

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

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

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

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 sa 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 să nu bea niciun shot **din cazanul** $i$.

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

    }
==

Obs: MOD=269696969 {**Nice**}

Obs: MOD=269 696 969 {**Nice**}

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

h2. $Solutie N*K, memorie N*K - 80 de 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:

    }
==

h2. $Soluţie N*K, memorie N - 100 puncte$

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

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)|

    }
==

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>
 
Observaţie total nenecesară(credit ==user(user="lucaperju" type = "tiny")==): Deşi sunt oameni foarte respectabili in comisie, un ,,Mlc'' cinstit primeşte respect din partea concurenţilor

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>

public

protected