USACO 2022 February Contest Silver Division - Robot Instructions

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Notice that we are trying to take a subset of indices for which the sum of their positions gives the final point (or where Bessie should end up). We apply the meet in the middle technique. After we do the sums, we try to combine them so that they give the desired pair, and for each different number of indices selected we display the answer.

Source code

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

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

int main() {

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

    int n;
    cin >> n;

    long long x, y;
    cin >> x >> y;

    vector<pair<int, int> > instructions(n);
    vector<vector<pair<long long, long long> > > cnt(21);

    for (int i = 0; i < n; i++) {
        cin >> instructions[i].first >> instructions[i].second;
    }

    int hf = n/2;

    for (int i = 0; i < (1<<hf); i++) {
        long long dx = 0, dy = 0;
        int sz = 0;
        for (int j = 0; j < hf; j++) {
            if (i & (1<<j)) {
                dx += instructions[j].first;
                dy += instructions[j].second;
                sz++;
            }
        }

        cnt[sz].push_back({dx, dy});

    }

    vector<int> longest_equal(21);
    for (int i = 0; i <= 20; i++) {
        sort(cnt[i].begin(), cnt[i].end());
        int eq = 1;
        for (int j = 1; j < (int) cnt[i].size(); j++) {
            if (cnt[i][j] == cnt[i][j-1]) {
                eq++;
            }
            else {
                longest_equal[i] = max(longest_equal[i], eq);
                eq = 1;
            }
        }
        longest_equal[i] = max(longest_equal[i], eq);
        int p2 = 1;
        while (p2 + p2 - 1 < longest_equal[i]) {
            p2 *= 2;
        }
        longest_equal[i] = p2;
    }

    hf = n - n/2;

    vector<long long> ans(n+1);

    for (int i = 0; i < (1<<hf); i++) {
        long long dx = 0, dy = 0;
        int sz = 0;
        for (int j = 0; j < hf; j++) {
            if (i & (1<<j)) {
                dx += instructions[n/2+j].first;
                dy += instructions[n/2+j].second;
                sz++;
            }
        }


        for (int j = 0; j <= 20; j++) {

            int L = -1;
            int p2 = (1<<17);
            pair<long long, long long> candidate = {x - dx, y - dy};
            while (p2) {
                if (L + p2 < (int) cnt[j].size() && cnt[j][L + p2] < candidate) {
                    L += p2;
                }
                p2 >>= 1;
            }

            if (L + 1 < (int) cnt[j].size() && cnt[j][L + 1] == candidate) {
                int R = L + 1;
                p2 = longest_equal[j];
                while (p2) {
                    if (R + p2 < (int) cnt[j].size() && cnt[j][R + p2] == candidate) {
                        R += p2;
                    }
                    p2 >>= 1;
                }
                ans[sz + j] += R - L;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}