Minimum Score

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
5 upvotes
Asked in companies
GoogleUberSwiggy

Problem statement

You are given an ‘N’ sided polygon. Every vertex of the polygon is assigned a value. The vertices are given in the form of an array of ‘N’ integers in clockwise direction.

You need to divide the polygon into ‘N - 2’ triangles. Each triangle has a triangle value. The triangle value is calculated by finding the product of its vertices.

Now, you need to find the minimum total triangle score. The total triangle score is the sum of the triangle scores of all the possible triangles.

Note: 
Note that a polygon can be divided into triangles in more than one way. You need to print the minimum sum of triangle values of all the triangles created.
Example : 
Given 'N' = 4, Array = [4, 3, 5, 2], the possible scores for these two triangle score are: (3 * 2 * 5) + (3 * 2 * 4) = 54 and (4 * 2 * 5) + (4 * 3 * 5) = 100.
The minimum of these two triangle scores is 54. So you need to print 54.

Example

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’ which denotes the number of test cases.

The first line of each test case contains a single integer ‘N’, denoting the vertices of the polygon.

The next line contains ‘N’ space-separated integers denoting the value of the vertices of the polygon.
Output Format: 
For each test case, you need to return the minimum triangle score possible from all triangles.

Print the output of each test case in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
3 <=  N  <= 50
1 <= ARR[i] <= 100

Where 'ARR[i]' denotes the Array elements that represent the sides of the polygon.

Time limit: 1 sec
Sample Input 1:
2
4
4 3 5 2
3
4 5 6
Sample Output 1:
54
120
Explanation of Sample Output 1:
In the first test case,'N' = 4, 'ARR' = [4, 3, 5, 2]. The possible scores for these two triangle score are: (3 * 2 * 5) + (3 * 2 * 4) = 54 and (4 * 2 * 5) + (4 * 3 * 5) = 100. The minimum of these two triangle scores is 54. So you need to print 54.

Example

In test case 2, we know only 1 triangle is possible and hence its triangle score will be 120.
Sample Input 2:
2
3
4 2 3
5
2 4 2 5 1
Sample Output 2:
24
26
Explanation of Sample Output 2:
In test case 1, Given 'N' = 3, 'ARR' = [4, 2, 3], the possible triangle score is: (4 * 2 * 3) = 24. So you need to print 24.

Example

In test case 2, Given 'N' = 5, 'ARR' = [2, 4, 2, 5, 1], the minimum of all the triangle scores is (1 * 2 * 4) + (1 * 4 * 2) + (1 * 2 * 5) = 26. So you need to print 26.

Example

Hint

Can you think of a recursion to make all the triangles using given sides?

Approaches (3)
Recursion

We can solve this problem by dividing it into smaller subproblems using recursion. We can divide the polygon recursively into three parts - one triangle and two sub polygons and we have to find the optimal way to divide this so that we will get a minimum triangle score. Let us say the starting and ending index of the given array is ‘i’ and ‘j’ , and ‘k’ is any index between ‘i+1’ and ‘j-1’  then we can divide this polygon into two polygons  A[ i…….k] + A[ k…….j] and a triangle formed by vertices i, j and k.

 

We will recursively divide all the polygons into sub polygons for all possible values of ‘ k ’ and return the minimum triangle score obtained.

 

The steps are as follows:

 

  • Let triangleScore('ARR', ‘i’, ‘j’) be our recursive function where ‘i’ and ‘j’ are the starting and ending index of vertices of the polygon.
  • If there are less than three vertices, we can not make a triangle from them so return 0.
  • Run a loop ‘k’ : ‘i’ + 1 to ‘j’ - 1
    • Return minimum value of ( INT_MAX ,triangleScore('ARR', ‘i’, 'k') + triangleScore('ARR', ‘k’, ‘j’) + triangleValue of triangle formed by vertices ‘i’, ‘j’ and 'k'.)
Time Complexity

O(N ^ (N - 3)), where ‘N’ is the number of sides in the polygon.

 

Since we are traversing through the complete array for ‘N’ - 3 times(until we reach an array having only 3 sides), the overall time complexity will be O(N ^ (N - 3)).

Space Complexity

O(1)

 

Since constant extra space is needed, so the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Minimum Score
Full screen
Console