USACO 2023 December Contest Silver Division - Target Practice

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

In order to approach this problem, we can look at all the cases in which we change a letter because there are not many of them. In order to do this efficiently, we use the fact that whenever we change a letter, only the positions nearby are changed (the offset is equal to \(2\)).

We can simulate the operations on a prefix, while also keeping track of a sum which tells us how many targets we hit in the first \(i\) positions. Then we take the operations backwards, trying to change the letter while also updating the targets that would be hit if we would change a letter on the prefix in such a way that the current position changes by \(1\) (again, the offset can be between \(-2\) and \(2\), as mentioned previously). In order to avoid double counting we can use a set which keeps track of whether a target was hit on the prefix or not.

For more implementation details check the code below.

Source code

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

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

int main() {
    int m, n;
    cin >> m >> n;

    const int OFFSET = 2e5 + 6;
    const int SIZE = OFFSET * 2 + 400005;

    vector<int> t(m + 1);
    vector<bool> p(SIZE, false);

    for (int i = 1; i <= m; i++) {
        cin >> t[i];
        p[OFFSET + t[i]] = true;
    }

    string s;
    cin >> s;
    s = " " + s;

    int poz = OFFSET;
    vector<int> pre(n + 1, 0);
    unordered_map<int, int> hit, whenhit;

    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1];

        if (s[i] == 'R') poz++;
        else if (s[i] == 'L') poz--;

        if (s[i] == 'F') {
            if (p[poz] && !hit[poz]) {
                pre[i]++;
                hit[poz] = i;
                whenhit[i] = poz;
            }
        }
    }

    int ret = pre[n];
    vector<set<int>> side(5), toadd(5);

    for (int i = n; i >= 1; i--) {
        if (whenhit[i]) {
            int hit_pos = whenhit[i];
            hit[hit_pos] = 0;
            whenhit[i] = 0;

            for (int j = 0; j <= 4; j++) {
                if (toadd[j].count(poz)) {
                    side[j].insert(poz);
                    toadd[j].erase(poz);
                }
            }
        }

        if (s[i] == 'R') {
            poz--;
            int ad = (p[poz] && !hit[poz] && !side[1].count(poz));
            ret = max(ret, max(pre[i - 1] + ad + (int)side[1].size(), pre[i - 1] + (int)side[0].size()));
        }
        else if (s[i] == 'L') {
            poz++;
            int ad = (p[poz] && !hit[poz] && !side[3].count(poz));
            ret = max(ret, max(pre[i - 1] + ad + (int)side[3].size(), pre[i - 1] + (int)side[4].size()));
        }
        else {
            ret = max(ret, max(pre[i - 1] + (int)side[1].size(), pre[i - 1] + (int)side[3].size()));

            for (int c = poz - 2; c <= poz + 2; c++) {
                if (c >= 0 && c <= SIZE - 1 && p[c]) {
                    if (hit[c])
                        toadd[c - poz + 2].insert(c);
                    else
                        side[c - poz + 2].insert(c);
                }
            }
        }
    }

    cout << ret;
    return 0;
}