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

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

,##### 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:**

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

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

## Comments

My solution in the contest combines this editorial with matrix power that works in .

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

:)