PowerOutage
SRM 144 · 2003-04-30 · by leadhyena_inran
Problem Statement
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
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.
{0}
{1}
{10}
Returns: 10
The simplest sewer system possible. Your technician would first check transformer 0, travel to junction 1 and check transformer 1, completing his check. This will take 10 minutes.
{0,1,0}
{1,2,3}
{10,10,10}
Returns: 40
Starting at junction 0, if the technician travels to junction 3 first, then backtracks to 0 and travels to junction 1 and then junction 2, all four transformers can be checked in 40 minutes, which is the minimum.
{0,0,0,1,4}
{1,3,4,2,5}
{10,10,100,10,5}
Returns: 165
Traveling in the order 0-1-2-1-0-3-0-4-5 results in a time of 165 minutes which is the minimum.
{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
Visiting junctions in the order 0-3-0-1-2-1-0-4-5-4-6-7-9-7-10-7-8-11 is optimal, which takes (10+10+10+10+10+10+100+5+5+1+1+1+1+1+1+100+5) or 281 minutes.
{0,0,0,0,0}
{1,2,3,4,5}
{100,200,300,400,500}
Returns: 2500
{0,0,0,1,3,3,3,6,7,1,6,9,11,2,5,9,8,4,1,7,14,14,19,17,10,0,22,19,22,4,2,21,30,11,15,15,28,2,0,16,4,34}
{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}
{1545174,710331,1502620,1852105,896652,899215,1652061,920516,422581,1473180,877279,1788544,1633870,1649520,431786,1995351,706354,1805296,662289,799528,694758,1453779,1956529,1869395,1220390,1884529,1319130,625564,1587407,1874797,1410594,487925,1907863,1330317,1255604,1901852,353482,1528028,1219052,1918150,892447,39622}
Returns: 98420169
These first thirty tests are random tests but the nodes are in order of easy construction.
{0,0,13,9,3,4,5,1,5,3,2,0,0,0,4,13,0}
{9,4,15,11,16,14,7,6,12,13,10,2,1,5,8,17,3}
{1046279,1311183,429331,1140774,1468021,49084,791438,304381,1675432,1353849,889525,391384,1018989,170090,53233,996444,194951}
Returns: 24023532
The next 20 testcases are in similar format to the 30 before it, but the order of the edges are jumbled up.
{1,3,3,0,0,3,6,0,0,4}
{4,5,10,1,7,6,9,3,2,8}
{24,75,49,99,2,66,19,23,4,83}
Returns: 682
These last 20 tests use randomization like the last 20, but the duct lengths are limited to [1-100] for 95% of the time. 5% of the time it chooses a duct length [1-2000000]. This will create spikes in the tree that will discourage edge counters.
Submissions are judged against all 87 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PowerOutage with a public method int estimateTimeOut(vector<int> fromJunction, vector<int> toJunction, vector<int> ductLength) · 87 test cases · 2 s / 256 MB per case