UVA - 1281 - Bus Tour

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

Keywords: Graph, All-Pairs Shortest Paths, Hamiltonian Path, Dynamic Programming, Bit Manipulation

Objective

Given:

List of locations.
1. A headquarter.
2. An attraction.
3. A list of hotels.
List of roads between locations.

We want to:

Find the shortest path, with constraints:
1. Path goes from headquarter → hotels (pickup) → attraction → hotels (dropoff) → headquarter.
2. Half of the hotels that are picked up first must be dropped off first as well.

Glossary

Graph — A structure consisting of a set of objects where some pairs of the objects are related.
All-pairs Shortest Paths (APSP) — A problem of finding the shortest paths between every pair of vertices in a graph.
Hamiltonian Path — A path in a directed or undirected graph which visits each and every vertex of the graph exactly once.
Dynamic Programming (DP) — A method used to solve complex problems by breaking them into smaller overlapping subproblems and storing their results to avoid recomputation.
Bit Manipulation — A technique of using bitwise operations to manipulate individual bits in a binary data.
Floyd-Warshall Algorithm — An algorithm attributed to Robert W. Floyd and Stephen Warshall to find the shortest path between all pairs of vertices in a weighted directed graph without a negative cycle.
Held-Karp Algorithm — An algorithm attributed to Michael Held and Richard M. Karp that employs dynamic programming to solve the traveling salesman problem.
Bitmask — A binary representation of a data that can be manipulated using bitwise operations.

Observation

We could model the relationship between locations and roads as a graph, where the locations are the vertices and the roads are the edges. Each road have travel time, so the graph is a weighted graph. In addition to that, it is possible to travel both ways, so the graph is an undirected graph. We want to find the shortest path that can fulfill the sequence of traversal that is specified by the problem. First, let us begin by breaking down the requirements.

First, we want to split the hotels into 2 batch based on the pickup time. The batch that are picked up first, will be dropped off first as well. We could find the total ways to split the hotels using combinatorics equation. We want to pick half of the hotels for the batch 1, with the remaining for the batch 2. Using combination equation of C(n,r) = n!/(r!(n-r)!), this gives us C({total hotels}, {total hotels}/2) = 18!/(9!*9!) = 48620 possible combination at maximum.

Next, the path formed a circular path from headquarter → hotels → attraction → hotels → headquarter. The shortest circular path for this case must be formed from the shortest path from headquarter → hotels → attraction and attraction → hotels → headquarter.

Now, let us focus on the first phase of the path (headquarter → hotels → attraction). We want to find the shortest path that visits every hotels, starting from headquarter, and ending in attraction. Headquarter and attraction have restriction on the sequence (must be at the start and end), but this are not the case for hotels, sequence doesn’t matter as long as we visit every hotels. This is similar to the concept of hamiltonian path, where we want to visit each vertices exactly once.

Before we deep dive into the hamiltonian path, let us simplify the graph first. When we traverse the graph and visit the hotel vertex, we have the option to either pickup or ignore it. The pickup sequence matters a lot for the dropoff sequence later, and this means ignoring a vertex may reduce the dropoff time and lead us to a better path than visiting. To handle this, we could transform the graph into an APSP. With the adjacency list produced by APSP, we can directly travel to the hotel vertex that we want to pickup or dropoff.

Next, lets focus back to the hamiltonian path. There are several ways to solve the hamiltonian path problem, however, I want to take the DP approach for this problem. The approach is based on the Held-Karp Algorithm, which we will talk more in the next section. With this approach, we want to traverse every possible visited state of the graph from a single origin, until we have discovered the shortest path of every possible visited state and end vertex. Since the number of vertices is quiet small, the visited state can be stored in a bitmask. Since there is 2 types of path, we need to find the hamiltonian path from both headquarter and attraction.

Last, we need to combine the hamiltonian path together to form a valid circular path. Let us begin by exploring every possible combination of the first batch hotels. The list of hotels can be transformed into the visited state, and using this state, we could retrieve the hamiltonian paths from the headquarter to the first batch hotels (for pickup) and the hamiltonian paths from the attraction to the first batch hotels (for dropoff). Let us focus on the pickup first, after the first batch hamiltonian paths is discovered, we need to extend the path to reach the second batch and attraction. In order to do this, we could retrieve the hamiltonian paths from the attraction to the second batch hotels that ends on any first batch hotel. We could combine them together to form a valid path, and the same mechanism can be applied for the dropoff path.

Algorithm

The APSP can be implemented using Floyd-Warshall algorithm, which works by creating an adjacency list from the original edges and traversing every possible alternative paths for each pair of vertices.

Since the number of vertices is small (20), the visited state can be stored in a bitmask integer with bit 1 indicating the existence of a value, and 0 indicating the absence of a value.

The Hamiltonian Path can be implemented using Held-Karp algorithm. We iteratively traverse the visited state from 0 until 2^{total locations} - 1. On top of that, we also store the last vertex that each visited state is visiting. On each iteration, we want to extend the path into another unvisited vertices, leading to a discovery of a new visited state and end vertex. This will eventually give us the shortest path to reach each vertex with every possible visited vertices.

Next, to discover every possible combination of the first group, we could iteratively scan every possible visited state from 0 until 2^{total locations} - 1, and filter out the state that has hamming weight (number of 1 bit) equals to half of the hotels, excluding the headquarter and attraction.

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

Implementation

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

/**
 * 1281 - Bus Tour
 * Time limit: 20.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3894
 */
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();

        for (int caseId = 1; in.hasNextInt(); caseId++) {
            final Input input = new Input();
            input.caseId = caseId;
            input.totalLocations = in.nextInt();
            input.totalRoads = in.nextInt();
            input.roads = new int[input.totalRoads][3];
            for (int i = 0; i < input.totalRoads; i++) {
                input.roads[i][0] = in.nextInt();
                input.roads[i][1] = in.nextInt();
                input.roads[i][2] = in.nextInt();
            }

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

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

class Input {
    public int caseId;
    public int totalLocations;
    public int totalRoads;
    public int[][] roads;
}

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

class Process {
    private final FloydWarshallAlgorithm floydWarshallAlgorithm = new FloydWarshallAlgorithm();
    private final HeldKarpAlgorithm heldKarpAlgorithm = new HeldKarpAlgorithm();

    public Output process(final Input input) {
        final int headquarter = 0;
        final int attraction = input.totalLocations - 1;
        final int[] locations = sequence(headquarter, attraction);
        final int locationsMask = Mask.mask(locations);
        final int[] hotels = sequence(1, input.totalLocations - 2);
        final int hotelsMask = Mask.mask(hotels);

        final int[][] APSP = floydWarshallAlgorithm.findAllPairsShortestPaths(
            input.totalLocations,
            input.roads
        );

        if (input.totalLocations == 3) {
            final Output output = new Output();
            output.caseId = input.caseId;
            output.totalTimes = 2 * (APSP[headquarter][1] + APSP[1][attraction]);
            return output;
        }

        final int[][] headquarterSSSHP = heldKarpAlgorithm.findSingleSourceShortestHamiltonianPaths(
            headquarter,
            input.totalLocations,
            APSP
        );
        final int[][] attractionSSSHP = heldKarpAlgorithm.findSingleSourceShortestHamiltonianPaths(
            attraction,
            input.totalLocations,
            APSP
        );

        final List<Integer> firstHotelsMasks = new LinkedList<>();
        for (int mask = 0; mask <= locationsMask; mask++) {
            if (Mask.contains(mask, headquarter)) continue;
            if (Mask.contains(mask, attraction)) continue;
            if (Mask.hammingWeight(mask) != (hotels.length / 2)) continue;
            firstHotelsMasks.add(mask);
        }

        // store shortest paths from:
        // headquarter -> [hotels] -> attraction
        // for every possible first hotels
        final int[] pickupShortestPaths = new int[locationsMask + 1];
        Arrays.fill(pickupShortestPaths, Integer.MAX_VALUE);

        // store shortest paths from:
        // headquarter -> [hotels] -> attraction
        // for every possible first hotels
        final int[] dropoffShortestPaths = new int[locationsMask + 1];
        Arrays.fill(dropoffShortestPaths, Integer.MAX_VALUE);

        int minTotalTimes = Integer.MAX_VALUE;

        for (final int firstHotelsMask : firstHotelsMasks) {
            final int secondHotelsMask = (~firstHotelsMask) & hotelsMask;

            // find optimal pickup path from:
            // headquarter -> [first hotels] -> last first hotel -> [second hotels] -> attraction
            for (int lastFirstHotel : hotels) {
                if (!Mask.contains(firstHotelsMask, lastFirstHotel)) continue;

                final int firstMask = Mask.add(firstHotelsMask, headquarter, lastFirstHotel);
                final int firstPath = headquarterSSSHP[firstMask][lastFirstHotel];

                final int secondMask = Mask.add(secondHotelsMask, lastFirstHotel, attraction);
                final int secondPath = attractionSSSHP[secondMask][lastFirstHotel];

                final int oldPath = pickupShortestPaths[firstHotelsMask];
                final int newPath = firstPath + secondPath;
                pickupShortestPaths[firstHotelsMask] = Math.min(oldPath, newPath);
            }

            // find optimal dropoff path from:
            // attraction -> [first hotels] -> last first hotel -> [second hotels] -> headquarter
            for (final int lastFirstHotel : hotels) {
                if (!Mask.contains(firstHotelsMask, lastFirstHotel)) continue;

                final int firstMask = Mask.add(firstHotelsMask, attraction, lastFirstHotel);
                final int firstTotalWeights = attractionSSSHP[firstMask][lastFirstHotel];

                final int secondMask = Mask.add(secondHotelsMask, lastFirstHotel, headquarter);
                final int secondTotalWeights = headquarterSSSHP[secondMask][lastFirstHotel];

                final int oldPath = dropoffShortestPaths[firstHotelsMask];
                final int newPath = firstTotalWeights + secondTotalWeights;
                dropoffShortestPaths[firstHotelsMask] = Math.min(oldPath, newPath);
            }

            final int totalTimes = pickupShortestPaths[firstHotelsMask] + dropoffShortestPaths[firstHotelsMask];
            minTotalTimes = Math.min(minTotalTimes, totalTimes);
        }

        final Output output = new Output();
        output.caseId = input.caseId;
        output.totalTimes = minTotalTimes;
        return output;
    }

    private int[] sequence(final int from, final int until) {
        final int length = until - from + 1;
        final int[] sequence = new int[until - from + 1];
        for (int i = 0; i < length; i++) sequence[i] = from + i;
        return sequence;
    }
}

class FloydWarshallAlgorithm {
    public int[][] findAllPairsShortestPaths(final int totalVertices, final int[][] edges) {
        final int[][] shortestPaths = new int[totalVertices][totalVertices];
        fill(shortestPaths, Integer.MAX_VALUE);

        for (int vertex = 0; vertex < totalVertices; vertex++) {
            shortestPaths[vertex][vertex] = 0;
        }

        for (final int[] edge : edges) {
            shortestPaths[edge[0]][edge[1]] = shortestPaths[edge[1]][edge[0]] = edge[2];
        }

        for (int alternativeVertex = 0; alternativeVertex < totalVertices; alternativeVertex++) {
            for (int originVertex = 0; originVertex < totalVertices; originVertex++) {
                if (shortestPaths[originVertex][alternativeVertex] == Integer.MAX_VALUE) continue;
                for (int destinationVertex = 0; destinationVertex < totalVertices; destinationVertex++) {
                    if (shortestPaths[alternativeVertex][destinationVertex] == Integer.MAX_VALUE) continue;

                    final int oldPath = shortestPaths[originVertex][destinationVertex];
                    final int newPath = shortestPaths[originVertex][alternativeVertex] + shortestPaths[alternativeVertex][destinationVertex];
                    shortestPaths[originVertex][destinationVertex] = Math.min(oldPath, newPath);
                }
            }
        }

        return shortestPaths;
    }

    private void fill(final int[][] array2, final int value) {
        for (final int[] array1 : array2) {
            Arrays.fill(array1, value);
        }
    }
}

final class HeldKarpAlgorithm {
    public int[][] findSingleSourceShortestHamiltonianPaths(
        final int originVertex,
        final int totalVertices,
        final int[][] paths
    ) {
        final int totalMasks = 1 << totalVertices;
        final int[][] shortestHamiltonianPaths = new int[totalMasks][totalVertices];
        fill(shortestHamiltonianPaths, Integer.MAX_VALUE);

        for (int destinationVertex = 0; destinationVertex < totalVertices; destinationVertex++) {
            if (originVertex == destinationVertex) continue;

            final int visitedMask = Mask.mask(originVertex, destinationVertex);
            shortestHamiltonianPaths[visitedMask][destinationVertex] = paths[originVertex][destinationVertex];
        }

        for (int endMask = 0; endMask < totalMasks; endMask++) {
            for (int endVertex = 0; endVertex < totalVertices; endVertex++) {
                if (!Mask.contains(endMask, endVertex)) continue;

                final int prevMask = Mask.remove(endMask, endVertex);
                for (int prevVertex = 0; prevVertex < totalVertices; prevVertex++) {
                    if (!Mask.contains(prevMask, prevVertex)) continue;
                    if (shortestHamiltonianPaths[prevMask][prevVertex] == Integer.MAX_VALUE) continue;
                    if (paths[prevVertex][endVertex] == Integer.MAX_VALUE) continue;

                    final int oldPath = shortestHamiltonianPaths[endMask][endVertex];
                    final int newPath = shortestHamiltonianPaths[prevMask][prevVertex] + paths[prevVertex][endVertex];
                    shortestHamiltonianPaths[endMask][endVertex] = Math.min(oldPath, newPath);
                }
            }
        }

        return shortestHamiltonianPaths;
    }

    private void fill(final int[][] array2, final int value) {
        for (final int[] array1 : array2) {
            Arrays.fill(array1, value);
        }
    }
}

final class Mask {
    public static int mask(final int... items) {
        return add(0, items);
    }

    public static int add(int mask, final int... items) {
        for (final int item : items) mask = add(mask, item);
        return mask;
    }

    private static int add(final int mask, final int item) {
        return mask | (1 << item);
    }

    public static int remove(int mask, final int... items) {
        for (final int item : items) mask = remove(mask, item);
        return mask;
    }

    private static int remove(final int mask, final int item) {
        return mask ^ (1 << item);
    }

    public static boolean contains(final int mask, final int item) {
        return ((mask >> item) & 1) > 0;
    }

    public static int hammingWeight(final int mask) {
        return Integer.bitCount(mask);
    }
}