Editorial for DMOPC '20 Contest 1 P4 - Victor Makes Bank - Olympiads Online Judge

Editorial for DMOPC '20 Contest 1 P4 - Victor Makes Bank

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

Let $a_i$ $a_{i}$ be the number of baby crabs that are $i$ $i$ months old, and let $a_T$ $a_{T}$ be the number of crabs that are adults. The transition from month $k$ $k$ to month $k+1$ $k + 1$ is given by:

$\displaystyle \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{T-1} \\ a_T \end{bmatrix} \mapsto \begin{bmatrix} K a_T \\ a_1 \\ a_2 \\ \vdots \\ a_{T-2} \\ a_{T-1} + a_T \end{bmatrix}$ $[\begin{matrix} a_{0} \\ a_{1} \\ a_{2} \\ ⋮ \\ a_{T - 1} \\ a_{T} \end{matrix}] \mapsto [\begin{matrix} K a_{T} \\ a_{1} \\ a_{2} \\ ⋮ \\ a_{T - 2} \\ a_{T - 1} + a_{T} \end{matrix}]$

Subtask 1

For 20% of points, we can implement this transition directly with two nested for loops.

Time Complexity: $\mathcal O(NT)$ $O (N T)$

Subtask 2

For the remaining 80% of points, we note the transformation is linear, and we can represent it with the matrix $A$ $A$ :

$\displaystyle A = \begin{bmatrix} 0 & 0 & \cdots & 0 & 0 & K \\ & & & & & 0 \\ & & & & & 0 \\ & & I & & & \vdots \\ & & & & & 0 \\ & & & & & 1 \end{bmatrix}$ $A = [\begin{matrix} 0 & 0 & \dots & 0 & 0 & K \\ 0 \\ 0 \\ I & ⋮ \\ 0 \\ 1 \end{matrix}]$

where $I$ $I$ is the $T \times T$ $T \times T$ identity matrix.

Then we can obtain the answer with

$\displaystyle A^{N-1}\begin{bmatrix} 0 \\ \vdots \\ 0 \\ C \end{bmatrix}$ $A^{N - 1} [\begin{matrix} 0 \\ ⋮ \\ 0 \\ C \end{matrix}]$

We can compute $A^{N-1}$ $A^{N - 1}$ quickly using binary exponentiation.

Time Complexity: $\mathcal O(T^3\log N)$ $O (T^{3} \log N)$

Comments

There are no comments at the moment.