463 - Polynomial Factorization

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

463 - Polynomial Factorization

Post by stubbscroll » Tue Jan 04, 2005 4:57 am

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
New poster
Posts: 4
Joined: Sun Dec 12, 2004 12:28 pm

Re: 463 Polynomial factorization, unsure about what to outpu

Post by totster » Tue Jan 04, 2005 6:26 pm

stubbscroll wrote: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
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Tue Jan 04, 2005 7:45 pm

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... :oops:

ata(TNU)
New poster
Posts: 2
Joined: Sat Jan 05, 2008 3:01 pm

Post by ata(TNU) » Tue Jan 08, 2008 11:40 am

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)
New poster
Posts: 2
Joined: Sat Jan 05, 2008 3:01 pm

Help with 463 please I get WA

Post by ata(TNU) » Fri Jan 11, 2008 10:44 am

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
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Re:

Post by stubbscroll » Sat May 09, 2009 10:05 pm

ata(TNU) wrote: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

Last edited by stubbscroll on Thu Jun 09, 2011 2:25 am, edited 1 time in total.

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Re: 463 Polynomial factorization, unsure about what to output

Post by stubbscroll » Sat May 09, 2009 10:20 pm

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
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 463 - Polynomial Factorization

Post by metaphysis » Sat Mar 25, 2017 3:09 am

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;
}

Post Reply

Return to “Volume 4 (400-499)”