PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
The key to solving this problem is to use the fact that it is possible to cover all milestones/points with just 7 roads/lines. By pigeonhole principle, this gives us a lower bound on the answer m=n/7. Let’s have a look at a non-deterministic(Monte Carlo) approach. Pick two random points (A, B) and count how many points lie on the line AB. If we repeat this several times, we are unlikely to miss the optimal solution. But just how unlikely are we?
The probability of choosing a pair of points which both lie on the optimal line is (m/n)^2 = 1/49. We won’t hit the right solution after k iterations with probability (48/49)^k. But remember that you have to pass all 30 test cases, which gives us the probability of finding the right solution: (1-(48/49)^k)^30. You don’t stand a chance with 100 iterations but you are well above 99% with 500.
However, many competitors took a different approach. Assume that we’re dealing with 50 points or more. In this case, the solution we’re looking for has to correspond to one of the original 7 lines. Pick some starting point A and sort all other points Bi by the angle of the line going through points A, Bi. If there is a sequence of more than 7 collinear points, you’ve found one of the original lines going through A. Now you can exclude all points on this line from choosing them as possible starting points in the future. Note that there will be at least one point left on the optimal line even if you exclude all other points due to intersections between lines. This way you can solve the problem by having to consider less than 50 starting points.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.