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 be the number of baby crabs that are i months old, and let a_T be the number of crabs that are adults. The transition from month k to month k+1 is given by

\displaystyle \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ \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}

Subtask 1

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

Time Compelexity: \mathcal O(NT)

Subtask 2

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

\displaystyle A = \begin{bmatrix} 0 & 0 & \cdots & 0 & 0 & K \\ & & & & & 0 \\ & & & & & 0 \\ & & I & & & \vdots \\ & & & & & 0 \\ & & & & & 1 \end{bmatrix} where I is the (T-1)\times(T-1) identity matrix.

Then we can obtain the answer with \displaystyle A^{(N-1)}\begin{bmatrix} 0 \\ \vdots \\ 0 \\ C \end{bmatrix}

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

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


Comments

There are no comments at the moment.