Editorial for Wesley's Anger Contest 6 Problem 4 - Runway Lights
Submitting an official solution before solving the problem yourself is a bannable offence.
For the first subtask, we can try all triplets of indices and explicitly find all subsequences of
WAC in the string.
There are two different approaches for this subtask. The first method involves dynamic programming, where you count the number of subsequences of
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.
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