UVA - 10350 - Liftless EME

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

Keywords: Graph Theory, Directed Acyclic Graph, Dynamic Programming

Problem Summary

Given:

Total roofs in a building.
Total holes in each roof.
Total times to walk between holes and ladders in each floor.
Total times to climb a ladder between adjacent floors (2 minutes).

We want to:

Find the minimum time to travel from the ground floor to the top floor.

Glossary

DAG — Directed Acyclic Graph
DP - Dynamic Programming

Observation

The relationship between roofs, holes and ladders can be modeled as a weighted graph, where the locations (roof + hole) is the vertices, roofs is a weighted edge that connect holes and ladders, and ladders is a weighted edge that connect 2 adjacent roofs. The weight between 2 adjacent roofs is exactly 2 minutes, and the weight between holes and ladders is specified on the input. It’s also possible for us to walk between any holes to any ladders within a floor.

Since we’re moving in one direction from the ground to the top, the graph in this problem could be classified as a DAG. Uniquely speaking, DAG can also be represented as a DP problem by transforming the vertices as the sub-problems and the edges as the transition between sub-problems.

Algorithm

To transform the DAG into DP, locations (roof + hole) will become the state of the DP and the total times will become the value of the DP. To traverse the DAG, we started moving from the ground roof to the upper roof. For every level of roof, we try every possible combination of holes and ladders, then store the most optimal time on the DP. We keep repeating this process until we’ve reached the top.

The time complexity for this solution is O({total roofs} * {total holes}) or O(10^3).

Implementation

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

/**
 * 10350 - Liftless EME
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1291
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(System.in);
        final PrintWriter out = new PrintWriter(System.out);
        final Process process = new Process();

        while (in.hasNext()) {
            final Input input = new Input();
            input.caseName = in.next();
            input.totalRoofs = in.nextInt();
            input.totalHoles = in.nextInt();
            input.walkTimes = new int[input.totalHoles * (input.totalRoofs - 1)][];
            in.nextLine();
            for (int i = 0; i < input.walkTimes.length; i++) {
                final String line = in.nextLine();
                final int[] row = Arrays.stream(line.split(" ")).mapToInt(Integer::parseInt).toArray();
                input.walkTimes[i] = row;
            }

            final Output output = process.process(input);
            out.println(output.caseName);
            out.println(output.minimumTotalTimes);
        }

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

class Input {
    public String caseName;
    public int totalRoofs;
    public int totalHoles;
    public int[][] walkTimes;
}

class Output {
    public String caseName;
    public int minimumTotalTimes;
}

class Process {
    public Output process(final Input input) {
        final Output output = new Output();
        output.caseName = input.caseName;
        output.minimumTotalTimes = dynamicProgramming(input);
        return output;
    }

    private int dynamicProgramming(final Input input) {
        // total times per roof and hole
        final int[][] dp = new int[input.totalRoofs][input.totalHoles];
        fill(dp, Integer.MAX_VALUE);

        for (int hole = 0; hole < input.totalHoles; hole++) {
            dp[0][hole] = 0;
        }

        for (int roof = 0; roof < input.totalRoofs - 1; roof++) {
            final int upperRoof = roof + 1;
            for (int hole = 0; hole < input.totalHoles; hole++) {
                for (int ladder = 0; ladder < input.totalHoles; ladder++) {
                    final int line = getLine(input, roof, hole);
                    final int walkTime = input.walkTimes[line][ladder];
                    final int climbTime = 2;

                    final int oldTotalTime = dp[upperRoof][ladder];
                    final int newTotalTime = dp[roof][hole] + walkTime + climbTime;
                    if (newTotalTime < oldTotalTime) {
                        dp[upperRoof][ladder] = newTotalTime;
                    }
                }
            }
        }

        return Arrays.stream(dp[input.totalRoofs - 1])
            .min()
            .orElse(Integer.MAX_VALUE);
    }

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

    private int getLine(final Input input, final int roof, final int hole) {
        return roof * input.totalHoles + hole;
    }
}