Problem Link: contest, practice
Difficulty: Medium
Pre-requisites: Interpolation, Derivatives, Integrals
Problem:
We are given 4 different points of the 2D plot of some cubic polynomial function F(t) and number T. Our task is to calculate the square under F(t) on the interval [0…T].
Explanation:
This problem is a good example showing that mathematical analysis is not just a theoretical thing, but can be useful for solving problems from real life.
The problem can be divided into three subproblems. We’ll consider them separately.
Finding the formula of F(t)
The first subproblem is to determine the formula of F(t) using 5 points lying on its 2D plot. Since F(t) is a cubic polynomial, our task is to find coefficients A, B, C and D from the following representation of F(t) = At3 + Bt2 + Ct + D.
Each polynomial of N’th degree can be defined by (N + 1) different points lying on its 2D plot. In our case N = 3, so we need 4 points to rebuild F(t).
The process of finding a polynomial, that goes exactly through a given set of points called Polynomial interpolation. It seems to me like Wikipedia can explain this topic better than me, so here is a link.
Finding the roots of F(t)
OK, now have F(t) = At3 + Bt2 + Ct + D. Let’s find all points ti, such that F(ti) = 0.
There are a lot of ways of finding the roots of a cubic polynomial. Here is a link.
Nevertheless, let’s consider author’s approach.
Firstly, let’s find a derivative F’(t) = 3At2 + 2B + C and find its roots. Between that roots our function F(t) is monotonous, so we can use a binary search in order to find the roots of F.
Here is a small illustration, that is made for your better understanding.
A, B, C, D are the given points, F(t) is drawn as a black line, F’(t) is drawn as a blue line. You can make sure, that between the roots of F’(t) F(t) is monotonous.
It can be unclear a bit how to use a binary search there, so let’s also discuss this point a little bit more.
Let’s assume that we have function F(t)(any function, not necessarily the one from this problem), which is guaranteed to be monotonous on some interval [L…R](let’s also assume, that it’s increasing on this interval, F(L) < F(R)). We want to find a root of F(t) on the interval.
Three situations are possible here:
- F(R) < 0. In this case F(t) has no roots on the interval;
- F(L) > 0. In this case F(t) has no roots on the interval;
The third situation is the most interesting since we can declare, that there is a root of F(t).
Let’s find it with a help of a binary search!
Let’s X = (L + R) / 2.
- If F(X) == 0, then X is the root;
- If F(X) < 0, then the root lays on the interval [X…R];
- If F(X) > 0, then the root lays on the interval [L…X].
We can do about log2(1014) ~ 50 such iterations. If there are no root found, then we can assume, that L is a very good approximation of the root and use in our further calculations.
Finding the area under F(t) on the interval [0…T]
OK, now we have function F(t), have its roots.
Let’s calculate the answer!
Firstly, let’s calculate the answer on the intervals between the roots of F separately.
Also, let’s consider function G(t) = At4/4 + Bt3/3 + Ct2/2 + Dt. In mathematical analysis, function G is called a primitive(link) of function F.
Also, the square under F on some interval [L…R] equals to |G(R) - G(L)|. This approach is suitable only if function F is either F(t) ≤ 0 for each t from [L…R] or F(t) ≥ 0 for each t from [L…R].
Since we’re doing calculations on the intervals between the roots, we can use this approach.
The total complexity is O(log2(1014)) per testcase, but can be solved in O(1) as well.
Setter’s Solution: link
Tester’s Solution: link
