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)

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

The time complexity of the dynamic programming solution is \mathcal{O}(N \cdot K), while the time complexity of the second method is \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 using dynamic programming and adding to the total the different cases accordingly.

Time complexity: \mathcal{O}(N)

Alternative Solution

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

Then, we can rephrase dp[i] as a 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] to dp[i+1] is a linear transformation on the vector dp[i]. Thus, we can think of each character in S as a matrix.

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

For a single copy of S:

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

And for K concatenations of S:

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

Finally, the answer is the fourth row of ans.

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


  • 4
    Moana  commented on Jan. 25, 2021, 2:52 p.m.

    My solution in the contest combines this editorial with matrix power that works in 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.