USACO 2024 February Contest Silver Division - Target Practice II

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We notice that for some targets we cannot place cows with a certain orientation (negative/positive) because that would mean shooting through the rectangle.

We also notice that, for the leftmost targets, it is optimal to place cows with negative slope as high as possible and those with positive slope as low as possible.

Thus, we can binary search for the answer to how low/high we place the cows, establishing a maximum slope (in modulo) that a cow shooting towards target \(x\) can have for all targets.

Source code

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

#include <algorithm>
#include <cmath>
#include <iostream>
#include <set>
#include <vector>
#define int long long
using namespace std;
int t;
vector<int> s, neg, poz;
bool ok(vector<pair<int, int>> needs_poz, vector<int> poz, int min_y) {
    vector<int> max_slope;
    for (auto chestie : needs_poz) {
        int x = chestie.first, y = chestie.second;
        max_slope.push_back((y - min_y) / x);
    }
    sort(max_slope.begin(), max_slope.end());
    for (int i = 0; i < max_slope.size(); i++) {
        if (poz[i] > max_slope[i]) {
            return 0;
        }
    }
    return 1;
}
int solvemn(vector<pair<int, int>> needs_poz, vector<int> poz) {
    sort(poz.begin(), poz.end());
    int st = -1e18, dr = 1e18, poz2 = -1e18;
    while (st <= dr) {
        int mij = (st + dr) >> 1ll;
        if (ok(needs_poz, poz, mij)) {
            st = mij + 1;
            poz2 = mij;
        } else
            dr = mij - 1;
    }
    return poz2;
}
int solvemx(vector<pair<int, int>> needs_neg, vector<int> neg) {
    for (int i = 0; i < needs_neg.size(); i++) {
        needs_neg[i].second = -needs_neg[i].second;
    }
    for (int i = 0; i < neg.size(); i++) {
        neg[i] = -neg[i];
    }
    return -solvemn(needs_neg, neg);
}
void solve() {
    int n, x;
    s.clear();
    neg.clear();
    poz.clear();
    cin >> n >> x;
    vector<int> leftmost;
    vector<pair<int, int>> needs_poz, needs_neg;
    for (int i = 1; i <= n; i++) {
        int y, y1, x1;
        cin >> y >> y1 >> x1;
        leftmost.push_back(y1);
        leftmost.push_back(y);
        needs_poz.push_back({x1, y});
        needs_neg.push_back({x1, y1});
    }
    for (int i = 1; i <= 4 * n; i++) {
        int x;
        cin >> x;
        s.push_back(x);
        if (x < 0) {
            neg.push_back(x);
        } else
            poz.push_back(x);
    }
    if (neg.size() < n || poz.size() < n) {
        cout << "-1\n";
        return;
    }
    sort(leftmost.begin(), leftmost.end());
    for (auto y : leftmost) {
        if (needs_neg.size() < neg.size()) {
            needs_neg.push_back({x, y});
        } else {
            needs_poz.push_back({x, y});
        }
    }
    int y_min = solvemn(needs_poz, poz);
    int y_max = solvemx(needs_neg, neg);
    cout << y_max - y_min << "\n";
    return;
}
int32_t main() {
    ios ::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> t;
    while (t--) 
        solve();
    return 0;
}