Checklist
Make sure to read all of How to ask for help on a problem before asking for help.
Problem Info
Question
My solution, unlike the usaco.guide solution, calculates the optimal speed manually. Just like the editorial, I store dp[i][j] for which i is the bitmask of mice and j is the last one, but here it stores a pair {s, t} where s is the optimal initial velocity and t is the time to reach j with bitmask i. I essentially loop over each final bit and then the previous ending and use that previous state’s time & speed to calculate the “arrival time” for the new final mouse (accounting for speed reduction). If we arrive to late, then we scale the speed to arrive exactly on time. However, this fails test case 4 for some reason. Why is that?
What I’ve Tried
Let us know what you’ve tried. Have you tried downloading the test data? Have you tried writing a brute force script? etc.
I originally thought it was some sort of out-of-bounds thing which is why I made literally everything a double - but that of course failed. I even used ChatGPT for 3+ hours - but it didn’t help much besides just go back to my original solution. I made a test-case-generator and all - but it didn’t find any counter-example.
My Work
#include <bits/stdc++.h>
using namespace std;
// data type for each Mouse
struct Mouse {
double x, y, time;
};
// Euclidean distance
double distance(double x1, double y1, double x2, double y2) {
return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int mouse_count;
cin >> mouse_count;
vector<Mouse> mice(mouse_count);
for (int index = 0; index < mouse_count; index++) {
cin >> mice[index].x >> mice[index].y >> mice[index].time;
}
double factor;
cin >> factor;
// 2D Bitmask DP of the mice, the ending mouse, and the initial speed/end time.
vector dp(1 << mouse_count, vector(mouse_count, make_pair(1'000'000'000.0, 1'000'000'000.0)));
// Solve the base case for which we have only 1 mouse: the speed is just distance/time.
for (int index = 0; index < mouse_count; index++) {
double speed = distance(0, 0, mice[index].x, mice[index].y)/mice[index].time;
dp[1 << index][index] = make_pair(speed, mice[index].time);
}
for (int bitmask = 1; bitmask < 1 << mouse_count; bitmask++) {
// Ignore if this is the base case
int bit_count = __builtin_popcount(bitmask);
if (bit_count == 1) continue;
// Final mouse to visit
for (int bit = 0; bit < mouse_count; bit++) {
if ((bitmask & 1 << bit) == 0) continue;
Mouse destination = mice[bit];
// Final mouse for previous state
for (int end = 0; end < mouse_count; end++) {
if (((bitmask ^ 1 << bit) & 1 << end) == 0) continue;
Mouse start = mice[end];
auto [original_speed, start_time] = dp[bitmask ^ 1 << bit][end];
// Apply reduction factor
double current_speed = original_speed * pow(factor, bit_count - 1);
double segment = distance(start.x, start.y, destination.x, destination.y);
double end_time = segment / current_speed + start_time;
// Scale the speed if we arrive to late.
if (end_time > destination.time) {
original_speed *= end_time/destination.time;
end_time = destination.time;
}
// We can't go slower to arrive exactly on time no matter what because the prior minimum
// was already the minimum. We can only go faster.
dp[bitmask][bit] = min(dp[bitmask][bit], make_pair(original_speed, end_time));
}
}
}
cout << min_element(dp[(1 << mouse_count) - 1].begin(), dp[(1 << mouse_count) - 1].end())->first << "\n";
return 0;
}
Explanation above under “Question”.