TopCoder problem "ByteLand" used in SRM 345 (Division I Level Three)



Problem Statement

    

The Kingdom of Byteland consists of several cities connected by bidirectional roads. There are castles standing in some of the cities. Byteasar, the King of Byteland is unhappy with his kingdom's defensive power, so he decided to build k additional castles (he can only afford that many).

Whenever one of the cities is attacked by the enemy, the army from the nearest castle must come with help. The enemy is smart, so it will always find and attack the city that is the farthest away from its nearest castle. Therefore, the distance from the attacked city to its nearest castle must be as small as possible. Your job is to calculate and return this distance, assuming that you can decide where to build the k additional castles.

The cities are built in a specific manner. Each city has a main gate and several other gates. Every gate is connected to another gate by a road. It is possible that two gates of the same city are connected (see example 2). For defensive reasons, every road has exactly one main gate on one of its ends. Please note that every road can be traversed in both directions.

The road going out of the main gate of the i-th city leads to the road[i]'th city and is distance[i] miles long. The int[] castles contains the 0-based indices of the cities in which a castle is already built.

 

Definition

    
Class:ByteLand
Method:buildCastles
Parameters:int[], int[], int[], int
Returns:int
Method signature:int buildCastles(int[] road, int[] distance, int[] castle, int k)
(be sure your method is public)
    
 

Constraints

-road will contain between 2 and 50 elements, inclusive (let's call this number n).
-road and distance will contain the same number of elements.
-Each element of road will be between 0 and n-1, inclusive.
-Each element of distance will be between 1 and 10^6, inclusive.
-k will be between 1 and n, inclusive.
-castle will contain between 0 and n-k elements, inclusive.
-Each element of castle will be between 0 and n-1, inclusive.
-The elements of castle will be distinct.
-It will be possible to build the castles in such a way that you can always reach a castle from each city.
 

Examples

0)
    
{1,2,3,4,0}
{1,1,1,1,1}
{}
1
Returns: 2
Building the castle in any of the cities results in the maximum distance from a city to a castle being 2.
1)
    
{1,2,0}
{1,2,3}
{2}
1
Returns: 1
2)
    
{0,1}
{1,1}
{1}
1
Returns: 0
3)
    
{0,2,0,0,2,2,8,3,8,7}
{10,9,1,8,1,3,7,2,8,1}
{3,4,6}
3
Returns: 3
4)
    
{1, 0}
{5, 10}
{}
1
Returns: 5

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7239

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10669&pm=7239

Writer:

rusolis

Testers:

PabloGilberto , brett1479 , Olexiy , ged

Problem categories:

Graph Theory, Greedy