REALROOT - Real Roots


In this problem you are challenged to factor the real roots of polynomials.

You are rewarded points based on the number of testcases you solve.

Input

The first line contains the number of test cases, T.

The first line of each test case contains an integer N, the number of coeficients.

The second line contains the polynomial coeficients aN-1, ..., a1, a0 such that (P(x) = aN-1xN-1 + ... + a1x+ a0x0).

Output

The roots of the polynomial, in sorted order. That is all real numbers r0, r1, r2, ... such that P(r) = 0.

Constrains

  • T ≤ 20
  • N ≤ 20
  • All coeficients are in the inclusive range [-106,106]
  • The output precision must be at least 2 decimal digits
  • The roots must truly be real. No complex roots even if the imaginative part is very small.

Cases

  1. Same as the example
  2. ~3  random integer roots
  3. ~15 random integer roots
  4. ~10 Random interger coefficients
  5. ~10 Random floating point roots
  6. ~10 Random floating point coefficients
  7. Polynomials on the form p0=x, pk+1=(pk-ak)^2 e.g. ((x-3)^2-1)^2

Example

Input:
4
3
1 0 -2                 x2 - 2
3
1 0 1                  x2 + 1
4
-1 3 -3 1              -x3 + 3x2 - 3x + 1
7
1 -1 -9 13 8 -12 0     x6 - x5 - 9x4 + 13x3 + 8x2 - 12x
Output:
-1.414214 1.4142135    -sqrt(2), sqrt(2)
                       No real roots
1 1 1                  Triple root in x=1
-3 -1 0 1 2 2          Mixed integer roots

Notes

  1. All testcases are double checked using Mathematica with 30 digits of precision.
  2. Constrains are set such that most approaches should be fine using double working precision.

 

 

 

 


hide comments
Shashi Kant Prasad: 2014-06-12 20:50:21

@Mitch Schwartz: Thanks for help. I also think, handling multiple roots is important here.
Now, my main problem is guessing initial approx.s to the roots.

Last edit: 2013-04-20 08:47:15
Mitch Schwartz: 2014-06-12 20:50:21

@Shashi Kant Prasad: I think the 7th class is unclear, my assumption was that p_0=1 is a typo for p_0=x, and a recurrence is defined, e.g. if a=5 then p_1=(x-5)^2, p_2=((x-5)^2-5)^2, and any of these polynomials could be in the input if it meets the other constraints -- also, maybe "a" is supposed to be a_k such that e.g. ((x-5)^2-3)^2 is also possible (with a_0=5 and a_1=3). At any rate I think the main thing is to be able to handle multiple roots.

[Corrected, thanks -Thomas.]

Last edit: 2016-01-02 14:00:40
Shashi Kant Prasad: 2014-06-12 20:50:21

In case 7: Polynomials on the form p0=1, pk+1=(pk-a)^2, what does pk mean?(k-th derivative of p?) also Polynomials on the form p0=1, (pk-a)^2 is pk raised to power -square(a).
Anybody, the successful guys, clarify!

Robert Gerbicz: 2014-06-12 20:50:21

Thanks for the answers! Just observed that the points are multiple of 100/7, so we can get points after solving an input set, not for a single equation.
No problem.

Thomas Dybdahl Ahle: 2014-06-12 20:50:21

The judge is the standard SPOJ "Ignores FP rounding up to 10^-2"
I'm sorry if it gives any problems.

Congrats to Mitch for being the first to solve this. Using Laguerre's method.

Last edit: 2012-10-15 22:55:15
Mitch Schwartz: 2014-06-12 20:50:21

It seems the custom judge suppresses runtime errors and also TLE according to infinite loop code I submitted just now (which got 0 score instead of TLE). I'm not sure if the author did this on purpose to make debugging harder, or just overlooked it.

I did a test and didn't find any unexpected whitespace in the input, so it should be ok for Python.

2 or 2.000000001 or 2.0000000000000000000000001 are all ok.

Last edit: 2012-10-13 07:37:49
Robert Gerbicz: 2014-06-12 20:50:21

Is the input files totally deleted ?? A very simple

#include
#include
int main(){
assert(0);
return 0;
}
// for some reason here spoj window deleted stdio.h and assert.h words.

gives no runtime error. How this can happen?
Other: if the coefficients are integers and some solutions are also integers then should we print these as an integer, or do you accept if I print 2.000000001 instead of 2. Can I print say 28 digits after the decimal point for non-integer solutions?

I'm still getting AC with my python codes in 0 sec with perfect 0 point.

Last edit: 2012-10-12 23:46:09
Thomas Dybdahl Ahle: 2014-06-12 20:50:21

I reduced the output precision contrains, as some of the polynomials couldn't be evaluated to 6 digits using double precision.

Last edit: 2012-06-09 18:25:59
Thomas Dybdahl Ahle: 2014-06-12 20:50:21

Petar: Your solution misses certain duplicated roots.

Last edit: 2012-06-09 14:54:14
Thomas Dybdahl Ahle: 2014-06-12 20:50:21

Thank you, that was unclear. Hopefully it's better now.


Added by:Thomas Dybdahl Ahle
Date:2012-06-06
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64