USACO 2023 US Open Contest Gold Division - Pareidolia

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem can be done relatively easily using DP by having at first something like \(dp[i][j][pos]\) = min cost if among first \(i\) characters, we created \(j\) bessies and the \(j+1^{th}\) bessie is completed until position pos.

However, this DP would run in \(O(n^2)\) which is too slow for our constraints. A key observation is that for a given position, we are always better off by having more bessies even if they are more expensive to create as we create them one by one.

Based on this observation, we want to discard \(j\) and reframe the dp as \(dp[i][pos]\) = {max # of bessies, min cost to achieve this count} which can be implemented easily in linear time.

A key thing to consider about this technique is the fact that it is used in other problems too, such as Elevator Rides from CSES (they use it there in the context of a bitmask dp).

Basically this technique is based on reframing the state by using less dimensions and using one of the dimensions as part of the thing we evaluate in our final outcome.

Source code

The source code in C++ can be seen below.

#include <iostream>
#include <vector>

using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;

    int n = s.size();

    vector<int> v(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    s = ' ' + s;

    vector<vector<pair<int, int>>> dp(n+1, vector<pair<int, int>> (7, {-1, (1<<30)}));
    dp[0][0] = {0, 0};

    string pattern = "#bessie";
    for (int i = 0; i < n; i++) {
        for (int len = 0; len < 6; len++) {
            if (dp[i][len].first == -1) {
                continue;
            }
            // don't pick current character
            dp[i+1][len] = max(dp[i+1][len], {dp[i][len].first, dp[i][len].second - v[i+1]});
            // pick current character
            if (s[i+1] == pattern[len+1]) {
                dp[i+1][(len+1)%6] = max(dp[i+1][(len+1)%6], {dp[i][len].first + (len == 5), dp[i][len].second});
            }
            else {
                // if it's b, we start from pos 1, otherwise from pos 0
                if (s[i+1] != 'b') {
                    dp[i+1][0] = max(dp[i+1][0], {dp[i][len].first, dp[i][len].second});
                }
                else {
                    dp[i+1][1] = max(dp[i+1][1], {dp[i][len].first, dp[i][len].second});
                }
            }
        }
    }

    pair<int, int> maxi = {-1, (1<<30)};
    for (int i = 0; i < 6; i++) {
        maxi = max(maxi, dp[n][i]);
    }
    cout << maxi.first << '\n' << -maxi.second << '\n';
    return 0;
}