UVA - 12515 - Movie Police 

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

Keywords: Brute Force, Sliding Window

Problem Summary 

Given:

  1. Total movies

  2. Total clips

  3. List of movie signatures

  4. List of clip signatures

We want to:

  1. Find an index of movie signature with the most similarity

Glossary 

  1. Brute Force — A search strategy that systematically explores every option until the answer is discovered.

  2. Sliding Window — A technique for processing contiguous segments of data by moving a fixed-size or variable-size window across a sequence.

Observation 

The hamming distance can be calculated by counting the number of characters that don’t match between 2 signatures.

Next, the similarity between a clip and a movie can be calculated by comparing the clip with every possible segments of the movie. The length of the segment must be equals with the clip. Since segment is a contiguous sub-sequence of the movie with a fixed length, we could use sliding window strategy to discover every possible segments of the movie.

Last, we could use Brute Force strategy to find the most similar movie. We start by calculating the similarity of every movies and lookup for the first movie with the greatest similarity.

Algorithm 

The hamming distance section can be implemented by iteratively comparing the characters. The sliding window section can be implemented by iteratively creating a sub-string of movie from a different start point. The brute force section can be implemented by iteratively calculating the similarity between clip and movies while keeping track of the last most similar movie.

The time complexity for this solution is O({total clips} * {total movies} * {length} ) or O(10^7).

Implementation 

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

/**
 * 12515 - Movie Police
 * Time limit: 4.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3960
 */
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 Input input = new Input();
        input.totalMovies = in.nextInt();
        input.totalClips = in.nextInt();
        input.movies = new String[input.totalMovies];
        input.clips = new String[input.totalClips];
        for (int i = 0; i < input.totalMovies; i++) {
            input.movies[i] = in.next();
        }
        for (int i = 0; i < input.totalClips; i++) {
            input.clips[i] = in.next();
        }

        final Output output = process.process(input);
        for (final int index : output.indexes) {
            out.println(index);
        }

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

class Input {
    public int totalMovies;
    public int totalClips;
    public String[] movies;
    public String[] clips;
}

class Output {
    public int[] indexes;
}

class Process {
    public Output process(final Input input) {
        final Output output = new Output();
        output.indexes = new int[input.totalClips];

        for (int i = 0; i < input.totalClips; i++) {
            final String clip = input.clips[i];
            int minimumSimilarity = Integer.MAX_VALUE;
            int minimumIndex = 0;

            for (int j = 0; j < input.totalMovies; j++) {
                final String movie = input.movies[j];
                final int similarity = getSimilarity(clip, movie);

                if (similarity < minimumSimilarity) {
                    minimumSimilarity = similarity;
                    minimumIndex = j + 1;
                }
            }

            output.indexes[i] = minimumIndex;
        }

        return output;
    }

    private int getSimilarity(final String clip, final String movie) {
        int minimumDistance = Integer.MAX_VALUE;
        for (int i = 0; i + clip.length() <= movie.length(); i++) {
            final String movieClip = movie.substring(i, i + clip.length());
            final int distance = getHammingDistance(clip, movieClip);
            minimumDistance = Math.min(minimumDistance, distance);
        }

        return minimumDistance;
    }

    private int getHammingDistance(final String signature1, final String signature2) {
        int distance = 0;
        for (int i = 0; i < signature1.length(); i++) {
            if (signature1.charAt(i) != signature2.charAt(i)) {
                distance++;
            }
        }

        return distance;
    }
}


Powered by Docmost