PROBLEM LINK:
Cassandra is Playing with Polygons
Setter: sayan_kashyapi
Tester: debrc
Editorialist: sayan_kashyapi
DIFFICULTY:
Medium
PREREQUISITES:
Catalan Numbers
PROBLEM:
You are given a polygon with N vertices labelled from 1 to N in clockwise order. You have to return the two values, the number of possible triangulation and the weight of the minimum triangulation. The weight of a triangulation is basically the sum of weights of triangles it consists of, where the weight of a triangle is denoted as the product of the labels of its vertices.
EXPLANATION
The total number of ways of triangulation = C_{(N - 2)}.
For better understanding of how to find out the minimum weight triangulation follow the image and dry run the code. In the code catalanNumber() function is used to calculate the Nth Catalan Number and minScoreTriangulation() function is used to find out the minimum score triangulation.
TIME COMPLEXITY
Time complexity is O(N^2) for each test case.
SOLUTIONS:
Setter's Solution
C++17
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;
using namespace std;
const int MOD = 1000000007;
void catalanNumber(int n)
{
cpp_int cat_ = 1;
for (cpp_int i = 1; i <= n; i++)
{
cat_ *= (4 * i - 2);
cat_ /= (i + 1);
}
cout << (cat_) % MOD << " ";
}
int minScoreTriangulation(vector<int>& A) {
int n = A.size();
vector<vector<int>>dp(n, vector<int>(n, 0));
for (int L = 3; L <= n; L++)
for (int i = 0; i < n - L + 1; i++) {
int j = i + L - 1;
dp[i][j] = INT_MAX;
for (int k = i + 1; k < j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + (A[i] * A[k] * A[j]) );
}
return dp[0][n - 1];
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> A;
for (int i = 1; i <= n; i++)
A.push_back(i);
catalanNumber(n - 2);
cout << minScoreTriangulation(A) << endl;
}
}
Tester's Solution
PYPY3
import math,sys
MAX=1001
MOD=1000000007
INT_MAX=sys.maxsize
dp=[0 for _ in range(MAX)]
def precompute():
dp[0]=1
for i in range(1,MAX):
dp[i] = 0
for j in range(0,i):
dp[i]=(dp[i]+(dp[j]*dp[i-j-1])%MOD)%MOD
def minScoreTriangulation(A):
n=len(A)
dp=[[0 for _ in range(n)] for _ in range(n)]
for L in range(3,n+1):
for i in range(0,n-L+1):
j=i+L-1
dp[i][j]=INT_MAX
for k in range(i+1,j):
dp[i][j] = min(dp[i][j],(dp[i][k]+dp[k][j]+(A[i]*A[k]*A[j])))
return dp[0][n-1]
precompute()
for _ in range(int(input())):
n=int(input())
a=[i for i in range(1,n+1)]
print(dp[n-2],minScoreTriangulation(a))
Python3.6
import math,sys
MAX=1001
MOD=1000000007
INT_MAX=sys.maxsize
dp=[0 for _ in range(MAX)]
def precompute():
dp[0]=1
for i in range(1,MAX):
dp[i] = 0
for j in range(0,i):
dp[i]=(dp[i]+(dp[j]*dp[i-j-1])%MOD)%MOD
def minScoreTriangulation(A):
n=len(A)
dp=[[0 for _ in range(n)] for _ in range(n)]
for L in range(3,n+1):
for i in range(0,n-L+1):
j=i+L-1
dp[i][j]=INT_MAX
for k in range(i+1,j):
dp[i][j] = min(dp[i][j],(dp[i][k]+dp[k][j]+(A[i]*A[k]*A[j])))
return dp[0][n-1]
precompute()
for _ in range(int(input())):
n=int(input())
a=[i for i in range(1,n+1)]
print(dp[n-2],minScoreTriangulation(a))
Feel free to Share your approach.
Suggestions are welcomed as always had been.