3292  Matrissor (From Dhaka 20052006)
Moderator: Board moderators
3292  Matrissor (From Dhaka 20052006)
I tried to solve this problem using Memoization. Simply partition the given set of matrix in two and see if it is possible to evaluate the subsets. Or else partion the set(s) that can not be evaluated and the process is recursive. Then consider the partition that requires minimum number of steps.
But I got Wrong Answer. Could some one verify whether my method is correct.
But I got Wrong Answer. Could some one verify whether my method is correct.
I think you should also consider partitions with more than two subsets.
Here's a test case. The output should be 2 and the optimal multiplication sequence is (20x30, 30x1, (1x30, 30x1)).
Here's a test case. The output should be 2 and the optimal multiplication sequence is (20x30, 30x1, (1x30, 30x1)).
Code: Select all
1
4
20 30
30 1
1 30
30 1
1
620
after editing my code now it handles ur case. but still WA. if u can give some more cases that is violated by my code that would be great!
#include<stdio.h>
#define INF 1000000000
struct MATRIX
{
int a,b;
}matrix[80];
int min(int a,int b)
{
if(a>b) return b;
return a;
}
int main()
{
int i,j,k,l,t,temp,f;
int cases,ks,q,mat;
int ans[80][80];
int lim,FALSE;
//freopen("test.in","r",stdin);
scanf("%d",&cases);
for(ks=1;ks<=cases;ks++)
{
printf("Matrix #%d\n",ks);
scanf("%d",&mat);
for(i=1;i<=mat;i++)
scanf("%d%d",&matrix[i].a,&matrix[i].b);
scanf("%d",&q);
while(q)
{
scanf("%d",&lim);
FALSE=0;
for(i=2;i<=mat;i++)
if(matrix[i1].b!=matrix[i].a)
{
ans[1][mat]=INF;
printf("Impossible.\n");
FALSE=1;
break;
}
if(FALSE) continue;
for(l=1;l<=mat;l++)
for(i=1;i<=matl+1;i++)
{
if(l==1) {ans[i][i]=0; continue;}
j=i+l1;
temp=0;
for(t=i+1;t<=j;t++)
temp+=(matrix[t].a*matrix[t].b);
temp*=matrix[i].a;
if(temp<=lim) ans[i][j]=1;
else ans[i][j]=INF;
for(k=i;k<j;k++)
{
if(k!=i)
{
temp=0;
for(f=i+1;f<=k;f++)
temp+=matrix[f].a*matrix[f].b;
temp+=matrix[k+1].a*matrix[j].b;
temp*=matrix[i].a;
if(temp<=lim)
ans[i][j]=min(ans[i][j],1+ans[k+1][j]);
}
if( (matrix[i].a*matrix[k].b*matrix[j].b<=lim) && (ans[i][j]>ans[i][k]+ans[k+1][j]+1) )
{
ans[i][j]=ans[i][k]+ans[k+1][j]+1;
}
}
}
if(ans[1][mat]>=INF) printf("Impossible.\n");
else printf("%d\n",ans[1][mat]);
}
printf("\n");
}
return 0;
}
#include<stdio.h>
#define INF 1000000000
struct MATRIX
{
int a,b;
}matrix[80];
int min(int a,int b)
{
if(a>b) return b;
return a;
}
int main()
{
int i,j,k,l,t,temp,f;
int cases,ks,q,mat;
int ans[80][80];
int lim,FALSE;
//freopen("test.in","r",stdin);
scanf("%d",&cases);
for(ks=1;ks<=cases;ks++)
{
printf("Matrix #%d\n",ks);
scanf("%d",&mat);
for(i=1;i<=mat;i++)
scanf("%d%d",&matrix[i].a,&matrix[i].b);
scanf("%d",&q);
while(q)
{
scanf("%d",&lim);
FALSE=0;
for(i=2;i<=mat;i++)
if(matrix[i1].b!=matrix[i].a)
{
ans[1][mat]=INF;
printf("Impossible.\n");
FALSE=1;
break;
}
if(FALSE) continue;
for(l=1;l<=mat;l++)
for(i=1;i<=matl+1;i++)
{
if(l==1) {ans[i][i]=0; continue;}
j=i+l1;
temp=0;
for(t=i+1;t<=j;t++)
temp+=(matrix[t].a*matrix[t].b);
temp*=matrix[i].a;
if(temp<=lim) ans[i][j]=1;
else ans[i][j]=INF;
for(k=i;k<j;k++)
{
if(k!=i)
{
temp=0;
for(f=i+1;f<=k;f++)
temp+=matrix[f].a*matrix[f].b;
temp+=matrix[k+1].a*matrix[j].b;
temp*=matrix[i].a;
if(temp<=lim)
ans[i][j]=min(ans[i][j],1+ans[k+1][j]);
}
if( (matrix[i].a*matrix[k].b*matrix[j].b<=lim) && (ans[i][j]>ans[i][k]+ans[k+1][j]+1) )
{
ans[i][j]=ans[i][k]+ans[k+1][j]+1;
}
}
}
if(ans[1][mat]>=INF) printf("Impossible.\n");
else printf("%d\n",ans[1][mat]);
}
printf("\n");
}
return 0;
}
Self judging is the best judging!
More test cases:
And this is what my program has found:
Code: Select all
3
4
1 20
20 40
40 20
20 10
1
1000
5
30 1
1 33
33 33
33 17
17 42
1
1300
9
1 20
20 40
40 20
20 10
10 1
1 20
20 40
40 20
20 10
2
1000 800
Code: Select all
Matrix #1 optimal sequence:
2 ((1x20, 20x40), 40x20, 20x10)
Matrix #2
3 (30x1, ((1x33, 33x33), 33x17, 17x42))
Matrix #3
4 ((((1x20, 20x40), 40x20, 20x10), 10x1, 1x20, 20x40), 40x20, 20x10)
5 (((1x20, 20x40), 40x20), 20x10, 10x1, ((1x20, 20x40), 40x20), 20x10)
My algorithm is to compute for each interval of matrices the minimum number of matrissor's uses, and (secondly) the minimum number of operations it took to multiply the last sequence of matrices. And when I split an interval into two, I also check whether it's possible to append the second subinterval at the end of the first.
For example in the test case #1 of my previous post, my program at some point splits the matrices as:
There are two possibilities. I can either evaluate the matrices as
(((1x20,20x40),40x20), 20x10), which gives the answer 3,
or I can add the matrix 20x10 at the end of the first interval and get the answer 2:
((1x20,20x40),40x20, 20x10)
The last sequence takes 800 + 1*20*10 = 1000 operations, so it doesn't exceed matrissor's capacity.
The same idea also works for more complicated test cases: if you want to evaluate a sequence of matrices
((A1, A2, ..., Ak), (B1, B2, ..., Bm)),
check whether it's possible to evaluate it as
(A1, A2, ..., Ak, (B1, B2, ..., Bm)).
For example in the test case #1 of my previous post, my program at some point splits the matrices as:
Code: Select all
((1x20, 20x40), 40x20) and 20x10
2 matrissor's uses, 0 matrissor's uses,
last sequence takes 1*40*20=800 ops. 0 ops.
(((1x20,20x40),40x20), 20x10), which gives the answer 3,
or I can add the matrix 20x10 at the end of the first interval and get the answer 2:
((1x20,20x40),40x20, 20x10)
The last sequence takes 800 + 1*20*10 = 1000 operations, so it doesn't exceed matrissor's capacity.
The same idea also works for more complicated test cases: if you want to evaluate a sequence of matrices
((A1, A2, ..., Ak), (B1, B2, ..., Bm)),
check whether it's possible to evaluate it as
(A1, A2, ..., Ak, (B1, B2, ..., Bm)).
I have passed the given test cases but still WA.
Can someone please verify my outputs for the following cases.
Input:
My Output:
Thanks in advance.
Can someone please verify my outputs for the following cases.
Input:
Code: Select all
 CUT  GOT AC  CUT 
Code: Select all
 CUT  GOT AC  CUT 
Last edited by Dreamer#1 on Thu Oct 13, 2005 9:17 pm, edited 1 time in total.
Can you give more details please? I have tried a similar algorithm, with A[j][k] being minimum number of matrissor uses for interval i..j, and matrices i..k are in a matrissor, but it doesn't work...mf wrote: The same idea also works for more complicated test cases: if you want to evaluate a sequence of matrices
((A1, A2, ..., Ak), (B1, B2, ..., Bm)),
check whether it's possible to evaluate it as
(A1, A2, ..., Ak, (B1, B2, ..., Bm)).

 New poster
 Posts: 21
 Joined: Sun Oct 05, 2003 11:19 am
 Location: Bulgaria, Shoumen
 Contact:
Just maintain two 2D arrays the one should contain the minimal amount of matrix ( i don't know the plural ) and the other the
minimal cost of multiplying the last few matrix in a given interval.
Rostislav
P.S. read the statment carefully i.e. you cannot use the proccesor like this : A*(...)*B... only A*B*C...
minimal cost of multiplying the last few matrix in a given interval.
Rostislav
P.S. read the statment carefully i.e. you cannot use the proccesor like this : A*(...)*B... only A*B*C...
Yeah, i got accepted after posting, i was a bit confused.Rostislav wrote:Just maintain two 2D arrays the one should contain the minimal amount of matrix ( i don't know the plural ) and the other the
minimal cost of multiplying the last few matrix in a given interval.
Rostislav
P.S. read the statment carefully i.e. you cannot use the proccesor like this : A*(...)*B... only A*B*C...

 Learning poster
 Posts: 99
 Joined: Sun Apr 06, 2003 5:53 am
 Location: Dhaka, Bangladesh
 Contact:
My code matches all the inputs provided in this post ... but still WA
Can anyone who has got AC post the o/p of the following sample? Thnx in advance...
Can anyone who has got AC post the o/p of the following sample? Thnx in advance...
Code: Select all
1
4
10 1
1 100
100 1
1 10
8
100 110 200 210 1000 1100 2000 2100
Where's the "Any" key?