Polygon Triangulation

Problem Statement Summary Given a convex polygon with N vertices, each having a weight w_i, triangulate it (divide into N - 2 triangles using non-crossing diagonals) to maximize the total score. The score of triangle...

Updated May 21, 2026

Track IOI

Year 2004

Statement Not mirrored

TeXC++

Problem statement

Problem Statement

No standalone statement file is available for this entry.

Open TeX section

A separate statement file is not available for this entry, so the page focuses on the editorial and implementation.

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Problem Statement Summary

Given a convex polygon with $N$ vertices, each having a weight $w_i$, triangulate it (divide into $N - 2$ triangles using non-crossing diagonals) to maximize the total score. The score of triangle $(i, k, j)$ is $w_i \cdot w_k \cdot w_j$.

Solution: Interval DP

This is structurally identical to optimal matrix-chain multiplication.

Recurrence

Fix edge $(i, j)$. Any triangulation of the sub-polygon $i, i{+}1, \ldots, j$ includes exactly one triangle containing edge $(i, j)$, with some third vertex $k$ ($i < k < j$). This gives: \[ \mathrm{dp}[i][j] = \max_{i < k < j} \bigl(\mathrm{dp}[i][k] + \mathrm{dp}[k][j] + w_i \cdot w_k \cdot w_j\bigr). \] Base case: $\mathrm{dp}[i][i{+}1] = 0$ (an edge, no triangle). Answer: $\mathrm{dp}[0][N{-}1]$.

Theorem.

The interval DP correctly computes the optimal triangulation because every triangulation of a convex polygon is uniquely determined by the choice of third vertex for each edge's triangle, and the subproblems are independent.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<long long> w(N);
    for (int i = 0; i < N; i++) cin >> w[i];

    // dp[i][j] = max score of triangulating sub-polygon i..j
    vector<vector<long long>> dp(N, vector<long long>(N, 0));

    for (int len = 3; len <= N; len++) {
        for (int i = 0; i + len - 1 < N; i++) {
            int j = i + len - 1;
            dp[i][j] = LLONG_MIN;
            for (int k = i + 1; k < j; k++) {
                long long val = dp[i][k] + dp[k][j] + w[i] * w[k] * w[j];
                dp[i][j] = max(dp[i][j], val);
            }
        }
    }

    cout << dp[0][N - 1] << "\n";
    return 0;
}

Complexity Analysis

Time: $O(N^3)$. Three nested loops: interval length, start position, and split point.
Space: $O(N^2)$.
For $N \le 500$ this runs comfortably. If the polygon is given as a ring (any edge can be the base), ``break the ring'' by fixing one edge or by considering all $N$ rotations.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

// IOI 2004 - Polygon
// Triangulate a convex polygon to maximize total score.
// Score of triangle (i,k,j) = w[i] * w[k] * w[j].
// Classic interval DP, O(N^3).
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<long long> w(N);
    for (int i = 0; i < N; i++) cin >> w[i];

    if (N < 3) { cout << 0 << "\n"; return 0; }

    // dp[i][j] = max score triangulating sub-polygon i..j
    vector<vector<long long>> dp(N, vector<long long>(N, 0));

    for (int len = 3; len <= N; len++) {
        for (int i = 0; i + len - 1 < N; i++) {
            int j = i + len - 1;
            dp[i][j] = LLONG_MIN;
            for (int k = i + 1; k < j; k++) {
                long long val = dp[i][k] + dp[k][j] + w[i] * w[k] * w[j];
                dp[i][j] = max(dp[i][j], val);
            }
        }
    }

    cout << dp[0][N - 1] << "\n";
    return 0;
}

Show raw files

TeX write-upcompetitive_programming/ioi/2004/polygon/solution.texC++ implementationcompetitive_programming/ioi/2004/polygon/solution.cpp