UVA - 11147 - KuPellaKeS BST

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

Keywords: Tree, Sliding Window

Objective

Given:

Total numbers.
List of numbers.

We want to:

Create a Binary Search Tree (BST), with these extra constraints:
1. The difference of sum between the left and the right subtree must be minimized.
2. If there is multiple ways to create such a tree, the sum of the left subtree must be maximum.
3. The same constraints is applied to the children of the node.
Create a string representation of the BST.

Glossary

Tree — A hierarchical data structure used to represent data in a parent-child relationship.
Sliding Window — A technique for processing contiguous segments of data by moving a fixed-size or variable-size window across a sequence.
Pre-order Traversal — A process of visiting each node of a tree in the following order: root, left, right.

Observation

We could model the relationship between numbers as a tree, where the numbers are the node. The numbers on the left nodes are less than or equals to the parent node, and the numbers on the right nodes are greater than the parent node.

Since the numbers are ordered in an increasing order inside the tree, we could start the tree reconstruction by sorting the numbers. Once sorted, we want to reconstruct the tree starting from the root node, until we reach the leave nodes.

During the tree traversal, we want to split the numbers into 3 parts: left children, parent, and right children. Since the numbers are sorted ahead of time, we just need to pick a number in that array that could split the numbers and minimize the difference between the left and right sum, which can be done efficiently using sliding window technique. After we are able to find the optimal ways to split the numbers, we just need to apply the same mechanism recursively for the left and right numbers. Once we know the value of the parent and its left and right children, we just need to recursively connect them together using the tree data structure.

Last, the string representation is written in pre-order traversal (root, left, right), which can be implemented with a recursive function.

Algorithm

The sliding window is used to discover the sum of the left and right numbers, when the array is sliced at a certain point. In order to do this, we could begin by initiating the sum of the left (zero) and the right (sum of all numbers). Then, we split the array iteratively from left to right. At each point, we want to increase the sum on the left side and decrease the sum on the right side. This should give us the sum of left and right children at every point that can be utilized to find a point that minimize the difference between the sum of the left and right children.

The pre-order traversal is implemented recursively, but we need to be careful with the string concatenation. Use StringBuilder to avoid rebuilding the whole string during the recursive call.

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

Implementation

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

/**
 * 11147 - KuPellaKeS BST
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2088
 */
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();

        final int totalCases = in.nextInt();
        for (int caseId = 1; caseId <= totalCases; caseId++) {
            final Input input = new Input();
            input.caseId = caseId;
            input.totalNumbers = in.nextInt();
            input.numbers = new int[input.totalNumbers];
            for (int i = 0; i < input.totalNumbers; i++) {
                input.numbers[i] = in.nextInt();
            }

            final Output output = process.process(input);
            out.format("Case #%d: %s\n", output.caseId, output.bst);
        }

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

class Input {
    public int caseId;
    public int totalNumbers;
    public int[] numbers;
}

class Output {
    public int caseId;
    public String bst;
}

class Process {
    public Output process(final Input input) {
        final Output output = new Output();
        output.caseId = input.caseId;

        final int[] numbers = input.numbers;
        Arrays.sort(numbers);

        final Tree bst = createKupellakesBST(numbers);
        output.bst = bst.toString();

        return output;
    }

    private Tree createKupellakesBST(final int[] numbers) {
        if (numbers.length == 0) return null;
        else if (numbers.length == 1) return new Tree(numbers[0]);

        final int rootIndex = findRootIndex(numbers);
        final int[] leftNumbers = Arrays.copyOfRange(numbers, 0, rootIndex);
        final int[] rightNumbers = Arrays.copyOfRange(numbers, rootIndex + 1, numbers.length);

        final Tree root = new Tree(numbers[rootIndex]);
        root.left = createKupellakesBST(leftNumbers);
        root.right = createKupellakesBST(rightNumbers);
        return root;
    }

    private int findRootIndex(final int[] numbers) {
        int leftSum = 0;
        int rightSum = sum(numbers);
        int minimumDifference = Integer.MAX_VALUE;
        int middle = 0;

        for (int i = 0; i < numbers.length; i++) {
            rightSum -= numbers[i];
            final int difference = Math.abs(leftSum - rightSum);
            leftSum += numbers[i];

            final boolean strictlyIncreasingRight = i + 1 == numbers.length || numbers[i + 1] > numbers[i];
            final boolean minimizeDifference = difference < minimumDifference;
            if (strictlyIncreasingRight && minimizeDifference) {
                minimumDifference = difference;
                middle = i;
            }
        }

        return middle;
    }

    private int sum(final int[] numbers) {
        int sum = 0;
        for (final int number : numbers) sum += number;
        return sum;
    }
}

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

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

    public String toString() {
        final StringBuilder builder = new StringBuilder();
        buildString(builder, this);
        return builder.toString();
    }

    private void buildString(final StringBuilder builder, final Tree tree) {
        if (tree == null) return;

        builder.append(tree.value);
        if (tree.left != null || tree.right != null) builder.append('(');
        buildString(builder, tree.left);
        if (tree.left != null && tree.right != null) builder.append(',');
        buildString(builder, tree.right);
        if (tree.left != null || tree.right != null) builder.append(')');
    }
}