Revizia anterioară Revizia următoare
Solutia problemei Omida Mincinoasa
Pentru început, observăm că C(n,i)·ik î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 2n-x. Astfel, dacă vom găsi un mod prin care să calculăm numărul de tuple cu x valori distincte, am rezolvat problema.
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).
Prin urmare, am rezolvat acest subtask în O(k3).
O implementare bazată pe această idee poate fi văzută aici.
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, cu o complexitate finală de O(maxk2 + t·k).
O implementare bazată pe această idee poate fi văzută aici.
