TCP - Editorial

@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

Did you find the roots of the given curve and then perform integration in blocks where function is monotonous?

I’ve submitted a lot of wrong solutions during the testing phase, some of them outputs negative values and didn’t get AC. May be that’s bacause of some wrong positive values. Anyway I will check checker.

1 Like

I used a very similar approach. I split the interval [0,T] into 5000 equal sub-intervals and I assumed that if the function has the same sign at both endpoints of a sub-interval then there is no root inside that interval - otherwise there is just one root. The reason for which I was quite sure that this would work was also the fact that the 4 given function values were integers, which made me assume that the roots of the function cannot be too close to each other.

2 Likes

This is the second version of the question i asked above… :stuck_out_tongue: However, I +1 for your statement “What’s correct in this code?”

I am having problem with precision …
After seeing @xellos0 solution that how he handled the precision I have changed my program . But still getting WA …Plz help !!
soln link CodeChef: Practical coding for everyone

So the correct way should have been fabs(a-b)/b<=epsilon. Right?

Yes, ‘b’ is in denominator.

@wittyceaser
can you please explain me the process of finding roots of the cubic polynomial and also tell me under which limits the intergration must be performed,thanks in advance!