title: Detecting when matrix multiplication is possible
body: <p>Here is an interesting problem that I encountered in a programming competition:</p>
  
  <p><strong>Problem statement:</strong> Given the dimensions of <code>n</code> matrices, determine if there exists an ordering such that the matrices can be multiplied. If there exists one, print out the size (product of the dimensions) of the resultant matrix.</p>
  
  <p><strong>My observations:</strong> This reduces to the NP-complete hamiltonian path problem if you consider each matrix as a vertex and draw a directed edge between matrices that can be multiplied. I solved this by simply brute-forcing the problem but this is clearly very slow. I was wondering if there are any clever optimizations for this particular instance of the problem.</p>