Connection Status:
Competition Arena > QuadraticRoots

QuadraticRoots

TCO '03 Round 3 · 2003-10-07 · by brett1479

TCO '03 Round 3 · 2003-10-07 · by brett1479 · Brute Force, Simple Math
Class Name: QuadraticRoots
Return Type: int[]
Method Name: findRoots
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

A quadratic equation has the format ax^2 + bx + c = 0 where a != 0. To solve this equation the quadratic formula is used: 
x = (-b (+|-) sqrt(b^2 - 4ac)) / 2a ,
where (+|-) means plus or minus, sqrt means square root, and x is the solution.

Given a list of values for a, b and c your method will return a sorted int[] of all integer solutions to the corresponding quadratic equations. The sorted values should be in ascending order with no repeats. For example, if
    a = {1} ,
    b = {2,3} ,
and c = {2,1} ,
your method would have to solve the quadratic equations corresponding to all combinations of values from a, b and c. This would amount to solving: 
 x^2 + 2x + 2 = 0  (Solutions : not integers)
 x^2 + 2x + 1 = 0  (Solutions : -1)
 x^2 + 3x + 2 = 0  (Solutions : -2,-1)  
 x^2 + 3x + 1 = 0  (Solutions : not integers)  .
Notice that all combinations have been tried. The return value would be {-2,-1}.

Constraints

  • a, b, and c will each contain between 1 and 50 elements inclusive.
  • Each element of a will be nonzero, between -10000 and 10000 inclusive.
  • Each element of b and c will be between -10000 and 10000 inclusive.
  • The returned int[] will contain at most 100 elements.
Examples
0)
{1}
{2,3}
{2,1}
Returns: { -2,  -1 }

Example from above.

1)
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
{1}
{1}
Returns: { }

No roots here.

2)
{1}
{0}
{-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,-11,-12,-13,-14,-15,-16}
Returns: { -4,  -3,  -2,  -1,  1,  2,  3,  4 }
3)
{1,1,2,2,3,3,4,4}
{1,1,2,2,3,3,4,4}
{1,1,2,2,3,3,4,4}
Returns: { -3,  -2,  -1 }

Tons of repeats.

4)
{1,10000,-10000}
{0,1,10000,-10000}
{0,1,10000,-10000}
Returns: { -10000,  -100,  -1,  0,  1,  100,  10000 }

Submissions are judged against all 103 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class QuadraticRoots with a public method vector<int> findRoots(vector<int> a, vector<int> b, vector<int> c) · 103 test cases · 2 s / 256 MB per case

Submitting as anonymous