Programming puzzle related to binary search

Question

I am trying to solve the following question which was part of a programming contest:

---

PROBLEM ID : CIELLAND

Chef Ciel develops a new island with her restaurants. In the island, Ciel intends to built N restaurants, and the coordinate of the i-th restaurant will be (xi, yi). In addition, Ciel is going to create K roads, whose location is not decided yet. Each road must be a infinitely long straight line.

Let di be the distance between the i-th restaurant and the nearest road from the i-th restaurant. Ciel would like to create K roads which minimize max(d1, d2, ..., dN). Your task is to calculate the minimal value of max(d1, d2, ..., dN).

---

Any ideas as to how I should approach it? Also, the contest editorial is out ( http://www.codechef.com/wiki/march-2012-cook-problem-editorials ) but I cannot understand the solution.

Any help regarding the approach to be followed would be much appreciated.

• Stefan Marinov: The problem looks somehow like Cluster analysis and Voronoi diagrams. My idea is to do something like modified k-means clustering or other dynamic programming technique.
• Marcin: Are you familiar with the travelling salesman problem? This appears to be a variant of that; in general, this is a type of dynamic programming problem.
• Marcin: I'd add that the linked solution was clearly not written to be easily and quickly understood. Try working through it.

Answer 1

At a high level, they are reformulating the problem so that it is easier to solve. By casting in the light below, they limit the number of possible lines to consider.

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?

To explain further, lets rephrase the problem A in words: The restaurants are sticklers for rules and there is a rule that says all restaurants must agree on a single maximum distance from the road - this'll be R. The circle created by the restaurant and R represents the place where a line needs to intersect to satisfy this requirement. The new problem asks the minimum number of roads to do this.

If this is not possible in under K roads, then something has to change. We can't add roads per the original problem, but we can modify R. This is where binary search comes in, but we have to solve problem A first.

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.

The important part is this, we need to find lines that intersect more than one circle. At most four lines from each pair of circle need be considered, check the source codes for implementation.

The next big step is the dynamic programming which find the minimum number of lines to cover all the circles. The 'mask' is a bitmask indicating which circles have been hit as each line is considered.

This solves the problem, but now we have to convert back. Remember R? We can now binary search to find the minimum R such that X<=K. In terms of my reformulation of Problem A, its the smallest distance all restaurant will agree to and still be serviced by a road

Hope that helps, tricky, but interesting problem.

• arya: "The important part is this, we need to find lines that intersect more than one circle. At most four lines from each pair of circle need be considered". I am sorry but I didn't quite get that. I think you said that the lines need to intersect more than one circle because otherwise the line would not give us the minimum lines required. Am I right ? And why consider atmost 4 lines from each pair ?
• dfb: Unless in the case where there is only one city, we need a line to intersect at least two circles. If a line intersects just one circle, it's not worth considering that line because there is some other circle we can intersect AND still intersect this line. Think of it like two points if thats easier - there is always a line that intersects two points. The 4 lines are the those composed of the common tangents of two circles. You can try proving this for yourself that there are no more than 4, it's hard for me to do so here without drawing it.

Answer 2

You should be able to solve it as k means clustering problem. Initially seed with a bunch of lines. Then iteratively update points assignment to lines and optimalline given points.

• dfb: I think 'Iteratively updating' here you are talking about the EM algorithm,correct? This is an approximation and won't work for a programming contest. It is interesting to note that the solution is an exponential time one