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) {
new_positiveSlopes.push_back(-s);
}
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) {
negativeSlopes.push_back(s);
} else {
positiveSlopes.push_back(s);
}
}
// Need at least N negative slopes and at least N positive slopes
if (negativeSlopes.size() < N || positiveSlopes.size() < N) {
cout << -1 << endl;
continue;
}
//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;
continue;
}
ll y_min = find_min_y(corners4PositiveSlopes, positiveSlopes);
ll y_max = find_max_y(corners4NegativeSlopes, negativeSlopes);
cout << y_max - y_min << endl;
}
return 0;
}
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.