Bisection Method
Moderator: Board moderators
Bisection Method
I've just used Bisection Method to solve 10341(Solve It) and 358(Don't Have a Cow, Dude).
I would like to know whether there are other problems which can be solved by this method.
Plz tell!!! Thx in advance.
I would like to know whether there are other problems which can be solved by this method.
Plz tell!!! Thx in advance.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
No, you don't need Bisection Method to solve Beavergnaw.
You can get the answer using just ONE formula!
Never mind, you can get ACC within 0.00.000 sec. with either method for sure!
You can get the answer using just ONE formula!
Never mind, you can get ACC within 0.00.000 sec. with either method for sure!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
I am a new in computational geometry and wanna solve the problems related to it. Can any one give me any tips how to make the initial approximation while solving any problems like 358 using bisection method or NR method.
In bisection method for a & b f(a) & f(b) should be of opposite sign.But how to determine a & b while implementing it in C???????
In bisection method for a & b f(a) & f(b) should be of opposite sign.But how to determine a & b while implementing it in C???????
Easy!Faizur wrote:In bisection method for a & b f(a) & f(b) should be of opposite sign.But how to determine a & b while implementing it in C???????
For instance, in Q358, first you should derive a formula f(x) = 0.
Then, you can clearly see that the function f(x) is strictly increasing.
Now choose the upper and lower limit. You may set 0 as the lower limit, and 2R as the upper limit.
Next, do the bisection!!
Finally, you get the answer easily!!!!!
By the way, what's "NR Method"??
Railway is quite interesting! I didn't use bisection, though...
Last edited by Observer on Wed Jun 18, 2003 9:15 am, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
You are correct Dominik Michniewski. NR is NewtonRaphson Method.
Another very good problem of Numerical method is The roots (10428). At first I tried it with Bisection method. But got either TLE or WA. Then I got accepted by applying NR method with Synthetic Division.
I am intersted to know the name of some other problems which should be solved numerically.
Another very good problem of Numerical method is The roots (10428). At first I tried it with Bisection method. But got either TLE or WA. Then I got accepted by applying NR method with Synthetic Division.
I am intersted to know the name of some other problems which should be solved numerically.
Hmm...... Multiple roots......... Let me think deeply......... Any hints??IIUC GOLD wrote:Another very good problem of Numerical method is The roots (10428). At first I tried it with Bisection method. But got either TLE or WA. Then I got accepted by applying NR method with Synthetic Division.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
i think nr method is preferrable and uses much less time than interval bisection methos.
because it's convergency is much greater than the former.
again nr method has some difficulty.
you must explicitely check whether it finds an infinity loop ro it finds roots in a very little distance.
this is the difficulties that is withdrawn by secant methos.
so i uses secant method. nr is also simpler to use.
because it's convergency is much greater than the former.
again nr method has some difficulty.
you must explicitely check whether it finds an infinity loop ro it finds roots in a very little distance.
this is the difficulties that is withdrawn by secant methos.
so i uses secant method. nr is also simpler to use.
"Everything should be made simple, but not always simpler"