## 348 - Optimal Array Multiplication Sequence

Moderator: Board moderators

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

### 348 - Optimal Array Multiplication Sequence

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

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
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.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
Thank You!

fsarker
New poster
Posts: 1
Joined: Mon May 23, 2005 5:51 pm

### 348: Why am i getting wrong answer?

The following is the code for Optimal Matrix Multiplication

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,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;
}
``````
I don't have any idea why i am getting WA. Anyone likes to help.
fsarker

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Contact:

### 348 - TLE

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

Code: Select all

``````#include<iostream>
#include<vector>
using namespace std;
#define max 1E7

void prin(int s,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={max};
int s;

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

}
}
``````
Karthe

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Contact:
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!
Karthe

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

### Re: 348 - TLE

Karthekeyan wrote: ...
main()
{
int N;
...
[/code]
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 ...
Make it

Code: Select all

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

Regards,
Suman.

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Contact:
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++)
Karthe

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
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.

kane116
New poster
Posts: 8
Joined: Sun Aug 07, 2005 5:35 am

### RTE - 348 Optimal Array Multiplication Sequence

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

Code: Select all

``````#include <stdio.h>
#include <string.h>

int n;
int idx;
int row, col;
int map;
int que;

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[], 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;
}
``````
Thanks a lot!! kane116
New poster
Posts: 8
Joined: Sun Aug 07, 2005 5:35 am
Please help me...I cannot find and error in my code. Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
You used map[j]=32767. This is too small. I used map[j]=2000000000.

Hope it helps.
Ami ekhono shopno dekhi...
HomePage

tuman
New poster
Posts: 24
Joined: Sat Oct 22, 2005 7:30 pm
Location: CUET
Contact:

### 348 (WA)

help me out. I m having some problem with this problem and continuously getting wrong answer . here is my code:

//code deleted after accepted // I hv found my erra. very stupid erra.
if anyone need critical input\output then post it here
We the dreamer of the dreamy dream...

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
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....
code removed after being accepted.. 