10524 - Matrix Reloaded

[longer]

The problem setter should work hard on something, at least English.

[mrbrett]

I've tried my code with all test inputs and outputs found in this board, but i still get WA.
What happens to this code? How can I get AC?

[c]#include <stdio.h>

# define MAX 100

int main()
{
float a[MAX][MAX],b[MAX][MAX],c[MAX][MAX];
float d,m;
int i,j,k,p,n=0;

while(scanf("%d",&n))
{
if(n==0) return(1);
if(n==1)
{
printf("Not possible\n");
p=0;
break;
}
p=1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%f",&a[j]);
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
b[j]=1;
else
b[j]=0;
}
}
if(a[0][0]==0)
{
for(j=0;j<n;j++)
{
c[0][j]=a[1][j];
a[1][j]=a[0][j];
a[0][j]=c[0][j];
c[0][j]=b[1][j];
b[1][j]=b[0][j];
b[0][j]=c[0][j];
}
}

for(i=0;i<n;i++)
{
d=a;
if(d==0)
{
printf("Not possible\n");
p=0;
break;
}
for(j=0;j<n;j++)
{
a[j]=a[j]/d;
b[j]=b[j]/d;
}
for(k=0;k<n;k++)
{
if(k!=i)
{
m=a[k];
for(j=0;j<n;j++)
{
a[k][j]=a[k][j]-(a[i][j]*m);
b[k][j]=b[k][j]-(b[i][j]*m);
}
}
}
}

if(p)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%.6f",b[i][j]);
printf(" ");
}
printf("\n");
}
printf("\n");
}
else printf("\n");
}
}[/c]

Thanks!

[Larry]

I have 2 suggestions:

use doubles, and use an epsilon when checking if it's zero..

[mrbrett]

what is an epsilon?

[Per]

Something small and squiggly with no legs, for example 1e-12.

When doing floating point computations, it is good practice to use an epsilon in comparisons, since floating point operations are (almost) never exact. For instance, in order to check if two doubles a and b are equal, one should check if |a-b| < epsilon, rather than if a==b.

[mrbrett]

Ok, i've tried with the epsilon and I still got WA. If I change the type from float to double, fails all. Even the sample tests are correct.

Here my sample inputs:

Code: Select all

2
1 2
2 1

2
1 2
2 1

4
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0 

10
9.5013 6.1543 0.5789 0.1527 8.3812 1.9343 4.9655 7.2711 7.9482 1.3652
2.3114 7.9194 3.5287 7.4679 0.1964 6.8222 8.9977 3.0929 9.5684 0.1176
6.0684 9.2181 8.1317 4.4510 6.8128 3.0276 8.2163 8.3850 5.2259 8.9390
4.8598 7.3821 0.0986 9.3181 3.7948 5.4167 6.4491 5.6807 8.8014 1.9914
8.9130 1.7627 1.3889 4.6599 8.3180 1.5087 8.1797 3.7041 1.7296 2.9872
7.6210 4.0571 2.0277 4.1865 5.0281 6.9790 6.6023 7.0274 9.7975 6.6144
4.5647 9.3547 1.9872 8.4622 7.0947 3.7837 3.4197 5.4657 2.7145 2.8441
0.1850 9.1690 6.0379 5.2515 4.2889 8.6001 2.8973 4.4488 2.5233 4.6922
8.2141 4.1027 2.7219 2.0265 3.0462 8.5366 3.4119 6.9457 8.7574 0.6478
4.4470 8.9365 1.9881 6.7214 1.8965 5.9356 5.3408 6.2131 7.3731 9.8833 

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1
5

0

Here my outputs for that samples:

Code: Select all

-0.333333 0.666667
0.666667 -0.333333

-0.333333 0.666667
0.666667 -0.333333

Not possible

-0.070885 0.190366 -0.064787 -0.466908 -0.007342 0.132556 0.393283 0.254180 0.106229 0.074244
0.106282 0.072758 -0.055644 -0.107017 0.006025 -0.143474 0.032887 0.017552 -0.003056 0.132946
-0.158503 0.248146 0.074397 -0.508077 -0.171241 0.390370 0.506519 -0.257355 0.004178 -0.179324
-0.158219 0.072117 0.018435 -0.126107 -0.073899 0.204099 0.305098 -0.170877 -0.001857 -0.091075
0.038540 0.060938 -0.058235 -0.168922 -0.065009 0.306328 0.203311 0.011262 -0.160097 -0.158063
0.026725 -0.086133 -0.081818 0.146694 0.111831 -0.137008 -0.228790 0.202612 0.059928 0.065387
0.111459 -0.174756 0.048315 0.512155 0.230113 -0.438042 -0.603086 0.271165 0.009040 0.107617
0.074352 -0.538201 0.230776 1.059829 0.164412 -0.692106 -0.874826 0.362629 0.179767 0.055162
-0.037257 0.248516 -0.040264 -0.435959 -0.229971 0.508425 0.460295 -0.241112 -0.128389 -0.153880
-0.027344 0.037008 -0.028874 -0.178656 -0.028273 0.168767 0.114784 -0.051992 -0.071996 0.058601

Not possible

Not possible

Any more idea?

[Larry]

Well,

Code: Select all

1 
5 

Should definitely be possible, right? =)

[mrbrett]

I've read on another thread that that case should be not possible.
I've tried with that case answering 0.200000, but still get WA.

[Larry]

Mine outputs 0.2, and I got AC..

[mrbrett]

Ok, I've changed that.
But what's the matter then?

[mrbrett]

Here is the status of my code now. With all the corrections suggested. But still get WA.

[c]#include <stdio.h>
#include <math.h>
#define MAX 100

int main()
{
double a[MAX][MAX],b[MAX][MAX],c[MAX][MAX];
double d,m;
int i,j,k,p,n=0;

while(scanf("%d",&n))
{
if(n==0) return(1);
p=1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%lf",&a[j]);
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
b[j]=1;
else
b[j]=0;
}
}
if(a[0][0]==0)
{
for(j=0;j<n;j++)
{
c[0][j]=a[1][j];
a[1][j]=a[0][j];
a[0][j]=c[0][j];
c[0][j]=b[1][j];
b[1][j]=b[0][j];
b[0][j]=c[0][j];
}
}

for(i=0;i<n;i++)
{
d=a;
if(fabs(d)<10e-12)
{
printf("Not possible\n");
p=0;
break;
}
for(j=0;j<n;j++)
{
a[j]=a[j]/d;
b[j]=b[j]/d;
}
for(k=0;k<n;k++)
{
if(k!=i)
{
m=a[k];
for(j=0;j<n;j++)
{
a[k][j]=a[k][j]-(a[i][j]*m);
b[k][j]=b[k][j]-(b[i][j]*m);
}
}
}
}

if(p)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%.6lf",b[i][j]);
printf(" ");
}
printf("\n");
}
printf("\n");
}
else printf("\n");
}
}[/c]

[dpitts]

What does no pivoting mean?

I've seen some posts that say it means that the output for

Code: Select all

4
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0

is "Not possible", but I don't see why it should be, or even how to test for this case. Maybe its because I'm tired right now. but thats still annoying. If you can find the inverse, then you can find the with swapping rows, than you can also solve it with only row additions and multiplications.

Hmm, I'm going to try something. Let you know if I make it AC.