CIELLAND - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

This problem can be solved by using binary search. Let’s consider the following Problem A.

Problem A: There are N circles. The center of the i-th circle is (xi, yi) and all circles have the radii R. And let we can draw X lines such that any circle intersects with at least one line. What is the minimal X?

It is clear that if and only if the answer of Problem A is no more than K, then the answer of the original problem is no more than R. Therefore if Problem A can be solved, then we can solve the original problem by using binary search.

Now, let’s consider solving Problem A. At first, the lines can be limited to common tangents to two circles. Because if a line intersects with some (at least 2) circles, we can move the line such that a moved line intersects with the same circles, and the moved line is one of common tangents. If a line intersects less than 2 circles, it is useless (but be careful of the case N = 1). There are at most 4 lines that is common tangents to two circles, so we consider at most 2 * N * (N-1) lines.

Then we can calculate the minimal X by using dynamic programming. DP[mask] denotes the minimal number of lines such that all circles in mask intersect at least one line, where mask is a subset of circles. At first, we set DP[empty set] = 0 and DP[not empty set] = infinity. For each line, we calculate the set S of circles which intersect the line, and DP[union of U and S] are changed into min(DP[union of U and S], DP[U] + 1) for all U. Then we can obtain minimal X as DP[set of all circles].

Problem A can be solved with O(N2 * 2N) time. Therefore the original problem can be solved with O(L * N2 * 2N) time, where L is the number of the loops corresponding binary search.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.