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)$ ~\mathcal{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}$ ~\dbinom{K + 2}{3}~ to the repeated string, while a subsequence of CAW will contribute $\dbinom{K}{3}$ ~\dbinom{K}{3}~ to the total. Any other permutation of WAC found in $S$ ~S~ will contribute $\dbinom{K + 1}{3}$ ~\dbinom{K + 1}{3}~.

The time complexity of the dynamic programming solution is $\mathcal{O}(N \cdot K)$ ~\mathcal{O}(N \cdot K)~, while the time complexity of the second method is $\mathcal{O}(N^3)$ ~\mathcal{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)$ ~\mathcal{O}(N)~

Alternative Solution

We can first perform DP with only one copy of $S$ ~S~ using the following state: $dp[i][j] =$ ~dp[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]$ ~dp[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}$

Now, advancing from $dp[i]$ ~dp[i]~ to $dp[i+1]$ ~dp[i+1]~ is a linear transformation on the vector $dp[i]$ ~dp[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]$

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

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

Finally, the answer is the fourth row of $ans$ ~ans~.

Time complexity: $\mathcal{O}(N+K)$ ~\mathcal{O}(N+K)~ or $\mathcal{O}(N+\log K)$ ~\mathcal{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)$ ~\mathcal{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.

:)