Problem Statement for ClassScores | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2005, TopCoder, Inc. All rights reserved. |




























Problem Statement for AutoLoan | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2005, TopCoder, Inc. All rights reserved. |





























Problem Statement for MissileTarget | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2005, TopCoder, Inc. All rights reserved. |
This is another problem that is fairly easily solved with a bit of grunt work to calculate out the desired values. Since we are looking for the lattice point that is closest to our best fit, our best bet is to first calculate the location of the actual best fit point (using floating point, that is), and then find the closest lattice point.
To find the best fit point, we one important observation: calculating the best fit x-coordinate and the best fit y-coordinate separately will give us our best fit point. Why? Since the scoring of a point as being best fit is based upon the sum of the squares of the distances from each of the points, we see that:
score = sum(d^2) = sum(sqrt((x – x0)^2 – (y – y0)^2)^2)
= sum((x – x0)^2 + (y – y0)^2)
= sum((x – x0)^2) + sum((y – y0)^2)
So, to minimize the score, it suffices to minimize each sum separately.
To minimize each sum, a ternary search works well. However, in this case, if you were inclined to do the mathematical gruntwork, then you found a nice shortcut. The average of the x-coordinates will give you the x-coordinate of the best fit point, and the same goes for the y-coordinates. (Why? Hint: Use calculus to prove where the minimum value is.)
Either way, once you have the location of the best fit point it's just simply a matter of finding the closest lattice point, and the easiest way to do this is by rounding. (Note the constraints were intended to prohibit the case where a point was equidistant from multiple lattice points.)