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) < 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

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:

2 Likes

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

CodeChef: Practical coding for everyone 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

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. CodeChef: Practical coding for everyone . 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 CodeChef: Practical coding for everyone , which does not even solve the Sample Testcases and still got Accepted .

7 Likes

Hi,

I tried solving the problem using the old school linear equation approach and finding the values of the constants a,b,c,d.The program executes well for the first test case but gives wrong answer for the second one,Can anyone advise where iam going wrong,PFB the link for my solution to the travelling chef problem
http://www.codechef.com/viewsolution/3785230

How can the code be accepted if we just print any negative value. Here is the link:
http://www.codechef.com/viewsolution/3786107

4 Likes

Can anyone tell me why my solution is wrong.

After finding the constants . I am running a loop from 1 to T and in each loop I am finding the value of integration in range i-1 to i and adding the absolute sum in the answer . it is giving correct answer for the sample testcases.

My solution CodeChef: Practical coding for everyone

Thankyou…

Can someone please explain this code for the above problem CodeChef: Practical coding for everyone
What’s happening in this code…??

What’s correct in this code??? Why is it giving AC???


[1]


  [1]: http://www.codechef.com/viewsolution/3786836

The judge has been fixed and the submissions in practice section have been rejudged. The error occurred because I assumed that in the judge - first file was correct file and the second file was the user output. Turns out I was wrong.

So while calculating relative error, I was using this -
fabs(a-b)/a<=epsilon

Now since ‘a’ is negative (user output), the LHS will always be less than RHS. And hence negative solution got accepted.

Excuse me for my lack of knowledge.

3 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. Was my approach correct for Travelling Chef problem? - general - CodeChef Discuss (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.