Page 1 of 2

348 - Optimal Array Multiplication Sequence

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

Posted: Wed Apr 02, 2003 9:26 am
by Andrey Mokhov
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.

Posted: Wed Apr 02, 2003 7:13 pm
by yiuyuho
Thank You!

348: Why am i getting wrong answer?

Posted: Mon May 23, 2005 6:12 pm
by fsarker
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[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;
}
I don't have any idea why i am getting WA. Anyone likes to help.

348 - TLE

Posted: Fri May 27, 2005 3:20 pm
by Karthekeyan
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[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
by Karthekeyan
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!

Re: 348 - TLE

Posted: Mon May 30, 2005 6:30 am
by sumankar
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.

Posted: Mon May 30, 2005 8:47 am
by Karthekeyan
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
by sumankar
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.

RTE - 348 Optimal Array Multiplication Sequence

Posted: Fri Sep 02, 2005 3:39 am
by kane116
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... :cry:
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;
    }
Thanks a lot!! :oops:

Posted: Sun Sep 04, 2005 2:25 am
by kane116
Please help me...I cannot find and error in my code. :cry:

Posted: Wed Oct 19, 2005 4:29 am
by Jan
You used map[j]=32767. This is too small. I used map[j]=2000000000.

Hope it helps.

348 (WA)

Posted: Tue Apr 25, 2006 2:00 pm
by tuman
help me out. I m having some problem with this problem and continuously getting wrong answer . :evil:

here is my code:

//code deleted after accepted :lol:

// I hv found my erra. very stupid erra.
if anyone need critical input\output then post it here

Posted: Wed Aug 23, 2006 12:49 am
by 898989
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

348 why PE

Posted: Thu Jan 11, 2007 3:47 pm
by sumantbhardvaj
code removed after being accepted.. :lol: