Get Time

   Problem Statement  

 Problem Statement for TallShoes

Problem Statement


A king of a mystical land likes to wear very tall shoes. The tall shoes are sometimes an inconvenience as they make traveling through the kingdom's road network difficult.

There are N cities in the kingdom. The cities are numbered 0 through N-1. The road network in the kingdom is connected: it is possible to get from any city to any other city by taking one or more roads. Each road in the network is bidirectional and connects two different cities. You are given the description of the road network in three int[]s: X, Y, and height, each with the same number of elements. For each valid i, there is a road that connects cities X[i] and Y[i]. The value height[i] is the height limit for that road: The king can travel along that road if and only if the height of his shoes is height[i] or less.

The king wants to walk from city 0 to city N-1. While doing so, he wants to wear shoes that are as tall as possible. Before he goes for the walk, he can increase the height limits for some roads. The king has a budget of B dollars for the modifications. Increasing the height limit of any road by k costs k^2 dollars. The height limit of each road can only be increased at most once.

You are given the int N, the int[]s X, Y and height, and the long B. Compute the maximum height of shoes the king may wear for his walk from city 0 to city N-1 after increasing the height limits appropriately.



Parameters:int, int[], int[], int[], long
Method signature:int maxHeight(int N, int[] X, int[] Y, int[] height, long B)
(be sure your method is public)


-N will be between 2 and 50, inclusive.
-from, to, height will have between N-1 and N*(N-1)/2 elements, inclusive.
-Each element of X, Y will be between 0 and N-1, inclusive.
-For all i, X[i] != Y[i].
-Each undirected edge X[i], Y[i] will appear at most once.
-Each element of height will be between 0 and 10^6, inclusive.
-The graph described by X and Y will be connected.
-B will be between 0 and 10^15, inclusive.


{0, 1, 0}
{1, 2, 2}
{3, 4, 2}
Returns: 4

In this example there are three roads: 0-1 (height limit 3), 1-2 (height limit 4), and 0-2 (height limit 2). The king has a budget of 1 dollar. The optimal way to use that budget is to increase the height limit for the 0-1 road from 3 to 4. After that change, the king can use shoes of height 4 and walk along the path 0-1-2.

{0, 1, 0}
{1, 2, 2}
{3, 4, 2}
Returns: 9
Here we can increase the last road's height by 7 which will allow the king to wear shoes of height 9. Note that the king is not required to spend the entire budget.
{0, 0, 3, 3, 4, 4, 4, 7, 7}
{1, 2, 1, 2, 3, 5, 6, 5, 6}
{1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000}
Returns: 2
Returns: 1047565
Returns: 999999

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 642 Round 1 - Division II, Level Three