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

Pentru început, observăm că $C(n,i)·i^k^$ înseamnă de fapt să alegem un subşir de lungime $i$ a mulţimii ${1,2,3,...,n}$, şi după aceea să alegem o tuplă de lungime $k$ din subşirul respectiv. În acest fel, numărăm toate perechile de tipul $(subşir, tuplă)$, dar acest lucru este echivalent cu a număra perechi de tipul $(tuplă, subşir)$. Observăm în continuare că pentru a alege un subşir care acoperă o tuplă de valori depinde doar de numărul de valori distincte $x$ din tuplă, iar numărul de moduri să alegem subşirul este $2^n-x^$. Astfel, dacă vom găsi un mod prin care să calculăm numărul de tuple cu $x$ valori distincte, am rezolvat problema.

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.

h2. Subtask 6: k ≤ 500

Putem folosi următoarea dinamică pentru a număra tuple: $dp[i][j] = numărul de tuple de lungime i care conţin toate valorile din [1,j]$. Ca recurenţă, să spunem că tupla noastră conţine $k > 1$ valori egale cu $j$, atunci $dp[i][j] += dp[i-k][j-1]·C(i,k)$.

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 în $O(k^3^)$.

Prin urmare, am rezolvat acest subtask in $O(k^3^)$.

O implementare bazată pe această idee poate fi văzută "aici":https://www.infoarena.ro/job_detail/3147762?action=view-source.

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

Observăm că dinamica de mai sus numără funcţii surjective definite pe ${1,2,3,...,k}$ cu valori în ${1,2,3,...,j}$. Numărarea acestor funcţii este un lucru cunoscut, o putem face prin diverse metode, soluţia oficială se foloseşte de "numere Stirling de speta a 2-a":https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind, cu o complexitate finală de $O(maxk^2^ + t·k)$.

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 bazată pe această idee poate fi văzută "aici":https://www.infoarena.ro/job_detail/3147763?action=view-source.

O implementare bazata pe aceasta idee poate fi vazuta "aici":https://www.infoarena.ro/job_detail/3147763?action=view-source.