## Editorial for IOI '94 P1 - The Triangle

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Let us introduce some notation to formalize the problem. The triangle consists of rows with . We number the rows of the triangle from top to bottom starting at , and the positions in each row from left to right also starting at . The number appearing in row at position is denoted by where and . There are numbers in the triangle. This amounts to numbers in the largest possible triangle (). The numbers are in the range from to .

A route starts with . For , a route may step from to either or . It ends in some with . Thus, a route visits numbers in steps. At each step in a route, there are two possible ways to go. Hence, there are routes in the triangle. The largest possible triangle () has routes. This is a huge number close to . The smallest value for a route sum is zero, and the largest value is , which is less than .

Our first design decision concerns the input data. Two approaches are possible:

- Read all input data at the beginning of the program and store it internally for later use.
- Process the input data while reading it, without ever storing all of it together.

Because the amount of input data is not so large (at most small numbers), it is easy to store all of it in program variables. Our first three programs start by reading all input data. In the fourth program, we illustrate the other approach.

For , the problem is easy because there is only one route. In that case, the maximum route sum equals . For , there are two types of routes: half of the routes turn left on the first step from the top, and the other half goes to the right. Each route sum equals *plus* the sum over the route continuing from when turning left, or from when turning right. Therefore, the maximum route sum equals *plus* the maximum of the sums over routes starting either in or in . Determining the maximum sum for routes starting in is the same problem for a smaller triangle.

#### Program 1

It is now easy to write a *recursive* function, say `MaxRS`

, that computes the maximum route sum from an arbitrary position in the triangle:

```
function MaxRS(r, p: index): integer ;
{ return maximum sum over all down routes starting in T[r, p] }
begin
if r = N then MaxRS := T[r, p]
else MaxRS := T[r, p] + Max(MaxRS(r+1, p), MaxRS(r+1, p+1))
end { MaxRS } ;
```

The invocation `MaxRS(1, 1)`

then solves the problem. However, this program passes the first three or four tests only. For a triangle with rows, the number of routes is simply too large (more than ) to be investigated in 30 seconds. You can eliminate the separate function `Max`

(for computing the maximum of two numbers) by writing it out into the body of function `MaxRS`

, but that will not help (enough).

This problem was included precisely because it is tempting to use recursion. The 'plain' recursive solution was intended to fail (on some of the tests).

#### Program 2

There is a standard technique to speed up such a recursive program, known by names such as *dynamic programming*, *tabulation*, *memoization*, and *memoing*. Whenever the function `MaxRS`

is called with actual parameters and for the first time, the result is computed and memoized in a table, say as . For every subsequent invocation of `MaxRS`

with these same parameters and , the result is not recomputed, but simply retrieved from the table as .

We introduce a table `MRS`

that is initialized at to indicate that the results are not yet known (note that all route sums are at least ). The function `MaxRS`

can be modified as follows:

```
function MaxRS(r, p: index): integer ;
{ return maximum sum over all down routes starting in T[r, p] }
begin
if MRS[r, p] = -1 then
if r = N then MRS[r, p] := T[r, p]
else MRS[r, p] := T[r, p] + Max(MaxRS(r+1, p), MaxRS(r+1, p+1)) ;
MaxRS := MRS[r, p]
end { MaxRS } ;
```

It is still a simple program and now it is also fast enough, because not all routes are followed completely. A disadvantage of this solution is that it requires additional storage for the table. In fact, Program 2 uses at least twice the amount of data memory compared to Program 1 (such a trade-off between speed and memory usage is a common dilemma). You can squeeze the table into the upper-right triangle of the square array, but that would complicate the program needlessly.

#### Program 3

When program 2 is analyzed a bit further, it becomes clear that table `MRS`

is filled in a particular order. Assuming that in the call `Max(E, F)`

, expression is, for instance, always evaluated before , the recursion pattern turns out to be very regular. Filling starts at the lower-left corner and continues from the bottom in diagonals slanting upward to the left. For five rows, the order is:

```
15
10 14
6 9 13
3 5 8 12
1 2 4 7 11
```

It is now a small step to come up with a program that fills table `MRS`

in a non-recursive way. Furthermore, this can be done in a more convenient order, say row by row from the bottom. That is, for five rows in the order:

```
15
13 14
10 11 12
6 7 8 9
1 2 3 4 5
```

The following procedure computes `MRS`

non-recursively (also called *iteratively*):

```
procedure ComputeAnswer ;
{ m := the maximum route sum }
var r, p: index ;
begin
for r := N downto 1 do
for p := 1 to r do
if r = N then MRS[r, p] := T[r, p]
else MRS[r, p] := T[r, p] + Max(MRS[r+1, p], MRS[r+1, p+1]) ;
m := MRS[1, 1]
end { ComputeAnswer } ;
```

(Of course, you can eliminate the if-statement by introducing a separate -loop for , but the program is fast enough as it is and better to understand this way.) Observe that each number is now inspected exactly once. Therefore, we do not need a separate table for storing `MRS`

if we put at . The type of `T`

must be adjusted because the input `T`

-values are numbers in the range , but `MRS`

-values possibly not.

#### Program 4

In Program 3, all input data must still be read and stored before the actual computation starts, because `MRS`

is computed from bottom to top. Routes in the triangle can, however, also be considered from bottom to top by flipping the direction. If we take that point of view, then we can say that:

- a route starts somewhere on the base at for ;
- it steps upward either left or right (on the boundary there is no choice), that is, from , with and , it may step to if , and to if ;
- it always terminates at .

We now redefine as the maximum sum over all *up*-routes starting in . The final answer is then obtained as the maximum value among with . The following recurrent relationships hold for `MRS`

:

- if
- if and
- if

The case distinction can be avoided by defining for or or . We then simply have:

`MRS`

can be computed iteratively from top to bottom. Therefore it is not even necessary to store all input values. Only one row of `MRS`

needs to be stored. From this row and an input row, the next row of `MRS`

is computed (this computation is a little tricky). The final answer is the maximum of the last row computed.

## Comments