so yknow i was on the dp grind when someone posted this problem on the github issues for the usaco guide (you can test here, but prepare google translate)
so we have a buncha circles, intervals really
and we wanna remove some so that none of them intersect (they can be tangent tho)
so let's define min_remove[s][e]
as the minimum amount of circles we have to
remove given that the only circles we consider are the ones that are completely
in the interval [s, e]
the recurrence for this is pretty simple actually
we go through all the middle cutting points and calculate the cost for isolating
the left & right parts completely from each other, which would mean removing
all circles in the interval that intersect with mid
NOTE however, that we don't include the circle that goes completely around the
entire interval, because it doesn't interfere with the left & right parts
so if the cutting point was defined as mid
, we'd have this:
min_remove[s][e] = min_remove[s][mid - 1] + min_remove[s][mid + 1] + circles_in[mid]
so we just do a simple range dp with this relation and basically win the problem
right?
WRONG.
you see, the dp relation itself isn't hard- it's calculating circles_in
that's
the hard part (at least it was the case for me)
so to fix this, we need to define ANOTHER DP ARRAY
circles_in[s][e][i]
is going to be the number of circles that intersect the point
s + i
given that the only circles we consider are in [s, e]
(excluding the possible outermost one that covers both s
and e
)
...actually, i think i'll leave it to the code to explain it
it does a better job
but that's enough rambling, here's the solution
#include <iostream>
#include <vector>
#include <algorithm>
using std::cout;
using std::endl;
using std::vector;
using std::pair;
/**
* task: https://hsin.hr/2010/school/seniors/tasks.pdf
* submission: https://www.acmicpc.net/problem/3102
* (sample input omitted due to length)
*/
int main() {
int circle_num;
std::cin >> circle_num;
// they're gonna be specified by start & end instead of center & radius
vector<pair<int, int>> circles(circle_num);
int min = INT32_MAX;
// just gonna assume valid input lmao
for (int c = 0; c < circle_num; c++) {
int center;
int radius;
std::cin >> center >> radius;
circles[c] = {center - radius, center + radius};
min = std::min(min, circles[c].first);
}
// normalize the intervals
int max = INT32_MIN;
for (int c = 0; c < circle_num; c++) {
circles[c].first -= min;
circles[c].second -= min;
max = std::max(max, circles[c].second);
}
vector<vector<vector<int>>> circles_in(max + 1, vector<vector<int>>(max + 1));
// fancy meeting you here, this is the part where i calculate circles_in
for (const pair<int, int>& c : circles) {
// set our base cases
circles_in[c.first][c.second] = vector<int>(c.second - c.first - 1, 1);
}
for (int len = 2; len <= max; len++) {
for (int start = 0; start + len <= max; start++) {
int end = start + len;
if (circles_in[start][end].empty()) {
circles_in[start][end] = vector<int>(len - 1);
}
vector<int>& curr = circles_in[start][end];
const vector<int>& lprev = circles_in[start][end - 1];
const vector<int>& rprev = circles_in[start + 1][end];
const vector<int>& mprev = circles_in[start + 1][end - 1];
if (len > 2) {
curr.front() += lprev.front();
curr.back() += rprev.back();
for (int i = 1; i < curr.size() - 1; i++) {
/*
* add the ones contributed by the left & right,
* then account for overcounting by subtracting the stuff
* that's common to both (aka in the middle)
*/
curr[i] += lprev[i] + rprev[i - 1] - mprev[i - 1];
}
}
}
}
// excluse the outermost circles for each interval (if thereis one)
for (const pair<int, int>& c : circles) {
vector<int>& interval = circles_in[c.first][c.second];
for (int& i : interval) {
i--;
}
}
vector<vector<int>> min_removed(max + 1, vector<int>(max + 1, INT32_MAX));
// set up base cases
for (int i = 0; i <= max; i++) {
min_removed[i][i] = 0;
if (i < max) {
min_removed[i][i + 1] = 0;
}
}
// just do our range dp & win
for (int len = 2; len <= max; len++) {
for (int start = 0; start + len <= max; start++) {
int end = start + len;
for (int mid = start + 1; mid < end; mid++) {
int left = min_removed[start][mid];
int right = min_removed[mid][end];
min_removed[start][end] = std::min(
min_removed[start][end],
left + right + circles_in[start][end][mid - start - 1]
);
}
}
}
cout << min_removed[0][max] << endl;
}