(toc)*{text-align:left} *Lista de probleme*
* 'Omida Mincinoasa':problema/omidamincinoasa
* 'Salutare Jupâne':problema/jupanul
* 'Permdist':problema/permdist

h1. Solutia problemei 'Omida Mincinoasa':problema/omidamincinoasa

==include(page="jc2023/solutii/omidamincinoasa")==

Pentru inceput, observam ca $C(n,i)·i^k^$ inseamna de fapt sa alegem un subsir de lungime $i$ a multimii ${1,2,3,...,n}$, si dupa aceea sa alegem o tupla de lungime $k$ din subsirul respectiv. In acest fel, numaram toate perechile de tipul $(subsir,tupla)$, dar acest lucru este echivalent cu a numara perechi de tipul $(tupla, subsir)$. Observam in continuare ca pentru a alege un subsir care acopera o tupla de valori depinde doar de numarul de valori distincte $x$ din tupla, iar numarul de moduri sa alegem subsirul este $2^n-x^$. Astfel daca vom gasi un mod prin care sa calculam numarul de tuple cu $x$ valori distincte, am rezolvat problema.

==include(page="jc2023/solutii/jupanul")==

h2. Subtask 6: k ≤ 500

==include(page="jc2023/solutii/permdist")==

Putem folosi urmatoarea dinamica pentru a numara tuple: $dp[i][j] = numarul de tuple de lungime i care contin toate valorile din [1,j]$. Ca recurenta, sa spunem ca tupla noastra contine $k > 1$ valori egale cu $j$, atunci $dp[i][j] += dp[i-k][j-1]·C(i,k)$.
 
Prin urmare, am rezolvat acest subtask in $O(k^3^)$.
 
O implementare bazata pe aceasta idee poate fi vazuta "aici":https://www.infoarena.ro/job_detail/3147762?action=view-source.
 
h2. Subtask 7: k ≤ 5000
 
Observam ca dinamica de mai sus numara functii surjective definite pe ${1,2,3,...,k}$ cu valori in ${1,2,3,...,j}$. Numararea acestor functii este un lucru cunoscut, o putem face prin diverse metode, solutia oficiala se foloseste de "numere Stirling de speta a 2-a":https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind, cu o complexitate finala de $O(maxk^2^ + t·k)$.
 
O implementare bazata pe aceasta idee poate fi vazuta "aici":https://www.infoarena.ro/job_detail/3147763?action=view-source.