You are not logged in. Please login at www.codechef.com to post your questions!

×

MSTONES - Editorial

PROBLEM LINKS

Practice
Contest

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.

This question is marked "community wiki".

asked 27 Nov '12, 11:51

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,359
×11
×3

question asked: 27 Nov '12, 11:51

question was seen: 1,534 times

last updated: 27 Nov '12, 11:51