PathSolving | Topcoder Archive

Problem Statement

You have been given polynomials x(t) and y(t) described by the int[]s xpoly and ypoly, respectively. Element i (0-based) of each int[] determines the the coefficient of the tⁱ term of the polynomial. Together, these polynomials describe a parameterized path through our space. Our space consists of all points (x,y) where x and y are integers between 0 and 10008, inclusive. At time t (t is any nonnegative integer) the aforementioned path is at the point (x(t),y(t)). All arithmetic in this problem is done modulo the prime 10009. We are looking for a non-zero polynomial p(x,y) such that every point (x',y') on the path gives p(x',y')=0. In other words, the image of the path is contained in the zero set of the polynomial. A polynomial in two variables (like p) takes the form

 p(x,y) = axⁱy^j + bx^ry^s + ... + cx^ty^u,

where the coefficients of each term are integers between 0 and 10008, inclusive, and the exponents are non-negative integers. The degree of such a polynomial is the maximum taken over the sum of the exponents in each term. For example, the degree of x²y³ + x⁴ + 4 is 5. Considering all potential polynomials p satisfying the properties above, return the smallest degree necessary. If no such polynomial exists, return -1.

Definition

Class:: PathSolving
Method:: minDegree
Parameters:: int[], int[]
Returns:: int
Method signature:: int minDegree(int[] xpoly, int[] ypoly)
(be sure your method is public)

Constraints

xpoly and ypoly will each contain between 1 and 11 elements, inclusive.
Each element of xpoly and ypoly will be between 0 and 10008, inclusive.

Examples

```
{1,2}
```
```
{2,3}
```
```
Returns: 1
```
Here the paths are x(t) = 1 + 2t and y(t) = 2 + 3t. The result is 1 due to the polynomial p(x,y) = 6673 + 6672y + x.
```
{2,3,4}
```
```
{0,2}
```
```
Returns: 2
```
The result is 2 due to the polynomial p(x,y) = 2 + 5006y + 10008x + y2.
```
{0,0}
```
```
{0,0,0}
```
```
Returns: 1
```
Here the result is 1 since p(x,y) = x works.
```
{1,0,0,0,3}
```
```
{0,0,1,0,1}
```
```
Returns: 2
```

{1,2,3,4,5,6,7,8,9,10}

{11,12,13,14,15,16,71}

Returns: 9

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.