Editorial for GFSSOC '15 Fall S3 - System(0);


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

We will talk about the more "observatory" solution. Since the problem statement specifically stated that the polynomial had only one real root, and NO imaginary roots, the polynomial can be thought of as having N equal roots.

A specific example would be a quadratic like 4x^2 + 4x + 1. It has one real root which is x = -0.5, more elegantly written as (2x + 1) = 0. Quadratics however always have "two" roots, but in this special case the other root is also (2x + 1) = 0, so we can rewrite it as (2x + 1)^2. A better way to look at 4x^2 + 4x + 1 (which will help us solve the general case) is factoring out the 4 first. That leaves us with 4(x^2 + x + 0.25). (x^2 + x + 0.25) is still a perfect square, and when we factor it we get 4(x + 0.5)^2. This is the exact same thing (you can check by expanding it out) as the form we had before, but it gives us the x intercept right away since the coefficient does not matter anymore. When you do 4(x + 0.5)^2 = 0, we can square root both sides, and then divide by 4 which leaves us with x + 0.5 = 0, or x = -0.5.

Now if we take a general polynomial that has, as we said before, N equal roots, we can factor it similarly. Let the leading coefficient of the polynomial be a, and the root itself be r. We then get a(x - r)^n as the factored form. The root is just r! How do we get this factored form from the expanded form? If we expand a(x - r)^n using binomial expansion, we get a(x - r)^n = a(x^n + n(-r)x^{n - 1} + \dots + (-r)^n) = ax^n + an(-r)x^{n - 1} + \dots + a(-r)^n.

The coefficient of the last term of our expanded form is a(-r)^n, so we just need to divide the last coefficient by the first coefficient to isolate -r, and then take the nth root (this gives us -r, multiply by -1 to get r)! There is still one more thing to consider. Any variable to the even power has two solutions (plus and minus), while odd powers only result in one solution. When we take the nth root of (-r)^n, we have two cases. If n is odd, that means our root will be r, so we are done. HOWEVER, if n is even, we either have r or -r. IF the root itself is positive, like x = 5, then in factored form it will be (x - 5)^n. This means the expanded form will be alternating in signs (expand it out by hand to see what we mean!). This is our key to finding whether we should take -r or r. Just look at the last two terms. If they have DIFFERENT signs, that means that our original root was positive, so we output |r|. If they have the SAME signs, that means that our original root was negative, so we output -|r| instead.

Difficult to explain, easy to code!

Cooler math-y solution by Timothy Li: The answer is -\dfrac{1}{n} \times \dfrac{c_n}{c_{n-1}}.


Comments

There are no comments at the moment.