Competitive Programming

IOI 1994 - The Triangle

Problem Statement Given a triangle of n rows of positive integers, find a path from the top to the bottom such that the sum of the numbers along the path is maximized. At each step, you may move to the element directl...

Source sync Apr 19, 2026

Track IOI

Year 1994

Files TeX and C++

Folder competitive_programming/ioi/1994/triangle

IOI1994TeXC++

This page is built from the copied files in competitive_programming/ioi/1994/triangle. Edit competitive_programming/ioi/1994/triangle/solution.tex to update the written solution and competitive_programming/ioi/1994/triangle/solution.cpp to update the implementation.

The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.

Raw TeX Raw C++

Problem statement

Problem Statement

Rendered from the "Problem Statement" section inside solution.tex because this entry has no separate statement file.

Raw TeX

Given a triangle of $n$ rows of positive integers, find a path from the top to the bottom such that the sum of the numbers along the path is maximized. At each step, you may move to the element directly below or to the element directly below and one position to the right.

Example:

The maximum sum path is $7 \to 3 \to 8 \to 7 \to 5 = 30$.

Constraints: $1 \le n \le 100$, each element is between 0 and 99.

Editorial

Rendered from the copied solution.tex file. The original TeX source remains available below.

Raw TeX

Solution Approach

This is a classic dynamic programming problem. We define: \[ \text{dp}[i][j] = \text{maximum sum achievable from element } (i,j) \text{ down to the bottom row} \]

Base Case

For the bottom row $i = n-1$: \[ \text{dp}[n-1][j] = \text{val}[n-1][j] \]

Recurrence

For rows $i = n-2$ down to $0$: \[ \text{dp}[i][j] = \text{val}[i][j] + \max\!\big(\text{dp}[i+1][j],\;\text{dp}[i+1][j+1]\big) \]

Answer

The answer is $\text{dp}[0][0]$.

Why Bottom-Up?

Bottom-up DP avoids recursion overhead and is straightforward: we start from the last row and propagate maxima upward. The triangle can be modified in place, requiring no extra memory beyond the input array.

C++ Solution

#include <cstdio>
#include <algorithm>
using namespace std;

int tri[101][101];

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            scanf("%d", &tri[i][j]);

    // Bottom-up DP: modify triangle in place
    for (int i = n - 2; i >= 0; i--)
        for (int j = 0; j <= i; j++)
            tri[i][j] += max(tri[i + 1][j], tri[i + 1][j + 1]);

    printf("%d\n", tri[0][0]);
    return 0;
}

Complexity Analysis

Time complexity: $O(n^2)$. We visit each element of the triangle exactly once. The total number of elements is $\frac{n(n+1)}{2}$, so the work is $\Theta(n^2)$.
Space complexity: $O(n^2)$ for storing the triangle. Since we modify the triangle in place, no additional space is needed beyond the input. Alternatively, one could use a 1D array of size $n$ for a rolling approach, yielding $O(n)$ extra space.

C++ competitive_programming/ioi/1994/triangle/solution.cpp

Exact copied implementation source.

Raw file

// IOI 1994 - The Triangle
// Bottom-up DP: find max-sum path from top to bottom
// Time: O(n^2), Space: O(n^2)
#include <bits/stdc++.h>
using namespace std;

int tri[101][101];

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            scanf("%d", &tri[i][j]);

    // Bottom-up DP: modify triangle in place
    for (int i = n - 2; i >= 0; i--)
        for (int j = 0; j <= i; j++)
            tri[i][j] += max(tri[i + 1][j], tri[i + 1][j + 1]);

    printf("%d\n", tri[0][0]);
    return 0;
}

TeX write-up competitive_programming/ioi/1994/triangle/solution.tex

Exact copied write-up source.

Raw file

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{geometry}
\geometry{margin=2.5cm}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{hyperref}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\color{blue}\bfseries,
  commentstyle=\color{green!60!black},
  stringstyle=\color{red!70!black},
  numbers=left,
  numberstyle=\tiny\color{gray},
  numbersep=8pt,
  frame=single,
  breaklines=true,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 1994 -- The Triangle}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Statement}

Given a triangle of $n$ rows of positive integers, find a path from the top to the bottom
such that the sum of the numbers along the path is maximized.
At each step, you may move to the element directly below or to the element
directly below and one position to the right.

\medskip
\noindent\textbf{Example:}
\begin{verbatim}
        7
       3 8
      8 1 0
     2 7 4 4
    4 5 2 6 5
\end{verbatim}
The maximum sum path is $7 \to 3 \to 8 \to 7 \to 5 = 30$.

\medskip
\noindent\textbf{Constraints:} $1 \le n \le 100$, each element is between 0 and 99.

\section{Solution Approach}

This is a classic dynamic programming problem. We define:
\[
  \text{dp}[i][j] = \text{maximum sum achievable from element } (i,j) \text{ down to the bottom row}
\]

\subsection{Base Case}
For the bottom row $i = n-1$:
\[
  \text{dp}[n-1][j] = \text{val}[n-1][j]
\]

\subsection{Recurrence}
For rows $i = n-2$ down to $0$:
\[
  \text{dp}[i][j] = \text{val}[i][j] + \max\!\big(\text{dp}[i+1][j],\;\text{dp}[i+1][j+1]\big)
\]

\subsection{Answer}
The answer is $\text{dp}[0][0]$.

\subsection{Why Bottom-Up?}
Bottom-up DP avoids recursion overhead and is straightforward: we start from the last
row and propagate maxima upward. The triangle can be modified in place, requiring no
extra memory beyond the input array.

\section{C++ Solution}

\begin{lstlisting}
#include <cstdio>
#include <algorithm>
using namespace std;

int tri[101][101];

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            scanf("%d", &tri[i][j]);

    // Bottom-up DP: modify triangle in place
    for (int i = n - 2; i >= 0; i--)
        for (int j = 0; j <= i; j++)
            tri[i][j] += max(tri[i + 1][j], tri[i + 1][j + 1]);

    printf("%d\n", tri[0][0]);
    return 0;
}
\end{lstlisting}

\section{Complexity Analysis}

\begin{itemize}
  \item \textbf{Time complexity:} $O(n^2)$. We visit each element of the triangle exactly once.
        The total number of elements is $\frac{n(n+1)}{2}$, so the work is $\Theta(n^2)$.
  \item \textbf{Space complexity:} $O(n^2)$ for storing the triangle. Since we modify the
        triangle in place, no additional space is needed beyond the input.
        Alternatively, one could use a 1D array of size $n$ for a rolling approach,
        yielding $O(n)$ extra space.
\end{itemize}

\end{document}

C++ implementation competitive_programming/ioi/1994/triangle/solution.cpp

Exact copied implementation source.

Raw file

// IOI 1994 - The Triangle
// Bottom-up DP: find max-sum path from top to bottom
// Time: O(n^2), Space: O(n^2)
#include <bits/stdc++.h>
using namespace std;

int tri[101][101];

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            scanf("%d", &tri[i][j]);

    // Bottom-up DP: modify triangle in place
    for (int i = n - 2; i >= 0; i--)
        for (int j = 0; j <= i; j++)
            tri[i][j] += max(tri[i + 1][j], tri[i + 1][j + 1]);

    printf("%d\n", tri[0][0]);
    return 0;
}

IOI 1994 - The Triangle

Source-first archive entry

Problem Statement

Editorial

Solution Approach

Base Case

Recurrence

Answer

Why Bottom-Up?

C++ Solution

Complexity Analysis

Code

Source Files