USACO Platinum 2023 March - Pareidolia

Explanation

Let's first try to solve the problem without updates on a single string. Notice that it is always optimal to take the earliest $b$ and then the earliest $e$ and then the earliest $s$ after that and so on because it maximizes the number of places you can search to find the next letter of "bessie".

Now let's try to solve the problem without updates for all substrings. Let $dp[i]$ be the number of positions of the string we have processed so far such that if we apply the greedy strategy described above, the next character we need to add is the $i$th character ($0$ indexed) of the string "bessie". We also need to add the substring starting from the current index. If the current letter of the string is $b$, then the next letter we need to add is $e$ so in this case we add $1$ to $dp[1]$. In every other case, we need to add $1$ to $dp[0]$ because the next character we add to fill "bessie" is $b$.

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	string s;
	cin >> s;
	int n = s.size();
	s = '$' + s;
	long long ans = 0;
	vector<long long> dp(6);

Notice that we can represent the transition from $dp$ to $ndp$ as a system of linear reccurences which depend on the letter.

B:$\\$ $ndp[0] = 0 \\$ $ndp[1] = dp[0] + 1 + dp[1] \\$ $ndp[2] = dp[2] \\$ $ndp[3] = dp[3] \\$ $ndp[4] = dp[4] \\$ $ndp[5] = dp[5] \\$ $newans = ans \\$

E:$\\$ $ndp[0] = dp[0] + 1 + dp[5] \\$ $ndp[1] = 0 \\$ $ndp[2] = dp[1] + dp[2] \\$ $ndp[3] = dp[3] \\$ $ndp[4] = dp[4] \\$ $ndp[5] = 0 \\$ $newans = ans + (n - i + 1) * dp[5] \\$

S:$\\$ $ndp[0] = dp[0] + 1 \\$ $ndp[1] = dp[1] \\$ $ndp[2] = 0 \\$ $ndp[3] = dp[2] \\$ $ndp[4] = dp[3] + dp[4] \\$ $ndp[5] = dp[5] \\$ $newans = ans \\$

I:$\\$ $ndp[0] = dp[0] + 1 \\$ $ndp[1] = dp[1] \\$ $ndp[2] = dp[2] \\$ $ndp[3] = dp[3] \\$ $ndp[4] = 0 \\$ $ndp[5] = dp[4] + dp[5] \\$ $newans = ans \\$

Identity (Any letter other than $b$, $e$, $s$, or $i$):$\\$ $ndp[0] = dp[0] + 1 \\$ $ndp[1] = dp[1] \\$ $ndp[2] = dp[2] \\$ $ndp[3] = dp[3] \\$ $ndp[4] = dp[4] \\$ $ndp[5] = dp[5] \\$ $newans = ans \\$

We can represent these linear recurrences with matrices where each letter of the string has its respective matrix. Now, multiplying all these matrices together will allow us to compute our answer. Note that since matrix multiplication is non commutative, we need to pay attention to the order of the two matrices that we are multiplying. In this case, we multiply matrices representing earlier indexes by matrices represting later indexes (rather than matrices representing later indexes by matrices represting later indexes).

We can optimize updates by building a segment tree on the matrices and updating each node with the respective matrix based on the given letter.

Note that if the letter is $e$, we need to set $mat[5][6]$ as $n - i + 1$.

The $i$-th column $(1 \leq i \leq 6)$ of each matrix represents $dp[i - 1]$, the $7$th column of each matrix represents the answer, and the $8$th column of each matrix is a constant $1$ so we can add $1$ to $dp[0]$ or $dp[1]$ at every index.

To extract the answer from the matrices, we can multiply the $1 \times 8$ matrix representing our initial state $[0, 0, 0, 0, 0, 0, 0, 1]$ by the product of all the matrices and look at the value in the $2$nd to last column, which we defined to be the answer.

This ends up being equivalent to the value located at $mat[7][6]$ of the product of all the matrices.

Implementation

The constant factor for this solution is high, so you may need to do some of the following optimizations to pass the test cases:

• Use C++.
• We can skip all $0$s while multiplying the matrices to speed up the multiplication.
• Use fastio and '\n' instead of endl.
• Build the segtree in $\mathcal{O}(N)$ rather than updating each index individually in $\mathcal{O}(N \log N)$.
• Use pragmas (Ofast, O3, unroll-loops, etc ...).

Time Complexity: $\mathcal{O}(N + Q \log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

const int sz = 8, N = 2e5 + 5;

using mat = array<array<long long, 8>, 8>;

mat operator*(mat const &a, mat const &b) {
	mat r;
	for (int i = 0; i < sz; i++) {