Editorial for Wesley's Anger Contest 6 Problem 4 - Runway Lights - Olympiads Online Judge

Editorial for Wesley's Anger Contest 6 Problem 4 - Runway Lights

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.

Authors: Plasmatic, Zeyu

Subtask 1

For the first subtask, we can try all triplets of indices and explicitly find all subsequences of WAC in the string.

Time complexity: $\mathcal{O}((N \cdot K)^3)$ $O ((N \cdot K)^{3})$

Subtask 2

There are two different approaches for this subtask. The first method involves dynamic programming, where you count the number of subsequences of W, WA and WAC for the first $i$ $i$ characters. This solution should run in linear time to the size of the repeated string.

The second method extends the first subtask's solution. A subsequence of a WAC permutation found in $S$ $S$ can contribute to the total number of subsequences of WAC in the repeated string. A subsequence of WAC will contribute $\dbinom{K + 2}{3}$ $(\binom{K + 2}{3})$ to the repeated string, while a subsequence of CAW will contribute $\dbinom{K}{3}$ $(\binom{K}{3})$ to the total. Any other permutation of WAC found in $S$ $S$ will contribute $\dbinom{K + 1}{3}$ $(\binom{K + 1}{3})$ .

The time complexity of the dynamic programming solution is $\mathcal{O}(N \cdot K)$ $O (N \cdot K)$ , while the time complexity of the second method is $\mathcal{O}(N^3)$ $O (N^{3})$ .

Subtask 3

For the full solution, both solutions from subtask 2 are combined. This can be done by trying and counting the subsequences for all permutations of WAC on string $S$ $S$ using dynamic programming and adding to the total the different cases accordingly.

Time complexity: $\mathcal{O}(N)$ $O (N)$

Alternative Solution

We can first perform DP with only one copy of $S$ $S$ using the following state: $dp[i][j] =$ $d p [i] [j] =$ The number of subsequences of the prefix $S[1 \dots i]$ $S [1 \dots i]$ equal to the first $j$ $j$ characters of WAC (This means that $j \in [0, 3]$ $j \in [0, 3]$ ).

Then, we can rephrase $dp[i]$ $d p [i]$ as a $4$ $4$ row vector in the following way:

$\displaystyle dp[i] = \begin{bmatrix}dp[i][0]\\dp[i][1]\\dp[i][2]\\dp[i][3]\end{bmatrix}$ $d p [i] = [\begin{matrix} d p [i] [0] \\ d p [i] [1] \\ d p [i] [2] \\ d p [i] [3] \end{matrix}]$

Now, advancing from $dp[i]$ $d p [i]$ to $dp[i+1]$ $d p [i + 1]$ is a linear transformation on the vector $dp[i]$ $d p [i]$ . Thus, we can think of each character in $S$ $S$ as a matrix.

Let $M_i$ $M_{i}$ be the matrix that represents the linear transformation of character $S_i$ $S_{i}$ .

For a single copy of $S$ $S$ :

$\displaystyle ans = (M_{|S|} M_{|S|-1} \dots M_1) dp[0]$ $a n s = (M_{| S |} M_{| S | - 1} \dots M_{1}) d p [0]$

And for $K$ $K$ concatenations of $S$ $S$ :

$\displaystyle ans = (M_{|S|} M_{|S|-1} \dots M_1)^K dp[0]$ $a n s = (M_{| S |} M_{| S | - 1} \dots M_{1})^{K} d p [0]$

Finally, the answer is the fourth row of $ans$ $a n s$ .

Time complexity: $\mathcal{O}(N+K)$ $O (N + K)$ or $\mathcal{O}(N+\log K)$ $O (N + \log K)$

Comments

4

Moana commented on Jan. 25, 2021, 2:52 p.m. ← edited →

My solution in the contest combines this editorial with matrix power that works in $\mathcal{O}(N+\log K)$ $O (N + \log K)$ .

3

Zeyu commented on Jan. 25, 2021, 3:15 p.m.

Yes, there are a lot of approaches that work for this problem. Plasmatic is currently writing an alternative editorial for the matrix solution :)

3

Plasmatic commented on Jan. 25, 2021, 4:32 p.m.

:)