Problema sir – OJI 2017, Clasa a 10-a

Enunțul problemei sir, de clasa a 10-a, dată în 2017 la OJI, se găsește pe InfoArena și PbInfo.

Rezumat

Considerăm șirurile de lungime $n$, care încep cu $1$, cu proprietatea că fiecare element este mai mare decât predecesorul lui cu cel mult $1$. Să se determine numărul de șiruri ce se termină în $u$, și respectiv numărul de șiruri în care un element apare de cel mult $r$ ori.

Soluție

Răspunsul pentru prima cerință este $C_{n - 1}^{u - 1}$, iar explicația este exact cea de la numărul de partiții ordonate ale unui număr natural, din acest articol. Șirul nostru este partiționat în $u$ secvențe, iar noi trebuie să alegem capetele acestora. Cum ultima secvență are capătul fixat în poziția $n$, rămâne să alegem capetele doar pentru primele $u - 1$ secvențe. Acestea trebuie să ia valori distincte din mulțimea $\{1, 2, \ldots, n - 1\}$, așa că numărul lor este $C_{n - 1}^{u - 1}$. Având nevoie de o singură combinare, o vom calcula folosind invers modular, pe baza formulei:

$$C_{n - 1}^{u - 1} = (n - 1)! \cdot (u - 1)!^{-1} \cdot (n - u)!^{-1}$$

La a doua cerință vom folosi programare dinamică astfel: Notăm cu $\mathrm{dp}[i]$ numărul de șiruri de lungime $i$ cu proprietatea dată. Putem obține un șir de lungime $i$ adăugând $j$ valori egale la un șir de lungime $i - j$, unde $1 \le j \le r$. Valorile adăugate sunt unic determinate de ultimul element al șirului de lungime $i - j$. Adică, dacă acesta se termină în $x$, atunci șirul nou se va termina în $j$ de $x + 1$. Deci, recurența este:

$$\mathrm{dp}[i] = \mathrm{dp}[i - 1] + \mathrm{dp}[i - 2] + \cdots + \mathrm{dp}[i - r]$$

Dinamica poate fi calculată imediat în $O(n \cdot r)$, însă poate fi optimizată foarte ușor făcând următoarea observație. Scriem una sub alta recurențele pentru $\mathrm{dp}[i]$ și $\mathrm{dp}[i - 1]$:

$$\begin{align}
\mathrm{dp}[i] & = \mathrm{dp}[i - 1] + \mathrm{dp}[i - 2] + \cdots + \mathrm{dp}[i - r]\\
\mathrm{dp}[i - 1] & = \mathrm{dp}[i - 2] + \mathrm{dp}[i - 3] + \cdots + \mathrm{dp}[i - r - 1]
\end{align}$$

Dacă scădem cele două relații, se vor reduce o grămadă de termeni și vom obține:

$$\mathrm{dp}[i] - \mathrm{dp}[i - 1] = \mathrm{dp}[i - 1] - \mathrm{dp}[i - r - 1]$$

De unde:

$$\mathrm{dp}[i] = 2 \cdot \mathrm{dp}[i - 1] - \mathrm{dp}[i - r - 1]$$

Evident, complexitatea pentru calcularea noii recurențe este $O(n)$.

Sursă C++

Dacă ai vreo nedumerire cu privire la problema sir, lasă un comentariu și te voi ajuta 🙂