USACO 2024 Silver February - Prolem 1 - Target Practice II

USACO 2024 February Contest, Silver - Problem 1. Target Practice II

View the problem here:

I am new to USACO contests but I do feel like this Silver problem is a bad problem for any level of computer science competition!

  • First of all, the problem description is too long. You have to spend so much time to read through and to understand the problem.

  • Second, there are multiple subproblems that you need to solve in order to solve the entire problem:

    • Identify that lower right corners can only be targeted by cows with positive slopes, and upper right corners can only be targeted by cows with negative slows
    • Split cows into two groups: ones with positive slopes and ones with negative slopes
    • Assign cows into proper vertices
    • Check the condition that has no feasible solution
    • Find the optimal target assignment with the smallest range in Ys. This requires finding the maximum possible value of the smallest Ys, the minimum possible values of the largest Ys. These two steps involves sorting, min/max elements of a list, calculating slopes, list comparison, and binary search.

I am curious how many people actually solved this Silver problem during the competition.

Here is my C++ Solution.
It is based on the official Python solution.

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

bool pair_comp_first(pair<ll, ll>& a, pair<ll, ll>& b) {
    return a.first < b.first;

bool pair_comp_second(pair<ll, ll>& a, pair<ll, ll>& b) {
    return a.second < b.second;

// Helper function to check if slopes are possible
// given current_y as the y position, calculate the max_slope vector 
// that shoot from current_y
// sort this max_slope
// slopes vector is already sorted ascending order
// all existing slopes must be less than or equal to this max_slope vectors in order.

bool is_feasible(ll current_y, vector<pair<ll, ll>>& corners, vector<ll>& slopes) {
    vector<ll> max_slopes;
    for (auto& corner : corners) {
        max_slopes.push_back((corner.second - current_y) / corner.first);
    sort(max_slopes.begin(), max_slopes.end());
    // each slope must be less than or equal to max_slope
    for (int i = 0; i < slopes.size(); i++){
        if (slopes[i] > max_slopes[i])
            return false;
    return true;

// Solve for minimum y-intercept
ll find_min_y(vector<pair<ll, ll>>& corners4PositiveSlopes, vector<ll>& positiveSlopes) {
    sort(positiveSlopes.begin(), positiveSlopes.end());

    //  find the min y value among all corners.
    ll min_y = std::min_element(corners4PositiveSlopes.begin(),corners4PositiveSlopes.end(), pair_comp_second)->second;

    // find max x value among all corners.
    ll max_x = std::max_element(corners4PositiveSlopes.begin(), corners4PositiveSlopes.end(), pair_comp_first)->first;

    ll hi = min_y;
    ll lo = min_y - positiveSlopes.back() * max_x;

    // It must be feasible here
    //assert(is_feasible(lo, corners4PositiveSlopes, positiveSlopes));

    //Binary Search - move y between lo and hi until there is still a feasible solution
    while (lo < hi) {
        ll mid = (lo + hi + 1) / 2;
        if (is_feasible(mid, corners4PositiveSlopes, positiveSlopes)) {
            lo = mid;
        } else {
            hi = mid - 1;
    return lo;

// Solve for maximum y-intercept (convert negativeSlopesative slopes to positive)
ll find_max_y(vector<pair<ll, ll>>& corners4NegativeSlopes, vector<ll>& negativeSlopes) {
    vector<pair<ll, ll>> new_corners4NegativeSlopes;
    for (auto& target : corners4NegativeSlopes) {
        new_corners4NegativeSlopes.push_back({target.first, -target.second});
    vector<ll> new_positiveSlopes;
    for (auto& s: negativeSlopes) {
    return -find_min_y(new_corners4NegativeSlopes, new_positiveSlopes);

int main() {
    int T;
    cin >> T;

    while (T--) {
        int N;
        ll x1;
        cin >> N >> x1;
        vector<ll> y_coordinates(2*N);
        vector<pair<ll, ll>> corners4PositiveSlopes, corners4NegativeSlopes;
        vector<ll> slopes(4 * N);

        for (int i = 0; i < N; ++i) {
            ll y1, y2, x2;
            cin >> y1 >> y2 >> x2;
            y_coordinates[2*i] = y1;
            y_coordinates[2*i+1] = y2;
            corners4PositiveSlopes.push_back({x2, y1});
            corners4NegativeSlopes.push_back({x2, y2});

        for (int i = 0; i < 4 * N; ++i) {
            cin >> slopes[i];

        vector<ll> negativeSlopes, positiveSlopes;
        for (ll s : slopes) {
            if (s < 0) {
            } else {

        // Need at least N negative slopes and at least N positive slopes
        if (negativeSlopes.size() < N || positiveSlopes.size() < N) {
            cout << -1 << endl;

        //For those corners on the left side of the target
        // Smallest Y coordinates go with negativeSlopesative slopes
        // until all negativeSlopesative slopes are gone.
        sort(y_coordinates.begin(), y_coordinates.end());
        for (ll y : y_coordinates) {
            if (corners4NegativeSlopes.size() < negativeSlopes.size()) {
                corners4NegativeSlopes.push_back({x1, y});
            } else {
                corners4PositiveSlopes.push_back({x1, y});

        // Should have allocated the same number of negativeSlopesative slopes to corners4NegativeSlopes
        // and the remain positive slopes go to orners4PositiveSlopes

        if (corners4NegativeSlopes.size() != negativeSlopes.size() ||
            corners4PositiveSlopes.size() != positiveSlopes.size() ) {
                cout << -1 << endl;

        ll y_min = find_min_y(corners4PositiveSlopes, positiveSlopes);
        ll y_max = find_max_y(corners4NegativeSlopes, negativeSlopes);

        cout << y_max - y_min << endl;

    return 0;
1 Like

My guess on why they made this problem so complicated is probably to prevent cheating with GPT-4 (just take a look at the usaco subreddit and you’ll find so many posts about people using AI to cheat). The problemsetters probably intentionally tried to make the statement a lot harder to understand than in previous contests, so that AI would fail to solve the problem but good silver contestants wouldn’t.