### 348 - Optimal Array Multiplication Sequence

Posted:

**Wed Apr 02, 2003 7:58 am**Is there another approach for this problem other than trying to generate all permutations of sequences?

The Online Judge board

https://uva.onlinejudge.org/board/

Page **1** of **2**

Posted: **Wed Apr 02, 2003 7:58 am**

Is there another approach for this problem other than trying to generate all permutations of sequences?

Posted: **Wed Apr 02, 2003 9:26 am**

The problem can be solved using Dynamic Programming.

I won't explain the algorithm to you as it can be found easily in 'net. Just look for any site about DP and most of them contain the algorithm for the problem.

Good luck!

Andrey.

I won't explain the algorithm to you as it can be found easily in 'net. Just look for any site about DP and most of them contain the algorithm for the problem.

Good luck!

Andrey.

Posted: **Wed Apr 02, 2003 7:13 pm**

Thank You!

Posted: **Mon May 23, 2005 6:12 pm**

The following is the code for Optimal Matrix Multiplication
I don't have any idea why i am getting WA. Anyone likes to help.

Code: Select all

```
#include<iostream>
#define MAX 12
using namespace std;
int s[MAX][MAX];
void print(int i,int j)
{
if(i==j)
cout<<"A"<<i;
else
{
cout<<"(";
print(i,s[i][j]);
cout<<" x ";
print(s[i][j]+1,j);
cout<<")";
}
}
int main()
{
int N,i,j,p[11],t,l,k,c=0;
unsigned long m[MAX][MAX];
while(cin>>N)
{
if(N==0) break;
c++;
for(i=0,j=0;i<N*2-1;i++)
{
cin>>t;
if(i%2 == 0)p[j++]=t;
}
cin>>p[j];
for(i=1;i<=N;i++) m[i][i]=0;
for(l=2;l<=N;l++)
{
for(i=1;i<=N-l+1;i++)
{
j=i+l-1;
m[i][j]=4294967295;
;
for(k=i;k<=j-1;k++)
{
t=m[i][k] + m[k+1][j] + p[i]*p[k]*p[j];
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}
cout<<"Case "<<c<<": ";
print(1,N);
cout<<"\n";
}
return 0;
}
```

Posted: **Fri May 27, 2005 3:20 pm**

I dont think there's any better algorithm than the one by DP....

my code is very much similar to the one in CLR!!!! CAN NEONE TEMME WHY THE OJ GIVES**TLE ** !!!! Where should I optimise??

my code is very much similar to the one in CLR!!!! CAN NEONE TEMME WHY THE OJ GIVES

Code: Select all

```
#include<iostream>
#include<vector>
using namespace std;
#define max 1E7
void prin(int s[1000][1000],int i, int j)
{
if(i==j)
cout<<"A"<<i;
else
{
cout<<"(";
prin(s,i,s[i][j]);
cout<<" x ";
prin(s,s[i][j]+1,j);
cout<<")";
}
}
main()
{
int N;
int cases=1;
while(cin>>N)
{
if(N==0)
break;
cout<<"Case "<<cases<<": ";
cases++;
int cost[1000][1000]={max};
int s[1000][1000];
vector<int> p;
int temp;
for(int i=0;i<N;i++)
{
cin>>temp;
p.push_back(temp);
cin>>temp;
}
p.push_back(temp);
int n=p.size()-1;
for(int i=1;i<=n;i++)
{
cost[i][i]=0;
}
for(int l=2;l<=n;l++)
{
for(int i=1;i<=n-l+1;i++)
{
int j=i+l-1;
cost[i][j]=max;
for(int k=i;k<=j-1;k++)
{
int q=cost[i][k]+cost[k+1][j]+p[i-1]*p[k]*p[j];
if(q<cost[i][j])
{
cost[i][j]=q;
s[i][j]=k;
}
}
}
}
prin(s,1,N);
cout<<'\n';
}
}
```

Posted: **Fri May 27, 2005 3:24 pm**

Even i wrote the similar code from CLR!

And got WA!! Then, on increasing the size of array 's', my code ran with the OJ but reported 'TLE"!! So the WA is due to the very small size of array 's' that you have used!

But, if you manage to overcome the TLE, do temme!

And got WA!! Then, on increasing the size of array 's', my code ran with the OJ but reported 'TLE"!! So the WA is due to the very small size of array 's' that you have used!

But, if you manage to overcome the TLE, do temme!

Posted: **Mon May 30, 2005 6:30 am**

I dont think this code would compile at all. AFAIK in C++, you need an explicit return type for all your functions, as there is no defaulting to int like C.So ...Karthekeyan wrote: ...

main()

{

int N;

...

[/code]

Make it

Code: Select all

`int main() {... return 0; }`

Regards,

Suman.

Posted: **Mon May 30, 2005 8:47 am**

Sorry, the code compiles very well! I have written like this for the past 50 problems and got 'em accepted! So, it's not the problem with compiling! (Note that the OJ uses g++)

Posted: **Mon May 30, 2005 9:43 am**

Off course, it compiles, otherwise you wouldn't get a TLE. I was trying to give you some generic advice.

As for this problem, I can tell you, TLE occurs mostly due to choice of inappropriate algorithm.The algorithm you are using here is ok.So next go check input limits.The problem says N will never be larger than 10, so why use a 1000x1000 array?Anyway, changing that array limit will give you WA!

You have the whole namespace under std, then you are defining a macro

`max' which actually clashes with the std::max() function.Change that.There are other problems in your code, like assigning double to int etc...so recheck your code.

Suman.

As for this problem, I can tell you, TLE occurs mostly due to choice of inappropriate algorithm.The algorithm you are using here is ok.So next go check input limits.The problem says N will never be larger than 10, so why use a 1000x1000 array?Anyway, changing that array limit will give you WA!

You have the whole namespace under std, then you are defining a macro

`max' which actually clashes with the std::max() function.Change that.There are other problems in your code, like assigning double to int etc...so recheck your code.

Suman.

Posted: **Fri Sep 02, 2005 3:39 am**

Please help me check the program, I don't know why OJ give RTE to me... I try it on both Linux and Windows, but no error occur...

Please help me...

Here is my code
Thanks a lot!!

Please help me...

Here is my code

Code: Select all

```
#include <stdio.h>
#include <string.h>
int n;
int idx;
int row[10], col[10];
int map[100][100];
int que[100][100];
int init()
{ memset(map, 0, sizeof(map));
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
return 0;
}
int cal()
{ int j, tmp;
for (int i = 0; i < n; i++)
{ map[i][i] = 0;
}
for (int l = 1; l < n; l++)
{ for (int i = 0; i < n - l; i++)
{ j = i + l;
printf("%d %d\n", i, j);
map[i][j] = 32767;
for (int k = i; k < j; k++)
{ tmp = map[i][k] + map[k + 1][j] + row[i] * col[k] * col[j];
if (tmp < map[i][j])
{ map[i][j] = tmp;
que[i][j] = k;
}
}
}
}
return 0;
}
int outpt(int arg[][100], int i, int j)
{ if (i == j)
{ printf("A%d", i + 1);
}
else
{ printf("(");
outpt(arg, i, arg[i][j]);
printf(" x ");
outpt(arg, arg[i][j] + 1, j);
printf(")");
}
return 0;
}
int inpt()
{
idx = 0;
do
{ init();
scanf("%d", &n);
if (n != 0)
{ idx++;
//printf("Case %d: ", idx);
for (int i = 0; i < n; i++)
{ scanf("%d %d", &row[i], &col[i]);
}
cal();
//outpt(que, 0, n - 1);
printf("\n");
}
} while (n != 0);
return 0;
}
int main()
{
inpt();
return 0;
}
```

Posted: **Sun Sep 04, 2005 2:25 am**

Please help me...I cannot find and error in my code.

Posted: **Wed Oct 19, 2005 4:29 am**

You used map*[j]=32767. This is too small. I used map**[j]=2000000000.*

Hope it helps.

Hope it helps.

Posted: **Tue Apr 25, 2006 2:00 pm**

help me out. I m having some problem with this problem and continuously getting wrong answer .

here is my code:

here is my code:

if anyone need critical input\output then post it here

//code deleted after accepted

// I hv found my erra. very stupid erra.

Posted: **Wed Aug 23, 2006 12:49 am**

Hello Karthekeyan

Your code is similar to my code, and this is expected

i got ac in 0.480 & you in 0.469, so u may getting wa in the last cases.

i think u hve problems with array p, or generaly ur array indexing

my code is copy & paste from "Introducaion to algorithms"

u only need long data type && 2000000000 as a large value to assign.

This problem must not give wa nor TLE nor RTE, it is only copy and paste from the algorithms book, so if any one get the above replyies, ur code has a minor bug....

I hope this is helpful

Your code is similar to my code, and this is expected

i got ac in 0.480 & you in 0.469, so u may getting wa in the last cases.

i think u hve problems with array p, or generaly ur array indexing

my code is copy & paste from "Introducaion to algorithms"

u only need long data type && 2000000000 as a large value to assign.

This problem must not give wa nor TLE nor RTE, it is only copy and paste from the algorithms book, so if any one get the above replyies, ur code has a minor bug....

I hope this is helpful

Posted: **Thu Jan 11, 2007 3:47 pm**

code removed after being accepted..