10428  The Roots
Moderator: Board moderators

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
10428  The Roots
Can someone please link me to a site or something with good explanation on how to solve this? Thanks in advance!

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
Well, I don't know any link on it. But I'll try to explain how I did it.
The problem is veryvery beautiful and tricky. It was great to solve it during contest. 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!!
Well I tried my best to explain, but if it is still not clear  ask for the details.
Good luck!
Andrey.
The problem is veryvery beautiful and tricky. It was great to solve it during contest. 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!!
Well I tried my best to explain, but if it is still not clear  ask for the details.
Good luck!
Andrey.

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
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!
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!

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
For this problem, I use Newton method. The recurrence is as follows:
X(n) = X(n1)  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.
X(n) = X(n1)  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.
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.
My AC code outputs:
I set EPS = 1e8
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

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
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..
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..
Check out http://www.algorithmist.com !

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
Anyone got any more test cases? I've recoded this and somehow I cannot get AC. (I can't find my original code..)
Thanks.
Thanks.
Check out http://www.algorithmist.com !
There is a method to solve this problem without doing any bisections.
A modified form of newton method called DurandKerner 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:
The algorithm terminates when abs(r(i,j)r(i,j1)) is sufficiently small.
A modified form of newton method called DurandKerner 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,j1)  f(r(p,j1)) / product(r(p,j1)r(k,j1) where k!=p)
}

 Experienced poster
 Posts: 109
 Joined: Sat Jun 23, 2007 9:53 pm
 Location: Brest, BELARUS
 Contact:
Re: 10428  The Roots
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
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
my profile
Re: 10428  The Roots
The problem is really beatiful. And so beatiful is its solution.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 veryvery beautiful and tricky. It was great to solve it during contest. 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!!
Well I tried my best to explain, but if it is still not clear  ask for the details.
Good luck!
Andrey.
I got accepted by recursive method and NR 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?
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10428  The Roots
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.
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!