TopCoder problem "OrderDoesMatter" used in SRM 298 (Division I Level Two)



Problem Statement

    Matrices are a common object in mathematics. A NxM matrix is basically a table with N rows of M values each. Given two matrices, one of size AxB and another of size CxD, the following multiplication rules apply:
  • You can only multiply them if B is equal to C.
  • The resultant matrix is of size AxD.
The number of elements in an AxB matrix is A multiplied by B. For example, a 3x7 matrix has 21 elements.

Given a list of matrices, determine if there's an ordering that allows you to multiply all of them. If multiple such orderings exist, choose the one where the result has the most elements. Return the number of elements in the result, or -1 if there is no valid ordering (see examples 0-3 for further clarification). The list of matrices is given as two int[]s, N and M, where the ith elements of N and M represent the number of rows and columns respectively of the ith matrix.
 

Definition

    
Class:OrderDoesMatter
Method:getOrder
Parameters:int[], int[]
Returns:int
Method signature:int getOrder(int[] N, int[] M)
(be sure your method is public)
    
 

Notes

-The association order is not important because we are only interested in the dimensions of the matrices.
 

Constraints

-M will have between 1 and 50 elements, inclusive.
-N and M will have the same number of elements.
-Each element of N and M will be between 1 and 1000, inclusive.
 

Examples

0)
    
{7,3,3}
{3,7,3}
Returns: 49
Here we can legally multiply all the matrices in three different ways:

(3x3)*(3x7)*(7x3) = (3x3) (elements = 9)

(3x7)*(7x3)*(3x3) = (3x3) (elements = 9)

(7x3)*(3x3)*(3x7) = (7x7) (elements = 49)

The maximum number of elements is then 49.
1)
    
{3,5,5}
{5,1,5}
Returns: 3
There's only one legal way to multiply the matrices (3x5)*(5x5)*(5x1)=(3x1) so the answer is 3*1=3.
2)
    
{3,5,5}
{5,2,4}
Returns: -1
There is no legal way to multiply the matrices.
3)
    
{5,2,3}
{2,5,3}
Returns: -1
Again, no legal way to multiply them all.
4)
    
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6157

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9819&pm=6157

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , radeye , Olexiy

Problem categories:

Graph Theory, Greedy, Simple Search, Iteration