Link to the problem: https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-1/problems/A3

We can represent the string with the sequence of non-negative integers $W = t_1, a_1, t_2, a_2, \dots,t_k,a_k,t_{k+1}$, where each $a_i$ represents the length of group of "O"s or "X"s with possibly "F"s in between such that $a_i$ and $a_{i+1}$ represent different character groups, and each $t_i$ represents the number of consecutive "F"s in between them (possibly zero).

For example, the string "FOFOFFXOFXX" can be represented with the sequence:

$t_1 = 1, a_1 = 3 (\text{OFO}), t_2 = 2, a_2 = 1 (\text{X}), t_3 = 0, a_3 = 1 (\text{O}), t_4 = 1, a_4 = 2 (\text{XX}), t_5 = 0$.

From this model, we can directly calculate the answer in terms of $a_i$ and $t_i$. Note that a substring starting from a character in the group $(t_j,a_j)$ and ending at a character in the group $(a_i,t_{i+1})$ will have $(i-j)$ switches. And there are $(t_j+a_j)\times(a_i+t_{i+1})$ such substrings. Hence, the desired answer is the sum over all possible pairs of $i$ and $j$:

$$ans=\displaystyle\sum_{i=1}^k \sum_{j=1}^i(i-j)(t_j+a_j)(a_i+t_{i+1})$$

What's left is how we update this value as the string grows, either by adding a single character or by duplicating it.

Initially, the string is empty and $ans=0$, $k=0$, $t_1=0$. There are 5 types of different operations:

  1. Appending "F" or "wildcard". This would simply add 1 to $t_{k+1}$.

  2. Appending "X" or "O", matching with the last non-"F" character of the string. This would squash the $a_k+t_{k+1}+1$ last characters into a new group. Hence, $a_k'=a_k+t_{k+1}+1$ and $t_{k+1}'=0$.

  3. Appending "X" or "O", different from the last non-"F" character of the string. This would increase $k$, the number of groups and add a group of $a_{k'=k+1}=1, t_{k'=k+1}=0$.

  4. Duplicating the string, where the first group $a_1$ and the last group $a_k$ are of different characters. The resulting sequence will be:

    $$⁍$$

    The number of groups will be doubled, i.e. $k'=2k$.

  5. Duplicating the string, where the first group $a_1$ and the last group $a_k$ are of the same characters. Note that the last group and the first group (of the duplicated one) will merge into a single group. The resulting sequence will be:

    $$⁍$$

    The number of groups will be $k'=2k-1$.

In each of the cases above, we will calculate the formula for the new $ans'$. In order to do this efficiently, we need to maintain some other values:

Powered by Fruition