442 - Matrix Chain Multiplication

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

Moderator: Board moderators

udvat
New poster
Posts: 29
Joined: Thu Aug 07, 2003 9:56 pm

442 - Matrix Chain Multiplication

Post by udvat » Sun Jun 13, 2004 2:44 pm

wud anybody plz provide me some tricky inputs for the problem 442??

murkho
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

442 , why WA??

Post by murkho » Tue Nov 01, 2005 4:31 pm

pls tell me some input for getting WA or help me to find probs here>>

Code: Select all

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


struct m{
			char ch;
			long row;
			long col;
		};


char stack[1000];


int main()
{

	struct m matrix[150],first,second,tmp;
	char str[10000];
	char ch_index = 'a'-1;
	char a,b,t;
	int test_case;
	int i,j;
	int index,flag,error_flag;
	unsigned long res;
	int matrix_index = -1;
	//freopen("442.txt","r",stdin);
	scanf("%d",&test_case); 
	scanf("%c",&t);
	

	for(i = 0;i<test_case;i++)	
	{
		scanf("%c",&t);
		scanf("%ld %ld",&matrix[t].row,&matrix[t].col);
		scanf("%c",&t);
		
	}

	
	while(gets(str)!= NULL)
	{
	
		i = 0;
		res = 0;		
		index = -1;
		flag = 0;
		error_flag = 0;
		while(str[i]) 
		{
			if( isupper(str[i]) ==1)
			{
				stack[++index] = str[i];
			
			}

			else if (str[i] == ')')
			{
				flag = 1;
				b = stack[index];
				index --;
				a = stack[index];
				index--;
				first = matrix[a];
				second = matrix[b];
				if(first.col != second.row)
				{
					printf("error\n");
					error_flag = 1;
					break;
				}
			
				else 
				{
					tmp.ch = ++ch_index;
					tmp.row = first.row;
					tmp.col = second.col;
					matrix[tmp.ch] = tmp;
					stack[++index] = tmp.ch;
					res+= first.row * first.col* second.col;
				
				}

			}
		
		
			i++;
		}
	
		if(flag ==0 && error_flag ==0)
			printf("0\n");
		else if(error_flag == 0)
			printf("%lu\n",res);

	}



}

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Tue Nov 01, 2005 7:27 pm

Change

Code: Select all

if( isupper(str[i]) ==1)
to

Code: Select all

if( isupper(str[i]))
Best of luck ;)
Where's the "Any" key?

murkho
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

Thanks .....

Post by murkho » Tue Nov 01, 2005 10:14 pm

Thank U . I just forget that on success isupper() returns a non zero value not exactly 1.
Again THank U for posting....and keep dreaming..

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

442 - RTE

Post by medv » Tue Jun 20, 2006 1:49 pm

I have RTE, but can't find why.
I did a lot of testing.
I tried to put char s[100000]; but it didn't help

Thanks, acc
Last edited by medv on Wed Jun 21, 2006 6:50 pm, edited 1 time in total.

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Tue Jun 20, 2006 8:58 pm

Add these two returns on error case in your expression() function,
expression();
if ( Error) return;
expression();
if ( Error) return;
These helps to get AC :).
ps. please remove the code and please please post formatted code.... its hard to watch it without that :P
Cheers.
Istiaque Ahmed [the LA-Z-BOy]

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

442: Why WA!

Post by rhsumon » Wed Aug 23, 2006 12:34 pm

Here is my programm : Why WA?? Pls Help me..........
#include<stdio.h>

struct matrix{
int r,c;
char name;
}mat[1000];

char stack[100],nam[50];
long cast,flag = 1,top,n,k;

char find(char a,char b){
int i,rowa,rowb,cola,colb,g_a,g_b;
for(i=0; i<n; i++){
if(mat.name == a){
rowa = mat.r;
cola = mat.c;
g_a = 1;
}
if(mat.name == b){
rowb = mat.r;
colb = mat.c;
g_b = 1;
}
if(g_a == 1 && g_b == 1) break;
}
if(cola == rowb){
cast = cast + cola*rowa*colb;
mat[n].r = rowa;
mat[n].c = colb;
mat[n].name = nam[k];
k++;
n++;
}
else {
printf("error\n");
flag = 0;
return 0;
}
return nam[k-1];
}
void push(char ch){
stack[top] = ch;
top++;
}
void pop(){
char a,b,res;
b = stack[top-1];
a = stack[top-2];
top-=2;
res = find(a,b);
if(res != 0) push(res);
}

int main()
{
int i,z;
char exp[100];
char str[2],s = 'a';
for(i=0; i<26; i++){
nam = s;
s++;
}
//freopen("442.in","r",stdin);
scanf("%d",&n);
z = n;
for(i=0; i<n; i++)
scanf("%s %d %d",&mat.name,&mat.r,&mat.c);
gets(str);
while(gets(exp) != NULL){
top = 0;
cast = 0;
flag = 1;
k = 0;
for(i=0; exp[i]; i++){
if(exp[i]!='(' && exp[i] != ')')
push(exp[i]);
else if(exp[i] == ')'){
pop();
}
}
if(cast > 0)
n = z;
if(flag == 1 || top == 1)
printf("%ld\n",cast);
}
return 0;
}

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Sun Feb 11, 2007 8:09 am

thanx everybody
keep posting
Last edited by newton on Thu Mar 22, 2007 6:10 am, edited 1 time in total.

User avatar
jainal cse du
New poster
Posts: 23
Joined: Thu Jul 27, 2006 2:43 pm
Location: University of Dhaka,Bangladesh

Post by jainal cse du » Wed Feb 14, 2007 3:18 pm

hello everebody
i am so bored with the chilly problem. i cant find the problem in my innocent code.
sample outputs are okey.
but why WA?
may anybody check it ?



Code: Select all


#include <iostream.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>

void push(char ch);
struct m{
	long row;
	long col;
};
char stack[200];
int top = 100;
int main()
{

 struct m matrix[100];
 long test,result,i,flag;
 char ch,a,b,str[100];
 cin >> test;
 while(test--)
 {
  cin>>ch;
  cin>> matrix[ch].row>> matrix[ch].col;
 }

 while(gets(str))
 {
  result = 0;
  for(i = 0; str[i]; i++)
  {
   if(isupper(str[i]))
    push(str[i]);
   else if(str[i]==')')
   {
    b = stack[top-1];
    a = stack[top-2];
    flag = 1;
    if(matrix[a].col != matrix[b].row)
    {
     flag = 0;
     cout<<"error"<<endl;
     break;
    }
    top-=2;
    result += matrix[a].row *matrix[a].col*matrix[b].col;
    ch = (char)top;
    matrix[top].row = matrix[a].row;
    matrix[top].col = matrix[b].col;
    stack[top++] = ch;
   }
  }
  if(flag)
   cout<<result<<endl;
   }
 return 0;
}
void push(char ch)
{
 stack[top++] = ch;
}




advanced thanks

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

Post by Jan » Thu Feb 15, 2007 9:55 am

jainal cse du wrote:hello everebody
i am so bored with the chilly problem. i cant find the problem in my innocent code.
sample outputs are okey.
but why WA?
Innocent code!! Really? Try the samples

Input:

Code: Select all

3
A 50 10
B 10 20
C 20 5
A
B
C
()
Output:

Code: Select all

0
0
0
error
Hope these help.
Ami ekhono shopno dekhi...
HomePage

el_vitucho
New poster
Posts: 1
Joined: Thu Mar 15, 2007 7:07 pm

Post by el_vitucho » Thu Mar 15, 2007 7:13 pm

Hi everybody, i cant find my mistake here :( , i tried with the inputs and my problem gave me the correct answers. Someone who post more inputs and outputs please!!!...
My code

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std;

struct matriz{
	char c;
	int filas,cols;
};
int main(void)
{
	int n=0;
	scanf("%d\n",&n);	
	matriz dict[30];	
	for(int i = 0; i < n;i++){		
		matriz m;
		scanf("%c %d %d\n",&(m.c),&(m.filas),&(m.cols));
		dict[m.c-'A']=m;
	}	
	char exp[1000];
	while(1){
		if(scanf("%s",exp)!=1) break;
		stack<matriz> s;		
		double total = 0;
		matriz thenew;
		int flag = 0;
		for(int j = 0; j < strlen(exp);j++){
			char car = exp[j];
			if(car>='A' && car<='Z'){
				s.push(dict[car-'A']);
			}
			else if(car==')'){
				if(s.size()==0) {
					flag = 1;
					break;
				}
				matriz sale1 = s.top();
				s.pop();
				matriz sale2 = s.top();
				s.pop();
				if(sale1.cols==sale2.filas || sale2.cols==sale1.filas){					
					if(sale2.cols==sale1.filas){
						matriz auxi = sale1;
						sale1=sale2;
						sale2=auxi;
					}
					thenew.filas = sale1.filas;
					thenew.cols = sale2.cols;
					s.push(thenew);
					total+=(sale1.cols*sale1.filas*sale2.cols);
				}
				else{
					flag = 1;
					break;
				}
			}
		}
		if(flag)printf("error\n");
		else printf("%g\n",total);
	}


}
HaCkErMaTe Programming Team

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

Post by Jan » Fri Mar 16, 2007 12:37 am

Try the cases...

Input:

Code: Select all

9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
(CG(HI))
(AB(C))
(A)
Output:

Code: Select all

6250
error
error
Hope these help.
Ami ekhono shopno dekhi...
HomePage

Darwish
New poster
Posts: 2
Joined: Wed May 23, 2007 6:19 pm

To Jan

Post by Darwish » Thu May 24, 2007 7:07 pm

Some test cases kindly given above by Jan are wrong according to the EBNF specification of the problem. Test cases:

Code: Select all

()
(CG(HI))
(AB(C))
According to the EBNF:

Code: Select all

Expression = Matrix | "(" Expression Expression ")"
Matrix     = "A" | "B" | "C" | ... | "X" | "Y" | "Z"
(): wrong since between the '(' and ')' there must exist _two_ valid expressions. Empty set by definition is not a valid expression (Since "Matrix" can't be empty)

(AB(C)): 2 wrong points.
1) Any two expressions beside each other must be inside "()", Considering A as the first expression, "B(C)" isn't a valid second expression.
2) (C) is not valid since two expressins must exist between "()" and by definition, an expression can't be empty.

(CG(HI)): same case as point 1 above

Best

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

Post by Jan » Thu May 24, 2007 8:20 pm

The second part of the input file strictly adheres to the following syntax (given in EBNF):
Missed that line. :oops: . You are correct.
Ami ekhono shopno dekhi...
HomePage

gba356
New poster
Posts: 15
Joined: Sat Apr 28, 2007 10:12 am
Location: Taiwan

Post by gba356 » Thu Oct 25, 2007 5:50 pm

I used STL to implement the stack. And for some reasons, my code is getting WA again and again; I wonder why...

Here's my code:

Code: Select all

Code deleted.
Wow, thanks for Jan's help. :D

But why can't I use the stack<char> one?
Last edited by gba356 on Fri Oct 26, 2007 6:39 pm, edited 1 time in total.

Post Reply

Return to “Volume 4 (400-499)”