10428 - The Roots

[Larry]

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

[Andrey Mokhov]

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

[Larry]

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]

One more thing: problemsetter says that infinity=25!

Andrey.

[erfan]

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

[DemonCris]

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]

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

[daveon]

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]

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]

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]

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]

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

[lighted]

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. 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 really beatiful. And so beatiful is its solution.
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?

[brianfry713]

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.