348 - Optimal Array Multiplication Sequence

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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

Post by yiuyuho » Wed Apr 02, 2003 7:58 am

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

Post by Andrey Mokhov » 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.

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

Post by yiuyuho » Wed Apr 02, 2003 7:13 pm

Thank You!

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

348: Why am i getting wrong answer?

Post by fsarker » Mon May 23, 2005 6:12 pm

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

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

348 - TLE

Post by Karthekeyan » 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??

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

    }
}
Karthe

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

Post by Karthekeyan » 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!
Karthe

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

Re: 348 - TLE

Post by sumankar » Mon May 30, 2005 6:30 am

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
Location: IITM,chennai,Tamil Nadu,India
Contact:

Post by Karthekeyan » 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++)
Karthe

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

Post by sumankar » 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.

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

RTE - 348 Optimal Array Multiplication Sequence

Post by kane116 » 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... :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:

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

Post by kane116 » Sun Sep 04, 2005 2:25 am

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Oct 19, 2005 4:29 am

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

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

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

348 (WA)

Post by tuman » Tue Apr 25, 2006 2:00 pm

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

Post by 898989 » 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
Sleep enough after death, it is the time to work.
Mostafa Saad

sumantbhardvaj
New poster
Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm
Contact:

348 why PE

Post by sumantbhardvaj » Thu Jan 11, 2007 3:47 pm

code removed after being accepted.. :lol:
Last edited by sumantbhardvaj on Thu Jan 11, 2007 8:06 pm, edited 2 times in total.

Post Reply

Return to “Volume 3 (300-399)”