11259. Minimum triangulation

You are given a regular polygon with  vertices numbered from 1 to n in counterclockwise order.

Triangulation of this polygon is a decomposition into triangles such that:

· each vertex of any triangle is a vertex of the original polygon;

· no two triangles have a positive-area intersection;

· the union of all triangles exactly covers the area of the original polygon.

The weight of a triangulation is defined as the sum of the weights of its triangles, where the weight of a triangle is the product of the labels of its vertices.

Find the minimum weight among all possible triangulations of the given polygon.

Input. One integer n (3 ≤ n ≤ 500) – the number of vertices of the polygon.

Output. Print the minimum weight among all triangulations of the given polygon.

Sample input 1	Sample output 1
3	6
Sample input 2	Sample output 2
4	18

SOLUTION

combinatorics

Algorithm analysis

Consider a triangle that contains the side (1, n). Let its third vertex be x, then the triangle has the form (1, n, x).

If x = n – 1, we simply remove the triangle (1, n, n – 1), after which an (n – 1) - gon remains, which we triangulate further.

If 1 < x < n – 1, consider the triangle (n, x, k), where x < k < n.

Replace the pair of triangles (1, x, n) and (n, x, k) with the pair (1, x, k) and (1, n, k). The total weight of the triangles decreases, since xn + xnk > xk + nk. After regrouping, we obtain

x(n – k) + nk(x – 1) > 0

The inequality holds because n – k > 0 and x – 1 > 0.

It follows that it is preferable to replace the triangle (1, x, n) with (1, k, n), where k > x. Therefore, the optimal choice is x = n – 1. The minimum weight triangulation is obtained by drawing all diagonals from vertex 1.

The sum of the weights of all triangles incident to vertex 1 is equal to

1 * 2 * 3 + 1 * 3 * 4 + … + 1 * (n – 1) * n =

Example

In the first test, the polygon is a triangle with vertices 1, 2, 3. Its weight is 1 * 2 * 3 = 6.

In the second test, the polygon is a square with vertices 1, 2, 3, 4. The minimum weight is achieved by the triangulation with the diagonal (1, 3):

1 * 2 * 3 + 1 * 3 * 4 = 6 + 12 = 18

Algorithm implementation

Read the input data.

scanf("%d", &n);

Compute the answer.

res = 0;

for (i = 2; i < n; i++)

res += 1ll * i * (i + 1);

Print the answer.

printf("%lld\n", res);