Optimum Tree traversal algorithm Topcoder

Question

I'm practicing a 1000 point algorithm problem on the topcoder.com arena.

The problem is as follows:     

You work for an electric company, and the power goes out in a rather large apartment complex with a lot of irate tenants. You isolate the problem to a network of sewers underneath the complex with a step-up transformer at every junction in the maze of ducts. Before the power can be restored, every transformer must be checked for proper operation and fixed if necessary. To make things worse, the sewer ducts are arranged as a tree with the root of the tree at the entrance to the network of sewers. This means that in order to get from one transformer to the next, there will be a lot of backtracking through the long and claustrophobic ducts because there are no shortcuts between junctions. Furthermore, it's a Sunday; you only have one available technician on duty to search the sewer network for the bad transformers. Your supervisor wants to know how quickly you can get the power back on; he's so impatient that he wants the power back on the moment the technician okays the last transformer, without even waiting for the technician to exit the sewers first.

You will be given three int[]'s: fromJunction, toJunction, and ductLength that represents each sewer duct. Duct i starts at junction (fromJunction[i]) and leads to junction (toJunction[i]). ductlength[i] represents the amount of minutes it takes for the technician to traverse the duct connecting fromJunction[i] and toJunction[i]. Consider the amount of time it takes for your technician to check/repair the transformer to be instantaneous. Your technician will start at junction 0 which is the root of the sewer system. Your goal is to calculate the minimum number of minutes it will take for your technician to check all of the transformers. You will return an int that represents this minimum number of minutes

Constraints:

• fromJunction will contain between 1 and 50 elements, inclusive.
• toJunction will contain between 1 and 50 elements, inclusive.
• ductLength will contain between 1 and 50 elements, inclusive.
• toJunction, fromJunction, and ductLength must all contain the same number of elements.
• Every element of fromJunction will be between 0 and 49 inclusive.
• Every element of toJunction will be between 1 and 49 inclusive.
• fromJunction[i] will be less than toJunction[i] for all valid values of i.
• Every (fromJunction[i],toJunction[i]) pair will be unique for all valid values of i.
• Every element of ductlength will be between 1 and 2000000 inclusive.
• The graph represented by the set of edges (fromJunction[i],toJunction[i]) will never contain a loop, and all junctions can be reached from junction 0.

Example Testcase:

Passed Test

{0,0,0,1,4}

{1,3,4,2,5}

{10,10,100,10,5}

Returns: 165

{0,0,0,1,4,4,6,7,7,7,20}

{1,3,4,2,5,6,7,20,9,10,31}

{10,10,100,10,5,1,1,100,1,1,5}

Returns: 281

{0, 0, 1, 1, 1, 3, 1, 4, 7, 2, 0, 3, 6, 8, 5, 11, 3, 12, 0, 15, 15, 18, 0, 4, 7, 24, 25, 10, 0, 19, 25, 6, 15, 29, 20, 5, 23, 19}

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38}

{178317, 81669, 294672, 1649827, 671297, 443274, 1823848, 333826, 1750416, 289900, 1922826, 1961031, 1984157, 1022042, 1708788, 952091, 1095097, 1600638, 1896461, 288397, 741380, 540242, 1094958, 60081, 950467, 1955292, 1607609, 1717760, 1318832, 242398, 1586217, 1374294, 1231329, 1969383, 562578, 962458, 1114049, 313948}

Returns: 78008798

Passed Test

{0, 0, 0, 0, 1, 0, 3, 2, 6, 4, 0, 2, 11, 3, 1, 14, 3, 2, 5, 15, 6, 0, 11, 8, 11, 24, 23, 6, 22, 2, 15, 20, 4, 22, 30, 14, 5, 9, 7, 7, 36, 15, 34, 3, 2}

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45}

{752846, 1419859, 179904, 163605, 1740377, 190846, 1352634, 965272, 824872, 538518, 1438990, 714089, 1749318, 238531, 429771, 1075929, 996791, 634327, 687236, 1567508, 1123950, 68018, 1617650, 191391, 571448, 1348412, 164008, 205801, 1063191, 1117957, 1692178, 1234376, 1504523, 1015591, 1828379, 1224921, 1545579, 937373, 1414625, 373769, 1896141, 1897686, 252657, 422834, 1773177}

Expected: 83927521

Received: 83927521

Code:

import java.util.*; public class PowerOutage { public int estimateTimeOut(int[] fromJunction, int[] toJunction, int[] ductLength) { int res = 0, len = fromJunction.length; for (int i = 0; i < len; i++) { res += ductLength[i] * 2; } return res - mostExpensivePath(fromJunction, toJunction, ductLength, 0); } public boolean count(int[] a, int node) { for (int i = 0; i < a.length; i++) { if (a[i] == node) return false; } return true; } //Depth First Search public int mostExpensivePath(int[] a, int[] b, int[] c, int currentRoot) { int cost = 0, maxC = 0, k = a.length, tempC = 0; while (!done(c)) { //find first deepest leaf node for (int i = 0; i < k; i++) { if (a[i] == currentRoot) { currentRoot = b[i]; cost += c[i]; i = -1; } } //trace leaf node back to the first multi-node parent for (int i = 0; i < k; i++) { if (b[i] == currentRoot) { currentRoot = a[i]; a[i] = -1; b[i] = -1; tempC += c[i]; c[i] = 0; i = -1; if (!count(a, currentRoot)) break; } } //check cost is max if (cost > maxC) maxC = cost; cost -= tempC; tempC = 0; } return maxC; } public boolean done(int[] c) { for (int i = 0; i < c.length; i++) { if (c[i] > 0) return false; } return true; } 

Code works fine and passes all testcases. Is there any way for me to improve on this?

Answer 1

Simpler (but in some cases very slow) function to calculate the cost of the longest path:

public int largestPathCost(int[] a, int[] b, int[] c) { int k = a.length; // prepare array of costs (times) to reach each node int cost[] = new int[k+1]; for (int i = 0; i <= k; i++) cost[i] = 0; // calculate times by adding duct lengths for (int toGo = k; toGo != 0;) { // nodes to calculate for (int i = 0; i < k; i++) { // test the i-th duct int fromId = a[i]; int toId = b[i]; // endpoint if (cost[toId] == 0) // not calculated yet if (fromId == 0 || cost[fromId] != 0) { cost[toId] = cost[fromId] + c[i]; toGo --; } } } // retrieve the maximum cost int maxC = 0; for (int i = 1; i <= k; i++) { if (cost[i] > maxC) maxC = cost[i]; } return maxC; } 

It may be very slow if ducts are given in reversed order (those farthest first). The worst case would be a single-path 'maze' with a long chain of ducts without forks, and ducts given in 'backwards' order. This would cause k iterations over the k-item array, making the total time cost of O(k^2).

To avoid the worst case you might sort the three input arrays by increasing toJunction[] values prior to the analysis. Then the actual analysis reduces to a single pass through a k-item array, so it takes a linear time O(k). Add the time of sorting, and the total complexity is O(k log k).