UVA - 11569 - Lovely Hint

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

Keywords: Dynamic Programming, Longest Increasing Subsequence

Objective

Given:

A sentence.
Lovely string definition.
1. Consists of an upper case alphabets.
2. A = 1, B = 2, …, Z = 26.
3. 5 x V1 ≤ 4 x V2.

We want to:

Find the length of the longest lovely string.
Find the number of ways to create the longest lovely string.

Glossary

Dynamic Programming (DP) — A method used to solve complex problems by breaking them into smaller overlapping subproblems and storing their results to avoid recomputation.
Longest Increasing Subsequence (LIS) — A classic computer science problem defined as finding the longest possible subsequence within a given sequence (array) where all elements are sorted in strictly increasing order.

Observation

Since any substring of the lovely string must follow the 5 x V1 ≤ 4 x V2 constraint, we could say that the V2 must be greater than V1, because V2 ≥ V1 × 5 / 4. Since the alphabets have a sequentially increasing values, we could say that lovely string must consists of lexicographically strictly increasing alphabets. This is similar to the LIS problem, which can be solved optimally using DP. In order to find such a subsequence, we could start by sorting the alphabets from the sentence in lexicographically increasing order. We can exclude any non upper case alphabets and duplicated alphabets.

Since this is a variation of the LIS problem, we could use DP bottom-up approach to find the LIS of the alphabets. We iteratively try to chain the greatest-to-lowest alphabets with every possible next alphabets. In each iteration, we keep track of the maximum length and the number of ways to form the maximum length. Those values are stored in a 1 dimensional array, the first dimension represent the first alphabet on the lovely substring and the value of the array represent the maximum length and the number of ways. At the end of iteration, we will have the maximum length and the number of ways of every possible first alphabets.

Last, we just need to retrieve the maximum length and the number of ways from the DP array.

Algorithm

We can use java TreeSet data structure to store unique alphabets in lexicographically increasing order. After that, the LIS can be implemented using a nested loop. We want to compute LIS starting from the smallest to the greatest length, this means the first loop will go from the greatest-to-lowest alphabet and the second loop will go to every possible next alphabet. At each iteration, we’ll discover the new length and number of ways of such a length. On each iteration, update the maximum length and number of ways of the maximum length for the current alphabet.

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

Implementation

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Set;
import java.util.TreeSet;

/**
 * 11569 - Lovely Hint
 * Time limit: 1.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2616
 */
public class Main {
    public static void main(final String... args) throws IOException {
        final BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        final BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        final Process process = new Process();

        final int totalSentences = Integer.parseInt(in.readLine());
        for (int i = 0; i < totalSentences; i++) {
            final Input input = new Input();
            input.sentence = in.readLine();

            final Output output = process.process(input);
            out.write(String.format("%d %d\n", output.length, output.total));
        }

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

class Input {
    public String sentence;
}

class Output {
    public int length;
    public int total;
}

class Process {
    public Output process(final Input input) {
        final int[] values = getValues(input.sentence);

        final int[] lengths = new int[27];
        final int[] totals = new int[27];

        for (int i = values.length - 1; i >= 0; i--) {
            final int value1 = values[i];
            lengths[value1] = 1;
            totals[value1] = 1;

            for (int j = i + 1; j < values.length; j++) {
                final int value2 = values[j];
                final boolean valid = value1 * 5 <= value2 * 4;

                if (valid) {
                    final int oldLength = lengths[value1];
                    final int newLength = 1 + lengths[value2];

                    final boolean longer = newLength > oldLength;
                    final boolean equals = newLength == oldLength;
                    if (longer) {
                        lengths[value1] = newLength;
                        totals[value1] = totals[value2];
                    } else if (equals) {
                        totals[value1] += totals[value2];
                    }
                }
            }
        }

        int maxLength = 0;
        int maxTotals = 0;

        for (int value = 1; value <= 26; value++) {
            final int length = lengths[value];
            final int total = totals[value];

            final boolean longer = length > maxLength;
            final boolean equals = length == maxLength;
            if (longer) {
                maxLength = length;
                maxTotals = total;
            } else if (equals) {
                maxTotals += total;
            }
        }

        final Output output = new Output();
        output.length = maxLength;
        output.total = maxTotals;
        return output;
    }

    private int[] getValues(final String sentence) {
        final Set<Integer> values = new TreeSet<>();
        for (final char letter : sentence.toCharArray()) {
            final boolean valid = 'A' <= letter && letter <= 'Z';
            if (valid) {
                final int value = letter - 'A' + 1;
                values.add(value);
            }
        }

        return values.stream()
            .mapToInt(Integer::intValue)
            .toArray();
    }
}