OJ Board

The Online Judge board
https://onlinejudge.org/board/

442 - Matrix Chain Multiplication

https://onlinejudge.org/board/viewtopic.php?t=5818

Page 2 of 2

Posted: Thu Oct 25, 2007 10:02 pm
by Jan
Try changing two things..

1. Split the input procedure

Code: Select all

for( int i=0;i<n;i++ ) 
{
    cin>>c;
    cin>>m[c].row>>m[c].col; 
}
2. Define an integer stack...

Code: Select all

stack<int> stk;
Hope these help.

Re: 442-matrix chain multiplication

Posted: Fri May 13, 2011 11:23 am
by Shafaet_du
You should get AC if you can pass the samples. However the answers can be large,so use long long for safety. Parsing is fairly easy,push matrixes and "(" in stack. if you get ")" pop last 3 elements. Last 2 are matrixes and 3rd is "(". Determine dimension of new matrix and push it. The syntax given in problem description ensures that you wont get rte using this technique.

runtime Error

Posted: Wed Mar 07, 2012 11:14 pm
by valeriAsus
Hi,I've run time error for this code:

Code: Select all



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class MainSt{
   	      
	       public static void main(String[] args) throws Exception{
		   	LeggiDaInput L=new LeggiDaInput();
            L.AllocaHashMapEriempi();
            L.LeggiCalcolaEspr(); 
            L.StampaCalcoli();
           }
	
   static class GestioneInfoMatrici{
    	  private int Righe;             
	  	  private StringTokenizer st;
	  	  private HashMap<String,Info>MatriciInput;   
	  	  private HashMap<String, Info>MatriciProd;
	  	  private Info I;
	  	    
	     GestioneInfoMatrici(int r) {
	          st=null;   Righe=r;    MatriciInput= new HashMap<String, Info>(r);   I=null; MatriciProd= new HashMap<String, Info>(1);
	     }	    
	  	    
	  	     void PosizionaInHashMap(String r){
        	   st=new StringTokenizer(r," ");
	             String K=st.nextToken();
                int nR =Integer.parseInt(st.nextToken());
                int nC =Integer.parseInt(st.nextToken());
                   I=new Info(nR, nC); 	 
                   MatriciInput.put(K,I);
	  	    }

	        Info getInfoSuM(String  k){   
	        	if(k.charAt(0)!='i')
	             return  (Info) MatriciInput.get(k);
	              
	                 return (Info) MatriciProd.get(k); 
	        }
	          
	           void InserInHashMap(String k,Info I){
	                MatriciProd.put(k,I);
	          }
	          
	          void SvuotaHashMap(){
	         MatriciProd.clear();  	  
	         } 
	  }            
	

    static class LeggiDaInput {
	    
		private  Info matrCalcolata;   
		private  GestioneInfoMatrici G;
		private int numM, numProd;
		private  String riga;
		private  BufferedReader in_Str=new BufferedReader(new InputStreamReader(System.in));
		private  StringTokenizer st;
		private int valore;
		private LinkedList<Integer> ProdMatrici;
		private  Matcher matcher;
		private  Pattern patternRiga = Pattern.compile("\\([A-Z0-9i]+\\)");
		private  Pattern patternP = Pattern.compile("[A-Z]{1}|i{1}[0-9]+i{1}");

	  	     LeggiDaInput() {
	  	     numM=0; riga=""; st=null;  numProd=0; G=new GestioneInfoMatrici(0);  
	         ProdMatrici= new LinkedList<Integer>(); matcher=null;
	  	}
	  	
	  	       void AllocaHashMapEriempi()throws Exception{
	  		  riga=in_Str.readLine();
	  		  numM=Integer.parseInt(riga);
	  		     
	  		      G=new GestioneInfoMatrici(numM); 
	          while(numM>0){
	           riga=in_Str.readLine() ;
	  		 G.PosizionaInHashMap(riga);
	              numM--;   
	         }    
	    }   
	  		
	  void LeggiCalcolaEspr() throws IOException{
		 
		   do{
	  	   numProd=0;
	  	   int kB=0;
           boolean errore=false;
	  	   riga=in_Str.readLine();
	  	   
	  	   if(riga.equals(null) || riga.length()==0)
	  		     //break;
	  	    
			  	       if(riga.length()>1){ 
			  	    	     while( (matcher=patternRiga.matcher(riga)).find()){
			      	        	    String chiave =  "i"+kB+++"i";
			      	        	     if(!VerificaEcalcoloBlocco(matcher.group(),chiave) ){
			  						   errore =true;	
			  			    		    break ; 
			  						  }
		   	  			      riga = riga.replaceFirst(patternRiga.pattern(),chiave);
			  	    	     }
			  		   } 
			   if(!errore)
	  	           ProdMatrici.add(numProd);
	           else
	        	   ProdMatrici.add(-1); 
	  	   
			   
	  		   G.SvuotaHashMap();
	  	 }while(true);  	
	   
	  }
	  	
	   boolean VerificaEcalcoloBlocco(String Par,String k){
	      	Matcher matcher2 = patternP.matcher(Par); 
	  		     boolean unaVolta=false;
	           
	  	  while(matcher2.find()){                                                  
	          String str=matcher2.group();
		  /*	  
		  	      if( str.charAt(0)=='°' && !solo1volta){                                                                      
		  	    	   k=str;
		  	    	   System.out.println("chiave da cambiare---> "+str);  
		  	      } 
		  */
		  	         if(!unaVolta){
		  			    matrCalcolata= new Info( G.getInfoSuM(str).getRiga(), G.getInfoSuM(str).getCol() );
		  			    unaVolta=true;
		  	         }
		  		 else{   
		  		         if( matrCalcolata.getCol()!= G.getInfoSuM(str).getRiga() ) 
		  		 	               return false;
		  			           
		  			   numProd+= matrCalcolata.getRiga()*(matrCalcolata.getCol()*G.getInfoSuM(str).getCol());
		  			   matrCalcolata.setCol( G.getInfoSuM(str).getCol()) ;
		  		}
		  	  
		  	 }
	             		 G.InserInHashMap(k,matrCalcolata);   
	             return true;
	  }
	      
	   void StampaCalcoli(){
	  		  for(int i=0; i<ProdMatrici.size() ; i++){
	  		     if(ProdMatrici.get(i)==-1)
	  		    		   System.out.println("error");
	  		    	  else
	  		               System.out.println(ProdMatrici.get(i));
	  		  }
		 }
}
	
	 static   class Info {
			private int Righe,Col;
			
			 Info(int r,int c){
		       Righe=r;  Col=c;		
			}
			int getRiga(){ return Righe;  }
			int getCol(){  return Col;    }
			
	  		void setRiga(int r){Righe=r;  }
			void setCol(int c){ Col=c;    } 	
		}
	  
      
}
this is the email that I've receveid:
Your submission with number 9829025 for the problem 442 - Matrix Chain Multiplication has failed with verdict Runtime error.
This means that the execution of your program didn't finish properly. Remember to always terminate your code with the exit code 0.
Please,You can help me?? :oops:

Re: runtime Error

Posted: Thu Mar 08, 2012 2:29 am
by brianfry713
http://ideone.com/3EUct

Exception in thread "main" java.lang.NullPointerException
at MainSt$LeggiDaInput.LeggiCalcolaEspr(Main.java:95)
at MainSt.main(Main.java:15)

Your RE is in this line before any output is generated:
if(riga.equals(null) || riga.length()==0)

Re: runtime Error

Posted: Thu Mar 08, 2012 10:00 am
by valeriAsus
it's not this the error,I've put on the site correctly this code:

Code: Select all


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Main{
   	      
	       public static void main(String[] args) throws Exception{
		   	LeggiDaInput L=new LeggiDaInput();
            L.AllocaHashMapEriempi();
            L.LeggiCalcolaEspr(); 
            L.StampaCalcoli();
           }
	
   static class GestioneInfoMatrici{
    	  private int Righe;             
	  	  private StringTokenizer st;
	  	  private HashMap<String,Info>MatriciInput;   
	  	  private HashMap<String, Info>MatriciProd;
	  	  private Info I;
	  	    
	     GestioneInfoMatrici(int r) {
	          st=null;   Righe=r;    MatriciInput= new HashMap<String, Info>(r);   I=null; MatriciProd= new HashMap<String, Info>(1);
	     }	    
	  	    
	  	     void PosizionaInHashMap(String r){
        	   st=new StringTokenizer(r," ");
	             String K=st.nextToken();
                int nR =Integer.parseInt(st.nextToken());
                int nC =Integer.parseInt(st.nextToken());
                   I=new Info(nR, nC); 	 
                   MatriciInput.put(K,I);
	  	    }

	        Info getInfoSuM(String  k){   
	        	if(k.charAt(0)!='i')
	             return  (Info) MatriciInput.get(k);
	              
	                 return (Info) MatriciProd.get(k); 
	        }
	          
	           void InserInHashMap(String k,Info I){
	                MatriciProd.put(k,I);
	          }
	          
	          void SvuotaHashMap(){
	         MatriciProd.clear();  	  
	         } 
	  }            
	

    static class LeggiDaInput {
	    
		private  Info matrCalcolata;   
		private  GestioneInfoMatrici G;
		private int numM, numProd;
		private  String riga;
		private  BufferedReader in_Str=new BufferedReader(new InputStreamReader(System.in));
		private  StringTokenizer st;
		private int valore;
		private LinkedList<Integer> ProdMatrici;
		private  Matcher matcher;
		private  Pattern patternRiga = Pattern.compile("\\([A-Z0-9i]+\\)");
		private  Pattern patternP = Pattern.compile("[A-Z]{1}|i{1}[0-9]+i{1}");

	  	     LeggiDaInput() {
	  	     numM=0; riga=""; st=null;  numProd=0; G=new GestioneInfoMatrici(0);  
	         ProdMatrici= new LinkedList<Integer>(); matcher=null;
	  	}
	  	
	  	       void AllocaHashMapEriempi()throws Exception{
	  		  riga=in_Str.readLine();
	  		  numM=Integer.parseInt(riga);
	  		     
	  		      G=new GestioneInfoMatrici(numM); 
	          while(numM>0){
	           riga=in_Str.readLine() ;
	  		 G.PosizionaInHashMap(riga);
	              numM--;   
	         }    
	    }   
	  		
	  void LeggiCalcolaEspr() throws IOException{
		 
		   do{
	  	   numProd=0;
	  	   int kB=0;
           boolean errore=false;
	  	   riga=in_Str.readLine();
	  	   
	  	   if(riga.equals(null) || riga.length()==0)
	  		     break;
	  	    
			  	       if(riga.length()>1){ 
			  	    	     while( (matcher=patternRiga.matcher(riga)).find()){
			      	        	    String chiave =  "i"+kB+++"i";
			      	        	     if(!VerificaEcalcoloBlocco(matcher.group(),chiave) ){
			  						   errore =true;	
			  			    		    break ; 
			  						  }
		   	  			      riga = riga.replaceFirst(patternRiga.pattern(),chiave);
			  	    	     }
			  		   } 
			   if(!errore)
	  	           ProdMatrici.add(numProd);
	           else
	        	   ProdMatrici.add(-1); 
	  	   
			   
	  		   G.SvuotaHashMap();
	  	 }while(true);  	
	   
	  }
	  	
	   boolean VerificaEcalcoloBlocco(String Par,String k){
	      	Matcher matcher2 = patternP.matcher(Par); 
	  		     boolean unaVolta=false;
	           
	  	  while(matcher2.find()){                                                  
	          String str=matcher2.group();
		  /*	  
		  	      if( str.charAt(0)=='°' && !solo1volta){                                                                      
		  	    	   k=str;
		  	    	   System.out.println("chiave da cambiare---> "+str);  
		  	      } 
		  */
		  	         if(!unaVolta){
		  			    matrCalcolata= new Info( G.getInfoSuM(str).getRiga(), G.getInfoSuM(str).getCol() );
		  			    unaVolta=true;
		  	         }
		  		 else{   
		  		         if( matrCalcolata.getCol()!= G.getInfoSuM(str).getRiga() ) 
		  		 	               return false;
		  			           
		  			   numProd+= matrCalcolata.getRiga()*(matrCalcolata.getCol()*G.getInfoSuM(str).getCol());
		  			   matrCalcolata.setCol( G.getInfoSuM(str).getCol()) ;
		  		}
		  	  
		  	 }
	             		 G.InserInHashMap(k,matrCalcolata);   
	             return true;
	  }
	      
	   void StampaCalcoli(){
	  		  for(int i=0; i<ProdMatrici.size() ; i++){
	  		     if(ProdMatrici.get(i)==-1)
	  		    		   System.out.println("error");
	  		    	  else
	  		               System.out.println(ProdMatrici.get(i));
	  		  }
		 }
}
	
	 static   class Info {
			private int Righe,Col;
			
			 Info(int r,int c){
		       Righe=r;  Col=c;		
			}
			int getRiga(){ return Righe;  }
			int getCol(){  return Col;    }
			
	  		void setRiga(int r){Righe=r;  }
			void setCol(int c){ Col=c;    } 	
		}
	  
      
}
but I've runtime error :cry: what 's the problem?

Re: runtime Error

Posted: Fri Mar 09, 2012 12:06 am
by brianfry713
I'm still seeing the same RE on the same line.
Instead of: if(riga.equals(null) || riga.length()==0)
use: if(riga==null || riga.length()==0)

Re: 442-matrix chain multiplication

Posted: Tue Oct 15, 2013 8:07 pm
by brianfry713
Input:

Code: Select all

2
A 1 2
B 3 1
(AB)
AC output:

Code: Select all

error
All times are UTC+02:00
Page 2 of 2

Powered by phpBB® Forum Software © phpBB Limited