Solution for "KRUZNICE"

kruznice.md

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;
}