UVA - 12249 - Overlapping Scenes

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

Keywords: Permutation, Searching

Objective

Given:

Number of scenes.
List of scenes.

We want to:

Find the minimum length of the movie.

Glossary

Permutation — A mathematical concept that determines the number of possible arrangements for a specific set of elements.
Searching — A process of locating a specific element or item within a collection of data.
Brute Force — A search strategy that systematically explores every option until the answer is discovered.

Observation

Movie is a sequence of scenes, and scene is a sequence of frames. To reduce the length of the movie, we can merge the ending and the beginning from any pair of 2 consecutive scenes, as long as it has identical frames.

Next, since the number of scenes is quiet small, it is possible for us to create every permutation of the sequence of the scenes. We will try to create a movie out of every possible sequence of the scenes.

After that, to create a shortest movie out of the sequence of the scenes, we need to search for the maximum matches from every possible ending and beginning of the consecutive scenes. Since the length of a scene is quiet small, we can naively compare every possible length of the ending and begining to find matches. When maximum matches found, we can merge the identical frames together and add the remaining frames into the movie.

Last, after we have identified every possible shortest movie, we just need to return the length of the actual shortest movie.

Algorithm

To generate permutation of the sequence of the scenes, unlike C++, java doesn’t have next_permutation function, but we can implement the same algorithm by ourself. The next permutation is defined as the next arrangement of the elements in the sorted order. We’ll use this mechanism to iterate over every possible permutation of the sequence of scenes.

To create the shortest movie out of the sequence of scenes, we can use brute force algorithm to identify the maximum identical frames out of the consecutive scene. This is done by going over every possible of scene length and comparing the ending and beginning of the consecutive scenes with such a length.

The time complexity of this solution is O({total scenes}! * {total scenes}^3) or O(10^5).

Implementation

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

/**
 * 12249 - Overlapping Scenes
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3401
 */
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.totalScenes = in.nextInt();
            input.scenes = new String[input.totalScenes];
            for (int i = 0; i < input.totalScenes; i++) {
                input.scenes[i] = in.next();
            }

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

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

class Input {
    public int caseId;
    public int totalScenes;
    public String[] scenes;
}

class Output {
    public int caseId;
    public int movieLength;
}

class Process {
    public Output process(final Input input) {
        final Permutation<String> permutation = new Permutation<>(input.scenes, Comparator.naturalOrder());

        int minMovieLength = Integer.MAX_VALUE;
        for (String[] scenes = permutation.next(); scenes != null; scenes = permutation.next()) {
            final String movie = createMovie(scenes);
            minMovieLength = Math.min(minMovieLength, movie.length());
        }

        final Output output = new Output();
        output.caseId = input.caseId;
        output.movieLength = minMovieLength;
        return output;
    }

    private String createMovie(final String[] scenes) {
        final StringBuilder movie = new StringBuilder();

        for (final String scene : scenes) {
            int commonLength;
            for (commonLength = scene.length(); commonLength >= 0; commonLength--) {
                final String commonMovie = movie.substring(Math.max(0, movie.length() - commonLength), movie.length());
                final String commonScene = scene.substring(0, commonLength);
                if (commonMovie.equals(commonScene)) break;
            }

            final String uncommonScene = scene.substring(commonLength, scene.length());
            movie.append(uncommonScene);
        }

        return movie.toString();
    }
}

final class Permutation<V> {
    private final V[] items;
    private final Comparator<V> comparator;
    private boolean executed;

    public Permutation(final V[] items, final Comparator<V> comparator) {
        this.items = items.clone();
        this.comparator = comparator;
        this.executed = false;

        Arrays.sort(this.items, this.comparator);
    }

    public V[] next() {
        if (!executed) {
            executed = true;
            return items;
        }

        int index = -1;
        for (int i = items.length - 2; i >= 0; i--) {
            final int compare = comparator.compare(items[i], items[i + 1]);
            if (compare < 0) {
                index = i;
                break;
            }
        }

        if (index == -1) {
            return null;
        }

        for (int i = items.length - 1; i > index; i--) {
            final int compare = comparator.compare(items[i], items[index]);
            if (compare > 0) {
                swap(i, index);
                break;
            }
        }

        reverse(index + 1, items.length - 1);
        return items;
    }

    private void reverse(int start, int end) {
        while (start < end) {
            swap(start, end);
            start++;
            end--;
        }
    }

    private void swap(int i, int j) {
        V temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }
}