I don't know where i made the mistake

So i have an exercise where when i put the wrong input for the number of matrixes it shows me the correct output. But i want while i put the correct input to show the correct answer. Here is my exercise:
Problem P: The problem of matrix multiplication
It is necessary to multiply n matrices M1 × M2 × M3 × ... × Mn. The dimensions of the matrices are known and given: r0, r1, r2, ... rn. The matrix Mi has dimensions ri-1 × ri.

Find the smallest possible number of elementary operations of multiplication of matrix elements, necessary for computing the above product.

Input
The first line of the standard input stream contains the number of test cases T.

Each test case consists of two lines.

The first line contains the number of matrices n (1 ≤ n ≤ 100).

The second line contains n + 1 natural numbers r0, r1, r2, ... rn are the sizes of the matrices. The numbers are separated by one space and lie in the range from 1 to 100.

Output
For each test case, print a minimal number of elementary operations of multiplication of matrix elements in a separate line.

Examples:
OUTPUT:
2
3// Here is where i have the problem the correct one is 3 but the output will show me 5000 but if enter 4 then it will show me the correct answer.
10 100 5 50
4//Same for here insted of 4 the number 5 is working even though there are actually 4 matrixes and not 5.
10 20 50 1 100

INPUT:
7500
2200
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
  #include<limits.h>
#include <iostream>
using namespace std;

int MinOperations(int r[], int n)
{
	int dp[n][n];
	int i, j, k, l, q;
	for (i = 1; i < n; i++)
    {
		dp[i][i] = 0;
    }
	for (l = 2; l <= n; l++)
	{
		for (i = 1; i <= n-l + 1; i++)
		{
			j = i + l - 1;
			dp[i][j] = INT_MAX;
			for (k = i; k < j; k++)
			{
				q = dp[i][k] + dp[k+1][j] + r[i-1]*r[k]*r[j];
				if (q < dp[i][j])
					dp[i][j] = q;
			}
		}
	}

	return dp[1][n - 1];
}
int main()
{

int T;
cin >> T;
while ( T--)
{


    int n;
    cin >> n;
	int arra[100];
	for ( int  i = 0 ; i < n; i++)
	{
	    cin >> arra[i];
	}
	cout <<	MinOperations(arra, n ) << endl;
}
	return 0;
}
Last edited on
Well, consider this before your proceed (assuming my 2 second google is correctly finding the best algorithm) ..

The fastest known matrix multiplication algorithm is Coppersmith-Winograd algorithm...

You appear to be using a N*N*N brute force multiply which is never going to get you the correct answer.

Also, why are you doing the multiply anyway? You should be able to compute the operations without doing the work...?



Hello jonnin i am doing the multiply because this is the formula which i use in order to get the answer i want i multiply the sizes of the matrixs in order to get the "smallest possible number of elementary operations of multiplication of matrix elements" and it is also part of the code that our teacher gave us during his lesson .
OK. It is'nt the smallest # of operations, its the brute force algorithm, but we can pretend :)

So I am not seeing it. What variable is totaling the # of operations performed? Its not dp; dp is assigned q and q is not a count, its a computation based off the data in the matrices.

it seems to me the innermost loop should be a counter. Depends on what you call an elementary operation, I assume that means "multiply or add" in this case, in which case every inner loop is doing 2 multiplies and 2 adds, so the inner loop should do a += 4 every iteration to some counter (???).

Which again is N*N*(something)*4. Figuring out the something ... only if you want to do that... the inner loop is bounded by i and k which vary based off the outer loops so its a little trouble to unravel what that number is.
Last edited on
Registered users can post here. Sign in or register to post.