OrderDoesMatter
SRM 298 · 2006-04-11 · by soul-net
SRM 298 · 2006-04-11 · by soul-net · Graph Theory, Greedy, Simple Search, Iteration
Problem Statement
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:
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.
- You can only multiply them if B is equal to C.
- The resultant matrix is of size AxD.
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.
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
Submissions are judged against all 157 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class OrderDoesMatter with a public method int getOrder(vector<int> N, vector<int> M) · 157 test cases · 2 s / 256 MB per case