Time Limit: Java: 2000 ms / Others: 2000 ms
Memory Limit: Java: 65536 KB / Others: 65536 KB
Given two arrays A and B, we can determine the array C = A B using the standard definition of matrix multiplication:
The number of columns in the A array must be the same as the number of rows in the B array. Notationally, let's say that rows(A) and columns(A) are the number of rows and columns, respectively, in the A array. The number of individual multiplications required to compute the entire C array (which will have the same number of rows as A and the same number of columns as B) is then rows(A) columns(B) columns(A). For example, if A is a 10 x 20 array, and B is a 20 x 15 array, it will take 10 x 15 x 20, or 3000 multiplications to compute the C array.
To perform multiplication of more than two arrays we have a choice of how to proceed. For example, if X, Y, and Z are arrays, then to compute X Y Z we could either compute (X Y) Z or X (Y Z). Suppose X is a 5 x 10 array, Y is a 10 x 20 array, and Z is a 20 x 35 array. Let's look at the number of multiplications required to compute the product using the two different sequences:
(X Y) Z
5 x 20 x 10 = 1000 multiplications to determine the product (X Y), a 5 x 20 array.
Then 5 x 35 x 20 = 3500 multiplications to determine the final result.
Total multiplications: 4500.
X (Y Z)
10 x 35 x 20 = 7000 multiplications to determine the product (Y Z), a 10 x
Then 5 x 35 x 10 = 1750 multiplications to determine the final result.
Total multiplications: 8750.
Clearly we'll be able to compute (X Y) Z using fewer individual multiplications.
Given the size of each array in a sequence of arrays to be multiplied, you are to determine an optimal computational sequence. Optimality, for this problem, is relative to the number of individual multiplcations required.
Case 1: (A1 x (A2 x A3)) Case 2: ((A1 x A2) x A3) Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))