Sunday, July 13, 2014

PowerOutage

Problem:
SRM 144 DIV 2 - 1100 Points
Overview:
Find the shortest amount of time required to traverse a series of tunnels connected in a tree-like layout.
Java Source:
    001: /*
    002: TopCoder
    003: Single Round Match: 144
    004: Division: 2
    005: Level: 3
    006: Points: 1100
    007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1697
    008:  */
    009:
    010: import java.util.ArrayList;
    011:
    012: public class PowerOutage {
    013:
    014:     private static final int MAX_JUNCTIONS = 50;
    015:
    016:     /* Each tunnel will need to be traversed twice, once on the way out and
    017:     then again on the way back.  However, if we save the longest tunnel for
    018:     last, then the power can go back on before we return along the longest
    019:     path.  Therefore the estimate time out is 2 * the sum of all the lenghts,
    020:      minus the longest length.
    021:      */
    022:     public int estimateTimeOut(int[] fromJunction, int[] toJunction,
    023:                                int[] ductLength) {
    024:
    025:         int sumOfLengths = 0;
    026:         for (int i : ductLength) sumOfLengths += i;
    027:
    028:         int longestLength = getLongestLength(fromJunction, toJunction,
    029:                 ductLength);
    030:
    031:         return (2 * sumOfLengths) - longestLength;
    032:     }
    033:
    034:     /*
    035:     Creates a graph representing the tunnels and junctions.  Then calls
    036:     getMaxLength() to determine the longest path.
    037:      */
    038:     private int getLongestLength(int[] from, int[] to, int[] length) {
    039:
    040:         EdgeWeightedDigraph graph = new EdgeWeightedDigraph(MAX_JUNCTIONS);
    041:
    042:         for (int i = 0; i < from.length; i++) {
    043:             graph.addEdge(new DirectedEdge(from[i], to[i], length[i]));
    044:         }
    045:
    046:         return getMaxLength(graph, 0);
    047:     }
    048:
    049:     /*
    050:     Uses recursion to return the length of the longest path beginning at the
    051:     source.
    052:      */
    053:     private int getMaxLength(EdgeWeightedDigraph graph, int source) {
    054:
    055:         int max = 0;
    056:
    057:         for (DirectedEdge edge : graph.getAdjacent(source)) {
    058:             int length = edge.weight + getMaxLength(graph, edge.to);
    059:             if (length > max) { max = length; }
    060:         }
    061:
    062:         return max;
    063:     }
    064:
    065:     /*
    066:     Holds a to and from junction, and the weight(distance) between them
    067:      */
    068:     class DirectedEdge {
    069:
    070:         final int from;
    071:
    072:         final int to;
    073:
    074:         final int weight;
    075:
    076:         DirectedEdge(int from, int to, int weight) {
    077:             this.from = from;
    078:             this.to = to;
    079:             this.weight = weight;
    080:         }
    081:     }
    082:
    083:     /*
    084:     A slimmed down Edge-Weighted Directed Graph.
    085:      */
    086:     class EdgeWeightedDigraph {
    087:
    088:         private final ArrayList[] adjLists;
    089:
    090:         EdgeWeightedDigraph(int numVertices) {
    091:             adjLists = new ArrayList[numVertices];
    092:             for (int i = 0; i < numVertices; i++) {
    093:                 adjLists[i] = new ArrayList();
    094:             }
    095:         }
    096:
    097:         void addEdge(DirectedEdge e) {
    098:             adjLists[e.from].add(e);
    099:         }
    100:
    101:         Iterable getAdjacent(int vertex) {
    102:             return adjLists[vertex];
    103:         }
    104:     }
    105: }
Notes:
First, the tunnels are laid out in a tree-like fashion. So there is only one path from the root to each junction and there are no loops.
Second, The power can go back on as soon as the last junction is reached.
Each tunnel will be traversed twice, once on the way out, and once again on the way back. Except for the longest length. We save the longest path for last, since the power can then go back on without having to wait for our return trip. Therefore, the estimated time is (2 * the sum of all tunnel lenghts) - (the length of the longest path)
Determining the sum of all lengths is trivial (Lines 25-26). Finding the longest path is a bit tougher. For this, I borrowed some code from an Edge-Weighted Directed Graph class that I was working with recently. The class is stripped down so that it only contains the addEdge() and getAdjacent() methods.
The graph is created by feeding it source junctions, destination junctions, and the time it takes to traverse the tunnel; all wrapped up in the form of a DirectedEdge class (Lines 40-44). It then calls getMaxLength() to determine the longest path starting from the source.
getMaxLength() determines the longest path rooted at the given junction by recursively calling getMaxLenght() on each of it's adjacent junctions and adding the distance to that adjacent junction.
Thank you for taking the time to read this solution. I welcome any feedback you may have.
For this, and other TopCoder solutions, please visit www.topcodingsolutions.net.

No comments:

Post a Comment