## 442 - Matrix Chain Multiplication

Moderator: Board moderators

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

### 442 - Matrix Chain Multiplication

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

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;

int main()
{

struct m matrix,first,second,tmp;
char str;
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
Contact:
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 .....

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

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

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

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
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 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!

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

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

char stack,nam;
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;
char str,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;
}

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:
thanx everybody
keep posting
Last edited by newton on Thu Mar 22, 2007 6:10 am, edited 1 time in total.

jainal cse du
New poster
Posts: 23
Joined: Thu Jul 27, 2006 2:43 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;
int top = 100;
int main()
{

struct m matrix;
long test,result,i,flag;
char ch,a,b,str;
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;
}

``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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
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;
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;
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
Contact:
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

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
Contact:
The second part of the input file strictly adheres to the following syntax (given in EBNF):
Missed that line. . You are correct.
Ami ekhono shopno dekhi...
HomePage

gba356
New poster
Posts: 15
Joined: Sat Apr 28, 2007 10:12 am
Location: Taiwan
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. 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.