2

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.

Improve this question
3
  • 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. Commented Mar 20, 2012 at 12:08
  • 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. Commented Mar 20, 2012 at 12:19
  • I'd add that the linked solution was clearly not written to be easily and quickly understood. Try working through it. Commented Mar 20, 2012 at 12:20

2 Answers 2

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

"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 ?
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.
0

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.

Improve this answer

1 Comment

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.