10524 - Matrix Reloaded

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

Moderator: Board moderators

longer
New poster
Posts: 2
Joined: Thu Nov 06, 2003 9:44 am

This is simply stupid

Post by longer » Fri Nov 07, 2003 10:11 am

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

mrbrett
New poster
Posts: 6
Joined: Thu Mar 11, 2004 6:28 pm

10524 -Matriz Reloaded WA :(

Post by mrbrett » Thu Mar 11, 2004 6:31 pm

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Mar 11, 2004 7:18 pm

I have 2 suggestions:

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

mrbrett
New poster
Posts: 6
Joined: Thu Mar 11, 2004 6:28 pm

Post by mrbrett » Thu Mar 11, 2004 9:37 pm

what is an epsilon?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Fri Mar 12, 2004 7:17 pm

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
New poster
Posts: 6
Joined: Thu Mar 11, 2004 6:28 pm

Post by mrbrett » Tue Mar 16, 2004 2:06 am

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Mar 16, 2004 2:15 am

Well,

Code: Select all

1 
5 
Should definitely be possible, right? =)

mrbrett
New poster
Posts: 6
Joined: Thu Mar 11, 2004 6:28 pm

Post by mrbrett » Tue Mar 16, 2004 12:10 pm

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Mar 16, 2004 6:04 pm

Mine outputs 0.2, and I got AC..

mrbrett
New poster
Posts: 6
Joined: Thu Mar 11, 2004 6:28 pm

Post by mrbrett » Tue Mar 16, 2004 10:01 pm

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

mrbrett
New poster
Posts: 6
Joined: Thu Mar 11, 2004 6:28 pm

Post by mrbrett » Wed Mar 24, 2004 2:50 pm

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
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

10524

Post by dpitts » Wed Aug 04, 2004 11:19 am

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.

Post Reply

Return to “Volume 105 (10500-10599)”