Editorial for GFSSOC '15 Fall S3 - System(0);
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 equal roots.
A specific example would be a quadratic like . It has one real root which is , more elegantly written as . Quadratics however always have "two" roots, but in this special case the other root is also , so we can rewrite it as . A better way to look at (which will help us solve the general case) is factoring out the first. That leaves us with . is still a perfect square, and when we factor it we get . This is the exact same thing (you can check by expanding it out) as the form we had before, but it gives us the intercept right away since the coefficient does not matter anymore. When you do , we can square root both sides, and then divide by which leaves us with , or .
Now if we take a general polynomial that has, as we said before, equal roots, we can factor it similarly. Let the leading coefficient of the polynomial be , and the root itself be . We then get as the factored form. The root is just ! How do we get this factored form from the expanded form? If we expand using binomial expansion, we get .
The coefficient of the last term of our expanded form is , so we just need to divide the last coefficient by the first coefficient to isolate , and then take the th root (this gives us , multiply by to get )! 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 th root of , we have two cases. If is odd, that means our root will be , so we are done. HOWEVER, if is even, we either have or . IF the root itself is positive, like , then in factored form it will be . 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 or . Just look at the last two terms. If they have DIFFERENT signs, that means that our original root was positive, so we output . If they have the SAME signs, that means that our original root was negative, so we output instead.
Difficult to explain, easy to code!
Cooler math-y solution by Timothy Li: The answer is .
Comments