442 - Matrix Chain Multiplication

[udvat]

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

[murkho]

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]

Change

Code: Select all

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

to

Code: Select all

if( isupper(str[i]))

Best of luck

[murkho]

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]

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

[the LA-Z-BOy]

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

[rhsumon]

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

[newton]

thanx everybody
keep posting

[jainal cse du]

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]

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.

[el_vitucho]

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);
	}


}

[Jan]

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.

[Darwish]

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]

The second part of the input file strictly adheres to the following syntax (given in EBNF):

Missed that line. . You are correct.

[gba356]

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?