442 - Matrix Chain Multiplication

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

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

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

[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)

[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 what 's the problem?

[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)

[brianfry713]

Input:

Code: Select all

2
A 1 2
B 3 1
(AB)

AC output:

Code: Select all

error