348  Optimal Array Multiplication Sequence
Moderator: Board moderators
348  Optimal Array Multiplication Sequence
Is there another approach for this problem other than trying to generate all permutations of sequences?

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
348: Why am i getting wrong answer?
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*21;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<=Nl+1;i++)
{
j=i+l1;
m[i][j]=4294967295;
;
for(k=i;k<=j1;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;
}
fsarker

 New poster
 Posts: 33
 Joined: Tue Jun 29, 2004 1:38 pm
 Location: IITM,chennai,Tamil Nadu,India
 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??
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[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<=nl+1;i++)
{
int j=i+l1;
cost[i][j]=max;
for(int k=i;k<=j1;k++)
{
int q=cost[i][k]+cost[k+1][j]+p[i1]*p[k]*p[j];
if(q<cost[i][j])
{
cost[i][j]=q;
s[i][j]=k;
}
}
}
}
prin(s,1,N);
cout<<'\n';
}
}
Karthe

 New poster
 Posts: 33
 Joined: Tue Jun 29, 2004 1:38 pm
 Location: IITM,chennai,Tamil Nadu,India
 Contact:
Re: 348  TLE
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.

 New poster
 Posts: 33
 Joined: Tue Jun 29, 2004 1:38 pm
 Location: IITM,chennai,Tamil Nadu,India
 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.
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.
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
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;
}
You used map[j]=32767. This is too small. I used map[j]=2000000000.
Hope it helps.
Hope it helps.
Ami ekhono shopno dekhi...
HomePage
HomePage
348 (WA)
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.
We the dreamer of the dreamy dream...

 Learning poster
 Posts: 83
 Joined: Wed Feb 01, 2006 12:59 pm
 Location: (Fcicu) 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....
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
Sleep enough after death, it is the time to work.
Mostafa Saad
Mostafa Saad

 New poster
 Posts: 19
 Joined: Sun Jun 18, 2006 4:07 pm
 Contact:
348 why PE
code removed after being accepted..
Last edited by sumantbhardvaj on Thu Jan 11, 2007 8:06 pm, edited 2 times in total.