UVA - 12768 - Inspired Procrastination

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

Keywords: Graph, Single-source Shortest Paths, Negative Cycle

Problem Summary

Given:

List of Points.
List of Decisions between Points with Procrastination Factor.

We want to:

Find the maximum total procrastination factors.

Glossary

Graph — A structure consisting of a set of objects where some pairs of the objects are related.
Single-source Shortest Paths (SSSP) — An algorithms to find the shortest paths from a single source vertex to all other vertices in a graph.
Bellman-Ford — An algorithm that computes single-source shortest paths in a weighted digraph, capable of handling graphs with negative edge weights.

Observation

The relationship between points and decisions can be modeled as a weighted directed graph, where the points are the vertices, the decisions are the edges, and the procrastination factors are the weights. The graph can contains cycles and negative weights.

Total procrastination factors is a sum of procrastination factor from a series of connected decisions, starting from point 1. We could retrieve the total by traversing the graph from vertex 1, which is similar to the concept of Negative Cycle SSSP, and Bellman-Ford algorithm is known to be the most optimal algorithm for this particular case. With Bellman-Ford, we could discover (1) the minimum total distances from vertex 1 to any vertices, and (2) whether infinite negative cycles exists on any vertices.

In contrary to Bellman-Ford, this problem asked for (1) the maximum total distances from vertex 1, and (2) whether infinite positive cycles exists. By flipping the graph weight (positive → negative, negative → positive), we could trick the algorithm into finding the maximum total distance and infinite positive cycles.

Algorithm

Negative Cycle SSSP can be implemented using Bellman-Ford algorithm. We first initiate the distances from the source to any other vertices as infinite positives, and the distances from and into the source should be 0. This distances represents the currently discovered shortest paths. We keep adding each edge into the discovered paths exactly total vertices - 1 times. By the end of the iteration, we should have discovered every paths from the source to the other vertices.

Keep in mind that the weight of the graph should be flipped before the Bellman-Ford is applied. Negative cycles exists when a new shortest paths could be formed by repeating the Bellman-Ford iteration. Negative cycles indicates that we could produce unlimited total procrastination factors. Since the total distances is flipped, we could get the maximum total factors by flipping the minimum total distances.

The time complexity of this solution is O({total points} * {total decisions}) or O(10^6).

Implementation

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

/**
 * 12768 - Inspired Procrastination
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4621
 */
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();

        while (true) {
            final Input input = new Input();
            input.totalPoints = in.nextInt();
            input.totalDecisions = in.nextInt();
            if (input.isEOF()) break;

            input.decisions = new int[input.totalDecisions][3];
            for (int i = 0; i < input.totalDecisions; i++) {
                input.decisions[i][0] = in.nextInt();
                input.decisions[i][1] = in.nextInt();
                input.decisions[i][2] = in.nextInt();
            }

            final Output output = process.process(input);
            if (output.isUnlimited) out.println("Unlimited!");
            else out.println(output.maximumTotalFactors);
        }

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

class Input {
    public int totalPoints;
    public int totalDecisions;
    public int[][] decisions;

    public boolean isEOF() {
        return totalPoints == 0 && totalDecisions == 0;
    }
}

class Output {
    public boolean isUnlimited;
    public int maximumTotalFactors;
}

class Process {
    public Output process(final Input input) {
        final int[][] negativeEdges = getNegativeEdges(input);
        final int[] distances = getDistancesWithBellmanFord(negativeEdges, input.totalPoints, 1);
        final boolean hasNegativeCycles = hasNegativeCycles(negativeEdges, distances);
        final int minimumDistance = getMinimumDistance(distances);

        final Output output = new Output();
        output.isUnlimited = hasNegativeCycles;
        output.maximumTotalFactors = -minimumDistance;

        return output;
    }

    private int[][] getNegativeEdges(final Input input) {
        final int[][] edges = new int[input.totalDecisions][3];
        for (int i = 0; i < input.totalDecisions; i++) {
            edges[i][0] = input.decisions[i][0];
            edges[i][1] = input.decisions[i][1];
            edges[i][2] = -input.decisions[i][2];
        }
        return edges;
    }

    private int[] getDistancesWithBellmanFord(final int[][] edges, final int maxVertex, final int source) {
        final int[] distances = new int[maxVertex + 1];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[source] = 0;

        for (int i = 0; i < maxVertex - 1; i++) {
            for (final int[] edge : edges) {
                final int from = edge[0], into = edge[1], weight = edge[2];
                if (distances[from] < Integer.MAX_VALUE) {
                    distances[into] = Math.min(distances[into], distances[from] + weight);
                }
            }
        }

        return distances;
    }

    private boolean hasNegativeCycles(final int[][] edges, final int[] distances) {
        for (final int[] edge : edges) {
            final int from = edge[0], into = edge[1], weight = edge[2];
            if (distances[from] < Integer.MAX_VALUE && distances[from] + weight < distances[into]) {
                return true;
            }
        }

        return false;
    }

    private int getMinimumDistance(final int[] distances) {
        return Arrays.stream(distances).min().orElse(0);
    }
}