Editorial for Wesley's Anger Contest 5 Problem 5 - A Squirrel's Life - Olympiads Online Judge

Editorial for Wesley's Anger Contest 5 Problem 5 - A Squirrel's Life

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: Zeyu

Subtask 1

For subtask 1, we can generate all possible sequences starting from $1$ $1$ and ending at $N$ $N$ , and then count the number of valid sequences in linear time.

Time Complexity: The time complexity is $\mathcal{O}(N \cdot N^E)$ $O (N \cdot N^{E})$ . Note that while that may seem unreasonable to fit within the time limit, two of the events in the sequence have already been set.

Subtask 2

For subtask 2, we can tackle this problem using dynamic programming. The state can be modelled using the current node, the length of the current sequence, a boolean marking whether or not event $2$ $2$ has been reached, and another boolean marking whether or not event $3$ $3$ has been reached.

Alternatively, this can be tackled using matrix exponentiation. If we analyze the transition of the dynamic programming solution it shares similarities with raising the adjacency matrix to the power of $E-1$ $E - 1$ . Using the exponentiation by squaring trick we can first build the adjacency matrix with $2^2 \cdot N$ $2^{2} \cdot N$ nodes (the nodes have been encoded with the two booleans to mark whether or not the events of type $2$ $2$ or $3$ $3$ have been visited yet), and then raise it to the power of $E-1$ $E - 1$ .

Time Complexity: For the dynamic programming solution, the time complexity is $\mathcal{O}(N^2 \cdot E)$ $O (N^{2} \cdot E)$ with a large hidden constant. For the matrix exponentiation solution, the time complexity is $\mathcal{O}(N^3 \cdot \log E)$ $O (N^{3} \cdot \log E)$ with a large hidden constant.

Subtask 3

Subtask 3 is an extension of subtask 2. For the dynamic programming solution, one more parameter to describe the number of supplies found is required. For the matrix exponentiation solution, we need to build a graph with $2^2 \cdot N \cdot (K + 1)$ $2^{2} \cdot N \cdot (K + 1)$ nodes to encode the number of acorn supplies found into the graph.

Time Complexity: For the dynamic programming solution, the time complexity is $\mathcal{O}(N^2 \cdot E \cdot K)$ $O (N^{2} \cdot E \cdot K)$ with a large hidden constant. For the matrix exponentiation solution, the time complexity is $\mathcal{O}((N \cdot K + N)^3 \cdot \log E)$ $O ((N \cdot K + N)^{3} \cdot \log E)$ with a large hidden constant.

Subtasks 4 and 5

These subtasks are meant to reward contestants who attempted to optimize their solution from subtask 3. The following subtasks' main objective is to reduce the constants. This can be done by reducing the number of nodes in the graph or by optimizing the matrix multiplication itself.

The first optimization that can be done is to take out the $2^2$ $2^{2}$ constant in the number of nodes in the graph. We can do this using inclusion-exclusion. Let $f(G)$ $f (G)$ return the number of walks from node $1$ $1$ to node $N$ $N$ using the graph $G$ $G$ . To retrieve all the walks where both events $2$ $2$ and $3$ $3$ are visited, the answer is $f(G) - f(G \setminus \{2\}) - f(G \setminus \{3\}) + f(G \setminus \{2, 3\})$ $f (G) - f (G ∖ {2}) - f (G ∖ {3}) + f (G ∖ {2, 3})$ , where $G \setminus \{A\}$ $G ∖ {A}$ is the graph obtained after deleting the node $A$ $A$ . In practice, this saves a constant of around $16$ $16$ .

The second optimization comes from the observation that a lot of the entries in the matrix will always be equal to $0$ $0$ . This is because you can never decrease your supply of acorns throughout the walk. For example, a node encoded with an acorn supply of 3 can never reach a node with a supply of any integer less than 3. We can set up the matrix multiplication's loops efficiently to save a constant of around $4$ $4$ to $6$ $6$ in practice.

The third optimization comes from the observation that $f(G)$ $f (G)$ only needs to return the number of walks from node $1$ $1$ to node $N$ $N$ . The final matrix does not need to be an entire matrix, and we only need to keep the first row. This reduces the matrix into a vector, which we can do much more efficient vector-matrix multiplication instead. In practice, this saves a constant of around $2$ $2$ .

Time Complexity: $\mathcal{O}((N \cdot K + N)^3 \cdot \log E)$ $O ((N \cdot K + N)^{3} \cdot \log E)$ with a smaller hidden constant.

Subtask 6

For the full solution, all three optimizations should be used to pass within the time limit. A proper implementation should be able to pass with ease and will be left as an exercise.

Note that there is an alternate solution which uses Berlekamp-Massey to find the shortest linear recurrence relation for a sequence. The sequence can be determined using the dynamic programming solution from subtasks 2 and 3.

Time Complexity: $\mathcal{O}((N \cdot K + N)^3 \cdot \log E)$ $O ((N \cdot K + N)^{3} \cdot \log E)$ with a very small hidden constant.

Comments

There are no comments at the moment.