Parabola
TCO2020 EastAsia Qualification · 2020-09-24 · by misof
Problem Statement
Tom has made some measurements.
Their outcomes are given in the
From the nature of the thing Tom measured he expects that the data can be described by a special quadratic function. More precisely, he is looking for a quadratic function f(x) = A*x*x + B*x + C such that A, B, C are integers, A is in [1,50], and B is in [-50,50].
Given a function f, the badness of a point estimate at coordinate x is the absolute value of the difference between f(x) and Y[x]. The total badness of f is the sum of the badness of all point estimates (over all x that are valid indices into Y).
Find the function f with the smallest total badness. In case of a tie minimize A, in case of a tie minimize B, and if there is still a tie, minimize C as well.
Return the
Notes
- It can be shown that the answer is always well-defined and that for the optimal answer C always fits into a signed 32-bit integer variable.
- Note that the total badness of a function may overflow a signed 32-bit integer variable.
Constraints
- Y will have between 1 and 1,000 elements, inclusive.
- Each element of Y will be between -10^8 and 10^8, inclusive.
{0, 1, 4, 9, 16, 25, 36, 49}
Returns: {1, 0, 0 }
The parabola 1*x*x + 0*x + 0 is clearly the only perfect fit.
{10000, 10030, 10120, 10269, 10482, 10750, 11077, 11471}
Returns: {30, 0, 10000 }
This time there is some noise, but still obviously the best fit is the parabola 30*x*x + 0*x + 10000. This parabola has values 10000, 10030, 10120, 10270, 10480, 10750, 11080, 11470. Thus, the badness of the individual point estimates is 0, 0, 0, 1, 2, 0, 3, and 1, and hence the total badness of this parabola is 0+0+0+1+2+0+3+1 = 7.
{47}
Returns: {1, -50, 47 }
With just a single data point any parabola with C = Y[0] fits, so the one with the smallest A and B was picked.
{-10000, -9990, -9960, -9910, -9838, -9748, -9638, -9508}
Returns: {10, 0, -10000 }
The badness of the returned parabola is 0 + 0 + 0 + 0 + 2 + 2 + 2 + 2 = 8. The parabolas 10*x*x + (-9999) and 10*x*x + (-9998) also have the same badness as the returned parabola but their C is bigger.
{-123, 456, -78, 901234, -5678, 901, -234567}
Returns: {1, -50, 18 }
Submissions are judged against all 123 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Parabola with a public method vector<int> estimate(vector<int> Y) · 123 test cases · 2 s / 256 MB per case