3292 - Matrissor (From Dhaka 2005-2006)

[shamim]

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.

[shanto86]

well, i made a DP soln but it is also getting WA. i can';t understand why? can any body help us?

Mahbub

[mf]

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)).

Code: Select all

1
4
20 30
30 1
1 30
30 1
1
620

[shanto86]

OH yeh! a brilliant case! my code outputs 3. let me see if i can correct it!

[shanto86]

perhaps i am not able to correct my DP soln to handle such type of case but i will try!

by this mean time, can u plz give a clue? will it be DP soln?

[shanto86]

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[i-1].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<=mat-l+1;i++)
{
if(l==1) {ans[i][i]=0; continue;}

j=i+l-1;

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;
}

[mf]

More test cases:

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

And this is what my program has found:

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)

[shanto86]

Mj, thanks for ur cases. Now I can understand where my algo fails. It fails in case of:
()

[mf]

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:

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.

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)).

[Dreamer#1]

I have passed the given test cases but still WA.

Can someone please verify my outputs for the following cases.

Input:

Code: Select all

-- CUT -- GOT AC -- CUT --

My Output:

Code: Select all

-- CUT -- GOT AC -- CUT --

Thanks in advance.

[Dreamer#1]

Never Mind got AC!

[domino]

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)).

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...

[Rostislav]

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...

[domino]

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...

Yeah, i got accepted after posting, i was a bit confused.

[Solaris]

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...

Code: Select all

1

4
10 1
1 100
100 1
1 10
8
100 110 200 210 1000 1100 2000 2100