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_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}

Subtask 1

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

Time Complexity: \mathcal O(NT)

Subtask 2

For the remaining 80% of points, we note the transformation is linear, we 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\times T 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


  • 3
    lemondeath  commented on Nov. 7, 2020, 11:10 p.m.

    I think I found an error: the matrix should actually be size (T+1) by (T+1) to represent each of the T months that a crab is a baby PLUS the one final state in which it is an adult. This was how I implemented my solution.


    • 2
      richardzhang  commented on Nov. 8, 2020, 1:17 p.m.

      Thank you, it has been fixed.