TCP - Editorial

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) < ). We want to find a root of F(t) on the interval.

Three situations are possible here:

  • < 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® - 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

6 Likes

This one was great, thank you setter. Ok I didn’t realize that current speed can be < 0, but anyway, perfect problem :wink:

1 Like

We can use numerical integration technique known as “Simpson’s Rule” integral (|F(t)|),t=0…T as well.

i simply tried solution of equation using matrix method but i dont know why this one was giving WAs. what’s wrong with that approach.

need help

http://www.codechef.com/viewsolution/3785815 here is my solution link

i tried to find the values of A,B,C,D using this equation X=inv(A)*B then use the values of A,B,C,D to find the answer.

2 Likes

My approach for finding the roots was to try all intervals [t,t+1] and in case F(t) has a different sign than F(t+1), bin-search the root starting from that interval. Making integer data that fails this approach was supposed to be hard, and it really turned out that way - first submit AC.

Also, what do you mean by “square under F”? Both the geometrical figure and second power don’t make any sense in this context!

5 Likes

Sometimes it’s really hard to come up with ALL tricky ideas in order to make tests against them. :wink:

It might actually be impossible or nearly impossible for integer data, because you can’t choose the roots of the polynomial arbitrarily and just compute its values for randomly chosen times. If there were decimals velocities on the input, though, it’d be easy. Not like it changes much, because Newton’s method is also simple, but why bother making a more complicated solution when you can bet a simple one will pass? :smiley:

1 Like

I exactly used the same but guess lacked somewhere in the implementation. http://discuss.codechef.com/questions/41512/was-my-approach-correct-for-travelling-chef-problem (However closed).

That is much the way given in editorial… However m still trying understanding completely… :stuck_out_tongue:

I was about to implement the same idea but the very fact that F(t) and F(t+1) may have the same sign and yet there may be a root of F(x) in (t,t+1) stopped me from doing it. But yes the fact that A, B, C and D are integers makes it difficult to make such a case.

If F(X)<0 for X= (L+R)/2, that means F(X) lies below the x-axis, and thus for some x’, F(x’) can be zero in the interval (L,X). Then how the statement “If F(X) < 0, then the root lays on the interval [X…R];” is true…??

That’s called experience :stuck_out_tongue:

In that topic we are not discussing our global problem. “F(t)(any function, not necessarily the one from this problem)”. I’m just explaining how to use a binary search to find the roots of any monotonous function.

@Xellos did you also attend to IPhO and won gold there: http://www.ipho2011.org/contents/gold_medals

If F(X) < 0, then the root lays on the interval [X…R] is true if F(L)<F® as written in the editorial but if taken opposite i.e if F(L)>F®, then root will lie in the interval (L,X)as we can see in the graph(where it is monotonous). That probably confused me in beginning.

Yeah I tried the exact same thing. Failed on the second test case provided. I can’t figure out why.

Yeah I did. It was with a lot of luck, though - I had solved Lagrange points earlier, and that was the hardest problem. It’d be different now.

1 Like

@Xellos, appreciate your help bro. i see you posting solutions to difficult problems on CF. would love to see your solutions to TC as well. btw, we are happy to see such bright coders among us, gold on both IPhO & IOI, just fantastic.

There is an evident mistake that you are actually calculating the displacement and not the distance covered till time T. You need to find the distance which, in the second test case, will not be zero while the displacement at t=8 is zero.

1 Like

Now there is a serious problem in the checker of this problem , as printing any negative value gives you AC . As you can see from the solution I have submitted in the Practice Section. http://www.codechef.com/viewsolution/3786010 . I think the checker is not handling correctly the negative values . The Idea to submit such a solution I got was from this submission done during the contest http://www.codechef.com/viewsolution/3784470 , which does not even solve the Sample Testcases and still got Accepted .

7 Likes
//