10428 - The Roots

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

10428 - The Roots

Post by Larry » Mon Jan 20, 2003 1:31 am

Can someone please link me to a site or something with good explanation on how to solve this? Thanks in advance! :)

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Sun Jan 26, 2003 10:19 am

Well, I don't know any link on it. But I'll try to explain how I did it.

The problem is very-very beautiful and tricky. It was great to solve it during contest. :P I noticed that we can find roots usind binary search, but we have to know intervals to search within! So the problem is to find the intervals. But we can do it if we will find the roots of derivative function. I mean roots of function f(x) are strictly between the roots of function f'(x). So it's some recurse! Nice!! 8)

Well I tried my best to explain, but if it is still not clear - ask for the details.

Good luck!
Andrey.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Jan 26, 2003 11:40 am

Ah, since N is 5, we find zeroes for f'(x), which in term, we find for f''(x)... until it hits a constant?

So let me get it straight:
for, say, x^2 - x + 100
we find f'(x), which is
2x - 1, then
we know it's zero at 1/2.. what do we do with this information? Binary search between 1/2 and infinity, and 1/2 and negative infinity?

Hrmm, I will try that tomorrow morning.. thanks!

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Mon Jan 27, 2003 8:12 am

One more thing: problemsetter says that infinity=25! :wink:

Andrey.

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

Post by erfan » Tue Apr 29, 2003 2:11 pm

i solve it as above method but WA.
Can anyone help me by some sample input output........ :lol:

User avatar
DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

Post by DemonCris » Thu Jul 31, 2003 8:47 am

For this problem, I use Newton method. The recurrence is as follows:

X(n) = X(n-1) - f( X(n) ) / f ' ( X(n) )

Therefore, I take every integer point in the range [-25, 25] to the recurrenece above to
get the approximation root. The iteration for one root is 20.

However, I think there is a problem, such as the number of root we found is not equal to
the input N, since if one root is 5.0012, we may find out 5.0011 and 5.0012.

I don't know how to handle this problem, please give me some hints. thank you.

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Thu Mar 10, 2005 2:26 am

So I wrote up a solution involving finding the roots of f' and then binary searching within those, but still get WA. Can anyone give me the output for these cases?
5 1 -70.511 1760.474617 -18012.337703009 60153.7853143281 -2436.14759274839
5 1 -107.986 4547.329316 -92955.399977144 918279.594779019 -3494904.34870324
5 1 -83.919 2646.66805 -38725.982206182 259141.252935141 -626567.937293735
5 1 -25.691 227.677493 -864.724329097 1311.16601295377 -460.799641539289
5 1 -51.342 679.106495 -2140.17242133 850.704629318064 -82.4627336639993
5 1 -88.132 3087.772527 -53711.314857152 463360.293973696 -1583739.40565588
5 1 -55.351 1103.621635 -9620.329256565 34643.1212240194 -37695.272277015
5 1 -98.807 3813.910377 -71597.772962341 650121.591477599 -2265391.53420778
5 1 -131.842 6888.996766 -178121.244449796 2275799.793536 -11475722.9226947
5 1 -62.637 1383.765019 -13727.493950787 62460.6093984407 -105661.95947089
2 1 4 4
0
I'm always willing to help, if you do the same.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Sun Jan 01, 2006 11:20 pm

My AC code outputs:

Code: Select all

Equation 1: 0.0410 6.3340 18.4670 19.1690 19.1690
Equation 2: 11.4780 15.7240 15.7240 24.4640 24.4640
Equation 3: 5.7050 9.9610 16.8270 16.8270 23.2810
Equation 4: 0.4910 2.9950 4.8270 5.4360 11.9420
Equation 5: 0.1530 0.2920 3.9020 3.9020 14.6040
Equation 6: 12.3820 17.4210 18.7160 19.7180 19.8950
Equation 7: 1.8690 5.4470 11.5380 14.7710 21.7260
Equation 8: 9.8940 17.0350 19.9120 25.6670 25.6670
Equation 9: 17.6730 17.6730 17.6730 23.8110 23.8110
Equation 10: 4.6640 6.8680 7.7110 15.1410 15.1410
Equation 11: -2.0001 -1.9999
I set EPS = 1e-8

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Jun 16, 2006 1:17 am

I expanded the infinities -

Equation 1: 0.0410 6.3340 18.4670 19.1690 26.5000
Equation 2: 11.4780 15.7240 24.4640 26.9620 29.3580
Equation 3: 5.7050 9.9610 16.8270 23.2810 28.1450
Equation 4: 0.4910 2.9950 4.8270 5.4360 11.9420
Equation 5: 0.1530 0.2920 3.9020 14.6040 32.3910
Equation 6: 12.3820 17.4210 18.7160 19.7180 19.8950
Equation 7: 1.8690 5.4470 11.5380 14.7710 21.7260
Equation 8: 9.8940 17.0350 19.9120 25.6670 26.2990
Equation 9: 17.6730 23.8110 28.7030 30.3330
Equation 10: 4.6640 6.8680 7.7110 15.1410 28.2530
Equation 11: -2.0000 -2.0000

So note that some answers in the one given above wasn't in the range..

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Sep 08, 2006 10:03 pm

Anyone got any more test cases? I've recoded this and somehow I cannot get AC. (I can't find my original code..)

Thanks.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sat Nov 04, 2006 5:52 am

There is a method to solve this problem without doing any bisections.
A modified form of newton method called Durand-Kerner or Weierstrass method can solve it using complex number arithmetic.
Just google it.
The main idea is this: let f be the polynomial, let r(p,j) be the p'th root found at j'th iteration, then
Let r(p,0) be (0.4+0.9i)^p

For each iteration, do the following:

Code: Select all

for p=1 to n do {
  r(p,j) = r(p,j-1) - f(r(p,j-1)) / product(r(p,j-1)-r(k,j-1) where k!=p)
} 
The algorithm terminates when abs(r(i,j)-r(i,j-1)) is sufficiently small.

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 10428 - The Roots

Post by andysoft » Wed Jul 23, 2008 2:18 pm

Can anyone who got Accepted give me some more test cases.

I was doing the binary search method as described in 2nd post: I recursively found roots of derivative of each function and I searched roots of function with binary search. And got WA... Any help/hint on this method? Thanx in advance
Now I lay me down to sleep...
my profile

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10428 - The Roots

Post by lighted » Mon Aug 04, 2014 6:51 pm

Andrey Mokhov wrote:Well, I don't know any link on it. But I'll try to explain how I did it.

The problem is very-very beautiful and tricky. It was great to solve it during contest. :P I noticed that we can find roots usind binary search, but we have to know intervals to search within! So the problem is to find the intervals. But we can do it if we will find the roots of derivative function. I mean roots of function f(x) are strictly between the roots of function f'(x). So it's some recurse! Nice!! 8)

Well I tried my best to explain, but if it is still not clear - ask for the details.

Good luck!
Andrey.
The problem is really beatiful. And so beatiful is its solution. :P
I got accepted by recursive method and N-R method but both solutions doesn't work properly with equal roots. :-?
If there are two equal roots they find that root only once. What i am missing? :roll:
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10428 - The Roots

Post by brianfry713 » Tue Aug 05, 2014 3:11 am

From the problem statement:
You can assume that a polynomial equation of degree n should have n real roots and all the roots are strictly different.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 104 (10400-10499)”