10778 - Mathemagicland

[medv]

Why WA?

I read carefully the text of the problem:
1. first line contains two integers n and k.
2. All inputs/outputs will fit into a standard 32-bit signed integer.
3. extract the rational numbers in order of magnitude from the n-tuple

So the roots are rational and can be searched via full search.
If I have a0*x^n + a1*x^(n-1) +... + an, all rational roots p/q have
property: p divides an, q divides a0.

This is not clear:
Output all distinct solutions in lexicographical order, one in each line.
Should I output only distinct solutions? But sample output gives them.

Lexicographical order - what is it? It means 1 < 21 because 1 is less 2
lexicographicaly. But problem text clearly says that roots must be in non
descending order.

I tried a lot of tests, got right answers. Can you give me some tests?
Thanks.


#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int n,k,i,j,w;
int p[102];
int q1[102],q2[102];
int q1len, q2len, rt;
int root[102],temp;
double t;

double gorner(int degree,int n, int *c,double value)
{
if (!n) return c[degree];
else return value * gorner(degree,n-1,c,value) + c[degree-n];
}

int compare(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}

int factorize(int n,int *c)
{
int i,count = 0;
c[count++] = 1;
for(i=2;i<=(int)sqrt(n);i++)
{
if (n % i == 0)
{
c[count++] = i;
while(n % i == 0) n /= i;
}
}
if (n > 1) c[count++] = n;
return count;
}

int not_present(int v)
{
int i;
for(i=0;i<rt;i++)
if (root[i] == v) return 0;
return 1;
}

int main(void){
while(scanf("%d %d",&n,&k),n>0)
{
p[n] = k;
for(i=0;i<n;i++)
{
scanf("%d",&p[n-i-1]);
if (i %2 == 0) p[n-i-1] = -p[n-i-1];
}
rt = 0;
while(1)
{
t = gorner(n,n,p,0.0);
if (fabs(t) > 1e-8) break;
for(i=0;i<n;i++)
p[i] = p[i+1];
p[n--] = 0;
root[rt++] = 0;
}
w = rt;

q1len = factorize(abs(p[0]),q1);
q2len = factorize(k,q2);

for(i=0;i<q1len;i++)
for(j=0;j<q2len;j++)
{
t = gorner(n,n,p,1.0*q1[i]/q2[j]);
if (fabs(t) < 1e-8)
{
temp = k*q1[i]/q2[j];
if (not_present(temp)) root[rt++] = temp;
}
t = gorner(n,n,p,-1.0*q1[i]/q2[j]);
if (fabs(t) < 1e-8)
{
temp = -k*q1[i]/q2[j];
if (not_present(temp)) root[rt++] = temp;
}
}

temp = 1;
while(temp)
{
temp = 0;
for(i=0;i<n;i++)
p[i] = p[i+1]*(i+1);
p[n--] = 0;j=rt;
for(i=w;i<j;i++)
{
t = gorner(n,n,p,root[i]);
if (fabs(t) < 1e-8)
{
root[rt++] = root[i];
temp = 1;
}
}
}
if (rt > 0)
{
qsort(root,rt,sizeof(int),compare);
for(i=0;i<rt-1;i++)
printf("%d ",root[i]);
printf("%d\n",root[rt-1]);
} else printf("No solution.\n");
}
return 0;
}

[bugzpodder]

i'll look at that...

[bugzpodder]

This is not clear:
Output all distinct solutions in lexicographical order, one in each line.
Should I output only distinct solutions? But sample output gives them.

Lexicographical order - what is it? It means 1 < 21 because 1 is less 2
lexicographicaly. But problem text clearly says that roots must be in non
descending order.

I tried a lot of tests, got right answers. Can you give me some tests?
Thanks.

you want to output the numbers in smallest to largest order. there is only one solution. so dont mind that saying distinct
it means that since the roots are up to a permutation, then you should and if you output everything from small to large, they have the same output, so they are considered as the same solution. i'll run ur code against the IO to see whats wrong

[bugzpodder]

your program fails on a lot of test cases... I sent you a PM (actually sending u one right now)

[medv]

To bugzpodder:
I send you PM - I need your help.
I found some mistakes, but soon WA.

I need some tests where my program is wrong.

[medv]

I improved my program - but WA. I need some tests.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

long int n,k,i,j,w;
long int p[105];
long int q1[2002],q2[2002];
long int q1len, q2len, rt;
long int root[102],temp;
double t;

double gorner(long int degree,long int n, long int *c,double value)
{
if (!n) return c[degree];
else return value * gorner(degree,n-1,c,value) + c[degree-n];
}

int compare(const void *a, const void *b)
{
return *(long int *)a - *(long int *)b;
}

long int not_present(long int v,long int upper,long int *c)
{
long int i;
for(i=0;i<upper;i++)
if (c[i] == v) return 0;
return 1;
}

long int factorize(long int n,long int *c)
{
int ct,i,j,count = 0;
c[count++] = 1;
for(i=2;i<=(int)sqrt(n);i++)
{
while (n % i == 0)
{
ct = count;
for(j=0;j<ct;j++)
if (not_present(c[j]*i,ct,c))
c[count++] = c[j]*i;
n /= i;
}
}
if (n > 1)
{
ct = count;
for(j=0;j<ct;j++)
if (not_present(c[j]*n,ct,c))
c[count++] = c[j]*n;
}
return count;
}

int main(void){
while(scanf("%ld %ld",&n,&k),n>0)
{
p[n] = k;
for(i=0;i<n;i++)
{
scanf("%ld",&p[n-i-1]);
if (i %2 == 0) p[n-i-1] = -p[n-i-1];
}
rt = 0;
while(1)
{
t = gorner(n,n,p,0.0);
if (fabs(t) > 1e-9) break;
for(i=0;i<n;i++)
p[i] = p[i+1];
p[n--] = 0;
root[rt++] = 0;
}
w = rt;

q1len = factorize(abs(p[0]),q1);
qsort(q1,q1len,sizeof(long int),compare);
q2len = factorize(k,q2);
qsort(q2,q2len,sizeof(long int),compare);

for(i=0;i<q1len;i++)
for(j=0;j<q2len;j++)
{
t = gorner(n,n,p,1.0*q1[i]/q2[j]);
if (fabs(t) < 1e-9)
{
temp = k*q1[i]/q2[j];
if (not_present(temp,rt,root)) root[rt++] = temp;
}
t = gorner(n,n,p,-1.0*q1[i]/q2[j]);
if (fabs(t) < 1e-9)
{
temp = -k*q1[i]/q2[j];
if (not_present(temp,rt,root)) root[rt++] = temp;
}
}

temp = 1;
while(temp)
{
temp = 0;
for(i=0;i<n;i++)
p[i] = p[i+1]*(i+1);
p[n--] = 0;j=rt;
for(i=w;i<j;i++)
{
t = gorner(n,n,p,1.0*root[i]/k);
if (fabs(t) < 1e-9)
{
root[rt++] = root[i];
temp = 1;
}
}
}
if (rt > 0)
{
qsort(root,rt,sizeof(long int),compare);
for(i=0;i<rt-1;i++)
printf("%ld ",root[i]);
printf("%ld\n",root[rt-1]);
} else printf("No solution.\n");
printf("\n");
}
return 0;
}

[Cho]

After reading back and forth many times between the problem statement and this thread, finally (I think) I understand what the problem is.

Could someone (little joey? mf? ) verify my input/output?
10778.in
10778.out

[mf]

Well, this line in your output is clearly wrong: "-15 10 10 5". The numbers in the output must be sorted, check your sorting function.

There are quite a lot of other differences, mostly because your program has found fewer roots than mine. I'll send you my output by e-mail.

[Cho]

After my first WA, I change the output order to be in alphabetical order because of the phrase "lexicographical order" in the problem. That's why I output "-15 10 10 5" intead of "-15 5 10 10". There is also another bug in my code too.

My output is now matched with yours. But still WA

[mf]

It's said in the problem statement, that every solution must satisfy: kx_a1 <= kx_a2 <= ... <= kx_am.
That's why you should sort the roots numerically.

I've noticed that the judge's input contains at least one -2^31. If you're using signed 32-bit integers and going to negate this number, you'll get overflow.

Could you post your code here?

[Cho]

My code will fail with input with -2^31. Now I change to long long, but still couldn't AC. Here is my code:

Code: Select all

Removed after AC

[Edit:] New WA-code updated
[Edit2:] AC

[mf]

Here are some test cases:

Code: Select all

1 -159
897773344 
1 1000
2147483647
1 -1000
-2147483648
3 -1000
-2147483648 0 0
0

My output:

Code: Select all

897773344

2147483647

-2147483648

-2147483648 0 0

I think your problems are caused because you use floating point approximations.
Maybe you should try switching to bignums or modular arithmetic.

[Cho]

It turns out that I print %d instead of %lld and two more variables which I should declare them as long long. My code now can pass your test cases. Hmm.. if it's the floating point problem, then it's a bit painful to correct it.
Anyway, thx a lot for your help.

[Edit:] The work for changing everything from floating point to modular arithmetic is much less than what I expect. And the problem of my code is indeed from the floating point errors (although I couldn't construct a case which make the floting point code fails). Finally AC now. Thanks again.

[sclo]

I didn't use any modular arithmetic and floating point computation in my solution, but it is slower.