## 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

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

Time complexity:

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 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 can contribute to the total number of subsequences of WAC in the repeated string. A subsequence of WAC will contribute to the repeated string, while a subsequence of CAW will contribute to the total. Any other permutation of WAC found in will contribute .

The time complexity of the dynamic programming solution is , while the time complexity of the second method is .

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 using dynamic programming and adding to the total the different cases accordingly.

Time complexity:

##### Alternative Solution

We can first perform DP with only one copy of using the following state: The number of subsequences of the prefix equal to the first characters of WAC (This means that )

Then, we can rephrase as a row vector in the following way:

Now, advancing from to is a linear transformation on the vector . Thus, we can think of each character in as a matrix.

Let be the matrix that represents the linear transformation of character .

For a single copy of :

And for concatenations of :

Finally, the answer is the fourth row of .

Time complexity: or