UVA - 10544 - Numbering the Paths 

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

Keywords: Graph, Directed Acyclic Graph, Single-source shortest paths, Dynamic Programming

Problem Summary 

Given:

  1. Total intersections.

  2. Total roads.

  3. List of roads between intersections.

  4. Total queries.

  5. List of queries, containing sequence of intersections.

We want to:

  1. Find the path number of each query based on lexicographically increasing paths.

Glossary 

  1. Graph — A structure consisting of a set of objects where some pairs of the objects are related.

  2. Directed Acyclic Graph (DAG) — A directed graph with no directed cycles.

  3. Single-source shortest paths (SSSP) — An algorithms to find the shortest paths from a single source vertex to all other vertices in a graph.

  4. Depth-first Search (DFS) — A graph traversal algorithm that starts from a source vertex and explores each path completely before backtracking and exploring other paths.

  5. Dynamic Programming (DP) — A method used to solve complex problems by breaking them into smaller overlapping subproblems and storing their results to avoid recomputation.

Observation 

The relationship between Intersections and Roads can be modeled as a graph, where the Intersections is the vertices and the roads is the Edges. In addition to that, the graph can be classified as DAG, because the roads are directional and designed in such a way that it is impossible to travel back to previously visited intersections, resulting in no cycles.

Next, we need to discover the mechanism to discover the lexicographically increasing paths. The paths can be discovered by traversing the graph starting from the first intersection defined on the query, which is similar to the concept of SSSP. In addition to that, we have the criteria to look for lexicographically increasing paths, which means we are prioritizing the discovery of a path with minimum vertex values at each iteration, which is similar to the concept of DFS. By sorting the edges by the destination vertex values, we could ensure that the DFS will maintain the lexicographic order during the path discoveries.

After we’ve discovered the lexicographically increasing paths, it is possible to find the path number by searching the result, but this approach is not optimal. Since we only have interest over the path number and not the whole paths, we can calculate it by counting the number of paths that is lexicographically lower than the query’s path.

To count the number of lexicographically lower path efficiently, we need to take advantage of the properties of DAG. Every DP problem can be represented as a DAG, so we need to convert the vertices and edges into subproblems to solve it with DP. Total paths from a vertices is equals to the total paths from each of its connected vertices and default to 1 if there are no connected vertices. We could define this subproblems as a recurrence relation.

Last, to find the number of lexicographically lower path, we combine the DFS and DP solution together. At each iteration of the traversal, count the number of paths from lower vertices. At the end of the traversal, we will have the total lower paths of the query.

Algorithm 

To ensure that the DFS traversal happens lexicographically, we need to create a graph that is sorted by the vertex values. Next, the recurrence relation that is defined on the DP can be implemented using recursive function, with vertex as the DP states and total paths as the DP values.

The time complexity of this solution is O({total queries} * {total vertices}).

Implementation 

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

/**
 * 10544 - Numbering the Paths
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1485
 */
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 totalTestCases = in.nextInt();
        for (int i = 0; i < totalTestCases; i++) {
            final Input input = new Input();
            input.totalLetters = in.nextInt();
            input.totalRoads = in.nextInt();
            input.roads = new char[input.totalRoads][];
            for (int j = 0; j < input.totalRoads; j++) {
                input.roads[j] = in.next().toCharArray();
            }
            input.totalQueries = in.nextInt();
            input.queries = new char[input.totalQueries][];
            for (int j = 0; j < input.totalQueries; j++) {
                input.queries[j] = in.next().toCharArray();
            }

            final Output output = process.process(input);
            for (int j = 0; j < output.queries.length; j++) {
                final char[] query = output.queries[j];
                final int pathId = output.pathIdPerQuery[j];
                out.print(query);
                out.print(": ");
                out.println(pathId);
            }
        }

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

class Input {
    public int totalLetters;
    public int totalRoads;
    public char[][] roads;
    public int totalQueries;
    public char[][] queries;
}

class Output {
    public char[][] queries;
    public int[] pathIdPerQuery;
}

class Process {
    public Output process(final Input input) {
        final Output output = new Output();
        output.queries = input.queries;
        output.pathIdPerQuery = new int[input.totalQueries];

        final int[][] edges = getEdges(input);
        final DirectedGraph graph = getGraph(edges);
        final int[][] queries = getQueries(input);

        final Memoization memoization = new Memoization();
        for (int i = 0; i < input.totalQueries; i++) {
            final int[] query = queries[i];
            final int totalLowerPaths = getTotalLowerPaths(memoization, graph, query, 0);
            final int pathId = totalLowerPaths + 1;
            output.pathIdPerQuery[i] = pathId;
        }

        return output;
    }

    private int[][] getEdges(final Input input) {
        final int[][] edges = new int[input.totalRoads][];
        for (int i = 0; i < input.totalRoads; i++) {
            final char[] road = input.roads[i];
            edges[i] = new int[]{road[0] - 'A', road[1] - 'A'};
        }
        return edges;
    }

    private DirectedGraph getGraph(final int[][] edges) {
        final DirectedGraph.Builder graph = new DirectedGraph.Builder(26);
        for (final int[] edge : edges) {
            graph.add(edge[0], edge[1]);
        }
        return graph.build();
    }

    private int[][] getQueries(final Input input) {
        final int[][] queries = new int[input.totalQueries][];
        for (int i = 0; i < input.totalQueries; i++) {
            queries[i] = new int[input.queries[i].length];
            for (int j = 0; j < input.queries[i].length; j++) {
                queries[i][j] = input.queries[i][j] - 'A';
            }
        }
        return queries;
    }

    private int getTotalLowerPaths(
        final Memoization memoization,
        final DirectedGraph graph,
        final int[] path,
        final int step
    ) {
        if (step == path.length) return 0;

        int totalLowerPaths = 0;
        final int vertex = path[step];
        for (final int next : graph.get(vertex)) {
            if (next == path[step + 1]) break;
            totalLowerPaths += getTotalPaths(memoization, graph, next);
        }

        return totalLowerPaths + getTotalLowerPaths(memoization, graph, path, step + 1);
    }

    private int getTotalPaths(
        final Memoization memoization,
        final DirectedGraph graph,
        final int current
    ) {
        if (graph.get(current).length == 0) return 1;
        if (memoization.contains(current)) return memoization.get(current);

        int totalPaths = 0;
        for (final int next : graph.get(current)) totalPaths += getTotalPaths(memoization, graph, next);
        memoization.set(current, totalPaths);

        return totalPaths;
    }
}

final class DirectedGraph {
    private final int[][] edges;

    private DirectedGraph(final Builder builder) {
        edges = new int[builder.edges.length][];
        for (int vertex = 0; vertex < builder.edges.length; vertex++) {
            final List<Integer> destinations = builder.edges[vertex] == null ? Collections.emptyList() : builder.edges[vertex];
            edges[vertex] = destinations.stream()
                .mapToInt(Integer::intValue)
                .distinct()
                .sorted()
                .toArray();
        }
    }

    public int[] get(final int from) {
        return edges[from];
    }

    static class Builder {
        private final LinkedList<Integer>[] edges;

        public Builder(final int maxVertex) {
            this.edges = new LinkedList[maxVertex + 1];
        }

        public void add(final int from, final int into) {
            if (edges[from] == null) edges[from] = new LinkedList<>();
            edges[from].add(into);
        }

        public DirectedGraph build() {
            return new DirectedGraph(this);
        }
    }
}

final class Memoization {
    private final int[] totalPathsPerVertex = new int[26];

    public void set(final int vertex, final int totalPaths) {
        totalPathsPerVertex[vertex] = totalPaths;
    }

    public int get(final int vertex) {
        return totalPathsPerVertex[vertex];
    }

    public boolean contains(final int vertex) {
        return totalPathsPerVertex[vertex] > 0;
    }
}


Powered by Docmost