3292 - Matrissor (From Dhaka 2005-2006)

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

3292 - Matrissor (From Dhaka 2005-2006)

Post by shamim » Sat Sep 24, 2005 11:33 am

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Mon Sep 26, 2005 9:00 am

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

Mahbub
Self judging is the best judging!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Sep 26, 2005 9:37 pm

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Tue Sep 27, 2005 4:06 am

OH yeh! a brilliant case! my code outputs 3. let me see if i can correct it! :D
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Tue Sep 27, 2005 6:17 am

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?
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Tue Sep 27, 2005 12:52 pm

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;
}
Self judging is the best judging!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Sep 27, 2005 5:32 pm

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Wed Sep 28, 2005 2:56 am

Mj, thanks for ur cases. Now I can understand where my algo fails. It fails in case of:
()
Self judging is the best judging!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Sep 28, 2005 9:13 am

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

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Thu Oct 13, 2005 8:03 pm

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. :)
Last edited by Dreamer#1 on Thu Oct 13, 2005 9:17 pm, edited 1 time in total.

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Thu Oct 13, 2005 9:15 pm

Never Mind got AC! :D

domino
New poster
Posts: 19
Joined: Thu Dec 25, 2003 6:01 pm

Post by domino » Mon Oct 17, 2005 4:30 pm

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)).
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
New poster
Posts: 21
Joined: Sun Oct 05, 2003 11:19 am
Location: Bulgaria, Shoumen
Contact:

Post by Rostislav » Tue Oct 18, 2005 3:31 pm

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
New poster
Posts: 19
Joined: Thu Dec 25, 2003 6:01 pm

Post by domino » Tue Oct 18, 2005 6:44 pm

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...
Yeah, i got accepted after posting, i was a bit confused.

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Sat Nov 26, 2005 8:48 pm

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
Where's the "Any" key?

Post Reply

Return to “ACM ICPC Archive Board”