USACO 2023 US Open Contest Silver Division - Field Day

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The main idea will be to rely on some meet in the middle to solve this problem. We fix the first half of a potential optimal answer and rely on preoomputations to solve the problem.

First we want to expand all strings to have a length of \(18\), effectively ignoring \(c\). Then we want to precompute for each possible combination of the first \(9\) bits, the maximum popcount we get if we also know the second half. This can be done in \(O((2^9)^3)\) but the constant is really good so it will work fast.

For each of the \(n\) strings, we can retrieve the answers from the things we already computed prior.

Source code

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

#include <iostream>

using namespace std;

int c, n, bst[512][512], is[512][512], cntbits[512];
bool viz[512];

int v[100002];

int main()
{    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    for(int i = 0; i <= 511; i++)
        cntbits[i] = __builtin_popcount(i);

    cin >> c >> n;
    for(int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;

        while(s.size() < 18)
            s += 'G';
        for(int j = 0; j <= 17; j++)
            if(s[j] == 'H')
                v[i] += (1<<(17 - j));
        is[v[i] / 512][v[i] % 512] = 1;
    }

    for(int i = 0; i <= 511; i++)
    {
        for(int lst = 0; lst <= 511; lst++)
            for(int cnd = 0; cnd <= 511; cnd++)
                if(is[i][cnd])
                {
                    viz[i] = 1;
                    bst[i][lst] = max(bst[i][lst], cntbits[(lst ^ cnd)]);
                }
    }

    for(int i = 1; i <= n; i++)
    {
        int ans = 0;
        for(int bits = 0; bits <= 511; bits++)
        {
            if(!viz[bits])
                continue;
            int partial_ans = cntbits[((v[i] / 512) ^ bits)] + bst[bits][v[i] % 512];
            ans = max(ans, partial_ans);
        }
        cout << ans << '\n';
    }

    return 0;
}