TCP - Editorial

editorial
, , ,
3

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

4

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
5

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
6

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
7

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

8

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
9

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…

10

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

11

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


[1]


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

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
13

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

14

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
15

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

16

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

17

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.

18

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…??

19

That’s called experience :stuck_out_tongue:

20

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.

21

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

22

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.