Bisection Method

Let's talk about algorithms!

Moderator: Board moderators

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

hager
New poster
Posts: 10
Joined: Wed Jan 01, 2003 4:26 am
Location: Ume
The only one I can remember at the moment is 10297(Beavergnaw), but there are surely more of them. Anyway, it's a nice problem.

Best regards

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

IIUC GOLD
New poster
Posts: 19
Joined: Tue Jun 11, 2002 4:27 pm
Location: Bangladesh
Contact:
Railway (10263) is a good problem which can be solved by Bisection method.

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm
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 N-R 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???????

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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???????
Easy!

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 "N-R 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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Newton-Raphson Method .... second name I may write wrong ...

Best reagrds
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

IIUC GOLD
New poster
Posts: 19
Joined: Tue Jun 11, 2002 4:27 pm
Location: Bangladesh
Contact:
You are correct Dominik Michniewski. NR is Newton-Raphson 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.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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.
Hmm...... Multiple roots......... Let me think deeply......... Any hints??
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
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.
"Everything should be made simple, but not always simpler"

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
Location: Dhaka, Bangladesh
What will be condition for No Solution in the problem 10341 - Solve It.
I am using Bisection Method.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
actually, u can use a dfinite number of iteration.
after the no. of iteration if the value dnot converges then u can tell no soln.
but if it converges then it is the answer.
i think u 've go it.
--
anupam
"Everything should be made simple, but not always simpler"

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:
Yes! But be concious about the TOLERANCE !!!
We are all in a circular way, no advances, only moving and moving!

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
Location: Dhaka, Bangladesh
Thanks for the reply.

Thanks to all.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
well moni bhai,
i don't understand abt tollarence.
would u plz decribe a little bit more.
i used floor(x)==0 and ceil(x)==1 to check whether the ans is between 0 and 1.
then what is tollarence here>>?
"Everything should be made simple, but not always simpler"