UVA - 1738 - Ceiling Function

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

Keywords: Tree, Tree Traversal, In-Order Traversal

Problem Summary

Given:

Total ceilings.
Total levels for each ceiling.
List of ceilings.

We want to:

Find total shapes of the ceiling’s tree representation.

Glossary

Tree — A hierarchical data structure used to represent data in a parent-child relationship.
Tree Traversal — A process of visiting each node of a tree exactly once in a specific order.
In-Order Traversal — A process of visiting each node of a tree from left → root → right.

Observation

The relationship between each level of the ceiling can be modeled as a tree, where the ceiling’s level is the parent, the ceiling’s next lesser level is the left child, and the ceiling’s next greater level is the right child.

Once we’ve build the tree representation of each ceiling, we need to figure out how to determine the shape of the tree. We could do a tree traversal to get a rough idea on the shape of the tree. During the traversal, we must find a state that guarantee uniqueness of each node position, which in this case is the number of left/right decision that we took to reach each node from the root. Collectively, this traversal data can be used to identify the shape.

Algorithm

The tree on this problem can be classified as a binary tree, so that means we just need to store the reference to the left and right child node. The insertion process can be handled by traversing the tree node using the lesser/greater constraint.

Next, we need to traverse the tree to get the shape identifier. There are multiple ways to do this, but lets focus on in-order traversal. In this case, the sequence of the traversal is left child, root, right child. In each iteration, keep track with the number of left/right decision we’ve taken. Increment the left if we’re traversing the left child, and increment the right if we’re traversing the right child. For simplicity, collect the traversal data as a string to be used as the shape identifier.

Last, we can get the number of shapes by counting how many unique shape identifier that exists using a hash table.

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

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * 1738 - Ceiling Function
 * Time limit: 10.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=5005
 */
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.totalCeilings = in.nextInt();
            input.totalLayers = in.nextInt();
            input.ceilings = new int[input.totalCeilings][input.totalLayers];
            for (int i = 0; i < input.totalCeilings; i++) {
                for (int j = 0; j < input.totalLayers; j++) {
                    input.ceilings[i][j] = in.nextInt();
                }
            }

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

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

class Input {
    public int totalCeilings;
    public int totalLayers;
    public int[][] ceilings;
}

class Output {
    public int totalShapes;
}

class Process {
    public Output process(final Input input) {
        final Set<String> shapes = new HashSet<>();
        for (final int[] ceiling : input.ceilings) {
            final Tree tree = new Tree();
            for (final int layer : ceiling) {
                tree.add(layer);
            }
            final String shape = tree.getShape();
            shapes.add(shape);
        }

        final Output output = new Output();
        output.totalShapes = shapes.size();
        return output;
    }
}

class Tree {
    public Node root;

    public void add(final int value) {
        root = add(root, value);
    }

    private Node add(final Node node, final int value) {
        if (node == null) return new Node(value);

        if (value < node.value) node.left = add(node.left, value);
        else node.right = add(node.right, value);
        return node;
    }

    public String getShape() {
        final LinkedList<String> path = new LinkedList<>();
        inorderTraversal(root, 0, 0, path);
        final String shape = path.stream()
            .map(Object::toString)
            .collect(Collectors.joining("_"));
        return shape;
    }

    private void inorderTraversal(
        final Node node,
        final int totalLefts,
        final int totalRights,
        final LinkedList<String> path
    ) {
        if (node != null) {
            inorderTraversal(node.left, totalLefts + 1, totalRights, path);
            path.addLast(String.format("%d:%d", totalLefts, totalRights));
            inorderTraversal(node.right, totalLefts, totalRights + 1, path);
        }
    }
}

class Node {
    public final int value;
    public Node left;
    public Node right;

    public Node(final int value) {
        this.value = value;
    }
}