UVA - 13141 - Growing Trees

This article will explain my thought process to solve a problem called Growing Trees (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Recurrence Relation, Dynamic Programming

Objective

Given:

Level of a tree.
Rules for branching:
1. No branching at level 1.
2. After branching, one of the subtree must branch again while the other can skip it.
3. After skipping a branching, the subtree must branch.

We want to:

Find the number of leaves.

Glossary

Recurrence Relation — A mathematical expression that defines a sequence in terms of its previous terms.
Dynamic Programming (DP) — A method used to solve complex problems by breaking them into smaller overlapping subproblems and storing their results to avoid recomputation.

Observation

We could model the branching process as a recurrence relation.

T(l, b) = \begin{cases} 1 & l = 0 \\ T(l-1,1) & b = 0 \\ T(l-1,0) + T(l-1,1) & b = 1 \end{cases}

The equation above describes the branching process. T(l,b) is a function to calculate total leaves, l is the remaining levels, and b is the decision for branching or not.

From the recurrence relation above, we could see that the number of branch depends on the remaining level and the branching decision, which indicate that we could use DP approach to store the state (remaining level and branching decision) and the result (total leaves) to avoid recomputation of the known state.

Algorithm

The DP on this problem can be implemented using a top-down approach, which means we can start by implementing the equation as a recursive function. Since the state is composed of 2 information, remaining level and branching decision, we could store it in a 2 dimensional array.

The time complexity of this solution is O({total levels} * 2) or O(10^2).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 13141 - Growing Trees
 * Time limit: 1.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=5052
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        while (in.hasNextInt()) {
            final Input input = new Input();
            input.level = in.nextInt();
            if (input.isEOF()) break;

            final Output output = process.process(input);
            out.println(output.totalLeaves);
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public int level;

    public boolean isEOF() {
        return level == 0;
    }
}

class Output {
    public long totalLeaves;
}

class Process {
    private final long[][] dp = new long[85][2];

    public Output process(final Input input) {
        final Output output = new Output();
        output.totalLeaves = getTotalLeaves(input.level - 1, false);
        return output;
    }

    private long getTotalLeaves(final int remainingLevel, final boolean mustBranch) {
        if (remainingLevel == 0) {
            return 1;
        }

        final boolean unknown = dp[remainingLevel][mustBranch ? 1 : 0] == 0;
        if (unknown) {
            if (mustBranch) {
                final long total1 = getTotalLeaves(remainingLevel - 1, true);
                final long total2 = getTotalLeaves(remainingLevel - 1, false);
                final long total = total1 + total2;
                dp[remainingLevel][1] = total;
            } else {
                final long total = getTotalLeaves(remainingLevel - 1, true);
                dp[remainingLevel][0] = total;
            }
        }

        return dp[remainingLevel][mustBranch ? 1 : 0];
    }
}