input:
Code: Select all
65 36 -272 -56 187
Code: Select all
1 1
65 -29 -243 187
Code: Select all
5 2 -17
13 2 -11
Also, does the input contain cases where the answer is two polynomials of degree 2?
Moderator: Board moderators
Code: Select all
65 36 -272 -56 187
Code: Select all
1 1
65 -29 -243 187
Code: Select all
5 2 -17
13 2 -11
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 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:Here's the output from my program:Code: Select all
65 36 -272 -56 187
But here's another possible factorization, from my random test case generator:Code: Select all
1 1 65 -29 -243 187
However, I thought all polynomials should only have one unique factorization!?Code: Select all
5 2 -17 13 2 -11
Also, does the input contain cases where the answer is two polynomials of degree 2?
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).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.
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
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;
}