Subtask 1

For subtask 1, we simply brute-force over all possible ways to break the string into subsequences.

Time complexity: ~\mathcal{O}(N!)~

Subtask 2

For subtask 2, notice that all possible scores will be a multiple of ~3~. This is because each subsequence will either contribute a score of:

• ~0~, if the first and last characters are the same
• ~-3~, if the first character is A and the last character is B
• or ~3~, if the first character is B and the last character is A

So, we can find the maximum number of subsequences with A as the starting character and B as the ending character by iterating through the string and keeping track of the number of As. We will always pair up a B with an A if there are any As available. We can then repeat this process again, iterating in reverse this time to find the maximum number of subsequences with B as the starting character and A as the ending character. Afterwards, we will have found the minimum and maximum possible total scores for the string. Finally, we notice that it is possible to achieve any total score between the minimum and maximum total score that is a multiple of ~3~, since we can just choose to remove the contribution of any sequence by making all of its characters pair with itself as separate subsequences instead.

Time complexity: ~\mathcal{O}(N)~

Subtask 3

For subtask 3, we should first make the observation that the expression for the score of a subsequence ~(v_{c_i}-v_{c_j})(v_{c_i}+v_{c_j})~ can be rewritten as ~(v_{c_i}^2-v_{c_j}^2)~. So, the contribution from starting or ending a subsequence with a character is independent from the other character at the beginning or end of the subsequence.

Now, we will use dynamic programming. Define ~dp[i][j][k] = 1~ if it is possible to have a total score of ~k~ from the first ~i~ characters such that there are ~j~ "open" sequences, and ~dp[i][j][k] = 0~ otherwise. Note that the absolute value of the total score for a string of length ~N~ is bounded by ~26^2 \cdot \lfloor \frac{N}{2} \rfloor~.

There are 3 cases to consider when transitioning from ~i-1~ to ~i~:

• We start a new subsequence with ~c_i~ as the first character.
  • ~c_i~ will contribute ~v_{c_i}^2~ to the total score. So, we transition from ~dp[i-1][j-1][k-v_{c_i}^2]~.
• We end an "open" sequence with ~c_i~ as the last character.
  • ~c_i~ will contribute ~-v_{c_i}^2~ to the total score. So, we transition from ~dp[i-1][j+1][k+v_{c_i}^2]~.
• We make a subsequence of length ~1~ just containing ~c_i~, or we add ~c_i~ to an "open" sequence without ending it.
  • ~c_i~ will not contribute to the total score. So, we transition from ~dp[i-1][j][k]~.

To save memory, notice that transitions to ~i~ come directly from ~i-1~, allowing us to cut down one dimension in our DP array. We can also improve our constant factor by instead defining ~dp[i][j]~ to be the set of possible total scores from the first ~i~ characters such that there are ~j~ "open" sequences, with similar transitions.

Time complexity: ~\mathcal{O}(26^2 \cdot N^3)~

Subtask 4

For subtask 4, we can optimize our previous DP transitions with bitsets. In Java or Python, it suffices to use arbitrarily large integers to represent bitsets. The implementation is left as an exercise to the reader.

Time complexity: ~\mathcal{O}(26^2 \cdot \frac{N^3}{32})~