Editorial for Wesley's Anger Contest 3 Problem 3 - Wesley Plays DDR

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.

Author: Zeyu

Subtask 1

For subtask 1, we only need to check if the combo moves match the current portion of the string. If it does not, we shift to the right by a character. There are no issues with selecting the longest combo in this case as there is only one possible combo.

Time Complexity: \mathcal{O}(|S| \cdot M \cdot |C|)

Subtask 2

For subtask 2 we are required to pick the longest combo that matches the next segment of moves. One clean way to do this is to sort the given combos in descending order by length. As you process through the string of combos the first combo in the moveset that matches will be the longest combo that can be performed.

Time Complexity: \mathcal{O}(M \cdot |C| \cdot \log M + |S| \cdot M \cdot |C|)

Comments


  • 0
    mrap  commented on July 10, 2024, 10:38 p.m.

    The explanation for Subtask 2 doesn't work for processing multiple combos of the same length, like in Sample 2. Have I missed something?