USACO 2024 February Contest Silver Division - Test Tubes#
Problem link: here
Solution Author: Stefan Dascalescu
Problem Solution#
If we compress the two tubes (since we do not need to hold more than one consecutive equal element), the minimum solution is the number of elements in the first row + the number of elements in the second row \(-1\) (\(+1\) if the result is \(1\) for this equation).
To construct the solution, we notice that we can "reduce" elements, which is what we want to do, if we transport them from one tube to another and the first element is the same in both. Thus, we will have a tube (the first) in which we have element \(1\) and the second will hold the other element at the end. If the tubes have the same element, then we "reduce" one.
In the third tube, we select one of the other two tubes (with number of elements \(>1\)) and take the third tube a different value from the other. We take the tube that has the last value different from that of the 3rd tube and reduce it. Finally, we do the same operation for the other tube. We move from tube \(3\) the substance to the tube with the same value.
Source code#
The source code in C++ can be seen below.
#include <bits/stdc++.h>
using namespace std;
pair<long long, long long> inner[2 * 40001];
pair<long long, long long> outer[2 * 40001];
pair<long long, long long> outerPos[40001];
pair<long long, long long> outerNeg[40001];
bool compareSecond(const std::pair<int, int>& a, const std::pair<int, int>& b) {
return a.second < b.second;
}
long long slopes[4 * 40001];
long long negSlopes[4 * 40001];
long long posSlopes[4 * 40001];
int main() {
int t;
cin >> t;
while (t--) {
int n;
long long x1;
cin >> n >> x1;
for (int i = 0; i < n; i++) {
long long v1, v2, v3;
cin >> v1 >> v2 >> v3;
inner[2 * i] = make_pair(x1, v1);
inner[2 * i + 1] = make_pair(x1, v2);
outer[2 * i] = make_pair(v3, v1);
outerPos[i] = make_pair(v3, v1);
outer[2 * i + 1] = make_pair(v3, v2);
outerNeg[i] = make_pair(v3, v2);
}
sort(inner, inner + 2 * n, compareSecond);
sort(outer, outer + 2 * n, compareSecond);
for (int i = 0; i < 4 * n; i++) {
cin >> slopes[i];
}
int pos = 0;
int neg = 0;
int c1 = 0;
int c2 = 0;
for (int i = 0; i < 4 * n; i++) {
if (slopes[i] > 0) {
pos++;
posSlopes[c1] = slopes[i];
c1++;
}
if (slopes[i] < 0) {
neg++;
negSlopes[c2] = -1 * slopes[i];
c2++;
}
}
sort(posSlopes, posSlopes + c1);
sort(negSlopes, negSlopes + c2);
for (int i = 0; i < c2; i++) {
negSlopes[i] *= -1;
}
if (pos < n || neg < n) {
// not enough positive / negative to make it work.
cout << "-1\n";
continue;
}
priority_queue<long long> pq; // these are the slopes, we greedily pick the highest abs value slope
for (int i = n; i < c1; i++) { // save n with smallest slope
pq.push(-1 * posSlopes[i]);
}
for (int i = n; i < c2; i++) { // save n with smallest abs slope
pq.push(-1 * negSlopes[i]);
}
long long upBound = 0;
long long downBound = 0;
bool chosen = false;
for (int i = 0; i < 2 * n; i++) {
if (!chosen) {
upBound = outer[i].second;
downBound = outer[i].second;
chosen = true;
}
upBound = max(upBound, outer[i].second);
downBound = min(downBound, outer[i].second);
}
for (int i = 0; i < 2 * n; i++) {
// iterate through all inner, and assign
long long x = inner[i].first;
long long y = inner[i].second;
long long curSlope = -1 * pq.top();
pq.pop(); // this shouldn't give an error, in theory
long long b = y - curSlope * x; // using y = mx + b
upBound = max(upBound, b);
downBound = min(downBound, b);
}
// binary search on the highest the top values can go, needing a negative slope
long long left = upBound;
long long right = 1000000000000000001;
while (left < right) {
long long mid = left + (right - left) / 2;
// mid = 12;
bool works = true;
vector<long long> reqSlopesNeg;
for (int i = 0; i < n; i++) {
// go through all thigns needing a negative slope
long long deltaY = outerNeg[i].second - mid;
long long deltaX = outerNeg[i].first;
long long reqSlope = deltaY / deltaX;
// any slope BIGGER than this will work.
reqSlopesNeg.push_back(-1 * reqSlope);
}
sort(reqSlopesNeg.begin(), reqSlopesNeg.end());
for (int i = 0; i < n; i++) {
long long avail = negSlopes[i];
long long need = -1 * reqSlopesNeg[i];
if (need > avail) {
// we don't have what we need
works = false;
break;
}
}
if (works) {
right = mid;
} else {
left = mid + 1;
}
// break;
}
long long ans = left;
left = -1000000000000000001;
right = downBound;
while (left < right) {
long long mid = left + (right - left + 1) / 2;
// mid = -5;
bool works = true;
vector<long long> reqSlopesPos;
for (int i = 0; i < n; i++) {
// go through all thigns needing a positive slope
long long deltaY = outerPos[i].second - mid;
long long deltaX = outerPos[i].first;
long long reqSlope = deltaY / deltaX;
// any slope BIGGER than this will work.
reqSlopesPos.push_back(reqSlope);
}
sort(reqSlopesPos.begin(), reqSlopesPos.end());
for (int i = 0; i < n; i++) {
long long avail = posSlopes[i];
long long need = reqSlopesPos[i];
if (need < avail) {
// we don't have what we need
works = false;
break;
}
}
if (works) {
left = mid;
} else {
right = mid - 1;
}
// break;
}
cout << ans - left << "\n";
}
}