463 - Polynomial Factorization

[stubbscroll]

Hi, I'm uncertain on what to output for this problem, as I seem to get several possible outputs for some inputs... My program's method is to first find the roots of the degree 4 polynomial. If no roots are found, I use trial division to see if I can find a degree 2 factor. I get a TLE verdict, because my trial division routine is too slow for large coefficients... Could anyone with AC (any of you two) or anyone fluent in polynomial factorization please tell me what the output is supposed to be for this input:

input:

Code: Select all

65 36 -272 -56 187

Here's the output from my program:

Code: Select all

1 1
65 -29 -243 187

But here's another possible factorization, from my random test case generator:

Code: Select all

5 2 -17
13 2 -11

However, I thought all polynomials should only have one unique factorization!?

Also, does the input contain cases where the answer is two polynomials of degree 2?

[totster]

Hi, I'm uncertain on what to output for this problem, as I seem to get several possible outputs for some inputs... My program's method is to first find the roots of the degree 4 polynomial. If no roots are found, I use trial division to see if I can find a degree 2 factor. I get a TLE verdict, because my trial division routine is too slow for large coefficients... Could anyone with AC (any of you two) or anyone fluent in polynomial factorization please tell me what the output is supposed to be for this input:

input:

Code: Select all

65 36 -272 -56 187

Here's the output from my program:

Code: Select all

1 1
65 -29 -243 187

But here's another possible factorization, from my random test case generator:

Code: Select all

5 2 -17
13 2 -11

However, I thought all polynomials should only have one unique factorization!?

Also, does the input contain cases where the answer is two polynomials of degree 2?

The polynomial 13x^2+2x-11 can still be factored into (x+1)(13x-11). In turn your output is incorrect in that 65x^3-29x-243x+187 can still be factored into (13x-11)(5x^2+2x-17).

[stubbscroll]

Thanks for the answer. There's obviously something very wrong with the root extraction routine, I'll check it again. But while doing all my calculations on paper I should have seen that (x+1) was a factor of 13x^2+2x-11...

[ata(TNU)]

Could you please tell me how to find roots? Because, my prog is kinda good, but gets WA. If someone would give good test cases to check my prog, I'll appreciate it. Please, help me, someone with AC.

[ata(TNU)]

Could you please tell me how to find roots? Because, my prog is kinda good, but gets WA. If someone would give good test cases to check my prog, I'll appreciate it. Please, help me, someone with AC.

[stubbscroll]

Could you please tell me how to find roots? Because, my prog is kinda good, but gets WA. If someone would give good test cases to check my prog, I'll appreciate it. Please, help me, someone with AC.

For monic polynomials a_0 + a_1x + ... + x^n, all roots will divide a_0. The input contains non-monic polynomials, so for all roots x, a_4*x divides a_0 (I think).

However, the factors can be two polynomials of degree two:

a_0 + a_1x + a_2x^2 + a^3x^3 + a_4x^4 = (c+bx+ax^2)(f+ex+dx^2) = ad x^4 + (ae+bd) x^3 + (af+be+cd) x^2 + (bf+ce) x + cf

To find these, do a somewhat clever brute force on the a,b,c,d,e,f values. We have that a_4 =ad, a_3 = ae+bd etc.

Here's a little dataset containing only degree 2 factors:

Code: Select all

493 172 -860 -151 58
69 -688 336 -855 58
25 120 13 -292 69
253 -182 25 -156 119
377 154 -873 -494 161
841 -116 -21 110 -121
391 195 866 179 437
69 431 -192 -237 65
377 792 77 -336 65
145 -552 -407 -92 21
361 -285 -126 137 -33
55 -42 -425 -32 21
77 368 113 360 -323
6 109 398 -888 299
10 21 -86 176 -21
161 646 -459 -460 187
115 151 278 -241 -551
667 -956 278 -73 6
46 157 397 -129 -247
221 -213 -806 379 667
87 526 369 -42 -49
21 -170 -5 314 65
187 118 282 41 -34
323 -175 -952 273 667
133 -480 667 -346 51
437 624 143 -126 -49
33 208 272 -195 -46
323 -91 -140 19 15
323 -23 151 -17 14
493 468 -405 -346 -57
39 -134 -240 517 38
299 7 294 -65 -119
115 -486 -61 -56 -667
377 584 -133 258 -437
38 -541 -410 -926 -493

Code: Select all

17 3 -29
29 5 -2

3 -29 2
23 -7 29

5 11 -3
5 13 -23

11 -17 7
23 19 17

13 -5 -23
29 23 -7

29 -7 11
29 3 -11

17 7 23
23 2 19

3 19 -5
23 -2 -13

13 17 -5
29 23 -13

5 -23 3
29 23 7

19 -13 3
19 -2 -11

5 -17 3
11 29 7

7 29 -19
11 7 17

2 17 -23
3 29 -13

2 -5 7
5 23 -3

7 29 -11
23 -3 -17

5 7 19
23 -2 -29

23 -29 3
29 -5 2

2 7 19
23 -2 -13

13 2 -23
17 -19 -29

3 17 7
29 11 -7

3 -23 -5
7 -3 -13

11 5 17
17 3 -2

17 -11 -23
19 2 -29

7 -19 17
19 -17 3

19 23 7
23 5 -7

3 11 2
11 29 -23

17 -3 -5
19 -2 -3

17 -3 2
19 2 7

17 5 -19
29 19 3

3 -17 19
13 29 2

13 2 17
23 -3 -7

5 -17 -23
23 -19 29

13 17 -19
29 7 23

2 -29 -17
19 5 29

[stubbscroll]

And now it's time to ask for help again.

I believe that my algorithm is correct, but I haven't been able to get accepted on this problem yet, even after all these years. My algorithm is based on what I wrote in my previous post. Here's an outline:

For each input a_4 x^4 + a_3 x^3 + a_2 x^2 + a_1 x + a_0:
- First, remove all roots x=0.
- Do a search for all the roots: For all integers a,b satisfying a|a_4 and b|a_0, check if b/a is a root.
- If no roots are found, search for factors of degree 2, by doing brute force on coefficients.

Could anyone post either hard cases (with either non-obvious sorting of factors or other tricky stuff), or some huge random datasets accompanied with correct answers (or point out a flaw in my algorithm)? Are 64-bits signed integers enough for intermediate calculations? I use doubles when testing whether a candidate is a root, by the way.

[metaphysis]

Test data generator:

Code: Select all

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_CASES = 100, DEGREE = 4, BASE = 50;

struct polynomial
{
    vector<int> coefficients;

    polynomial() {}

    polynomial(int a1, int a0)
    {
        coefficients.clear();
        coefficients.push_back(a1);
        coefficients.push_back(a0);
    }
    
    bool operator<(const polynomial &poly) const
    {
        if (coefficients.size() != poly.coefficients.size())
            return coefficients.size() < poly.coefficients.size();

        for (int i = 0; i < coefficients.size(); i++)
            if (coefficients[i] != poly.coefficients[i])
                return coefficients[i] < poly.coefficients[i];
    }
};

polynomial multiply(polynomial p1, polynomial p2)
{
    polynomial r;
    r.coefficients.assign(p1.coefficients.size() + p2.coefficients.size() - 1, 0);
    for (int i = 0; i < p1.coefficients.size(); i++)
        for (int j = 0; j < p2.coefficients.size(); j++)
            r.coefficients[i + j] += p1.coefficients[i] * p2.coefficients[j];
    return r;
}

int main(int argc, char *argv[])
{
    srand(time(NULL));

    for (int c = 1; c <= MAX_CASES; c++)
    {
        polynomial poly;
        poly.coefficients.push_back(1);

        //vector<polynomial> answer;
        for (int i = 1; i <= DEGREE; i++)
        {
            int a = rand() % BASE + 1;
            int b = rand() % BASE;
            
            if (rand() % 2 == 1) b *= (-1);
            
            poly = multiply(poly, polynomial{a, b});
            //answer.push_back(polynomial{a, b});
        }
        
        for (int i = 0; i < poly.coefficients.size(); i++)
        {
            if (i > 0) cout << ' ';
            cout << poly.coefficients[i];
        }
        cout << '\n';
        
        //sort(answer.begin(), answer.end());
        
        //for (int i = 0; i < answer.size(); i++)
        //{
        //    for (int j = 0; j < answer[i].coefficients.size(); j++)
        //    {
        //        if (j > 0) cout << ' ';
        //        cout << answer[i].coefficients[j];
        //    }
        //    cout << '\n';
        //}
        //cout << '\n';
    }
    
    return 0;
}