Star Simulation: Difference between revisions
imported>Kmk21 Created page with "We know we can't compare every star to every other, this is too slow. The line about "no more than 100,000 being within k of each other" is a big hint. Just break our "univers..." |
imported>Kmk21 No edit summary |
||
| Line 1: | Line 1: | ||
We know we can't compare every star to every other, this is too slow. The line about "no more than 100,000 being within k of each other" is a big hint. Just break our "universe" up into KxKxK sized chunks. We only need to check points that are in the sectors within K of us. This is at max 8 sectors. The distribution requirements ensure that not every point compares against most other points (This has to do with the fact that only 400 points clustered tightly make 100,000 "pairs" of points (400^2/2 = 100k). So we can expect on average only 400 comparisons per point, which puts us at 40 million. | We know we can't compare every star to every other, this is too slow. The line about "no more than 100,000 being within k of each other" is a big hint. Just break our "universe" up into KxKxK sized chunks. We only need to check points that are in the sectors within K of us. This is at max 8 sectors. The distribution requirements ensure that not every point compares against most other points (This has to do with the fact that only 400 points clustered tightly make 100,000 "pairs" of points (400^2/2 = 100k). So we can expect on average only 400 comparisons per point, which puts us at 40 million. | ||
Dividing space up so that you can find only the subset of problems you need to solve is a very common technique. It is used in one of the convex hull algorithms. | |||
[[Category:ICPC Problems]] | [[Category:ICPC Problems]] | ||
[[Category:Midatl2013]] | [[Category:Midatl2013]] | ||
[[Category: | [[Category:Divide and Conquer]] | ||
[[Category:Algorithm Medium]] | [[Category:Algorithm Medium]] | ||
[[Category:Implementation Medium]] | [[Category:Implementation Medium]] | ||
Latest revision as of 06:30, 27 August 2016
We know we can't compare every star to every other, this is too slow. The line about "no more than 100,000 being within k of each other" is a big hint. Just break our "universe" up into KxKxK sized chunks. We only need to check points that are in the sectors within K of us. This is at max 8 sectors. The distribution requirements ensure that not every point compares against most other points (This has to do with the fact that only 400 points clustered tightly make 100,000 "pairs" of points (400^2/2 = 100k). So we can expect on average only 400 comparisons per point, which puts us at 40 million.
Dividing space up so that you can find only the subset of problems you need to solve is a very common technique. It is used in one of the convex hull algorithms.