Connection Status:
Competition Arena > TallShoes

TallShoes

SRM 642 · 2014-08-25 · by lg5293

SRM 642 · 2014-08-25 · by lg5293 · Graph Theory, Search
Class Name: TallShoes
Return Type: int
Method Name: maxHeight
Arg Types: (int, vector<int>, vector<int>, vector<int>, long long)
Problem Statement

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.

Constraints

  • 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.
Examples
0)
3
{0, 1, 0}
{1, 2, 2}
{3, 4, 2}
1
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.

1)
3
{0, 1, 0}
{1, 2, 2}
{3, 4, 2}
52
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.

2)
8
{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}
3
Returns: 2
3)
10
{0,1,2,3,4,5,6,7,8}
{1,2,3,4,5,6,7,8,9}
{0,0,0,0,0,0,0,0,0}
9876543210123
Returns: 1047565
4)
6
{0,0,0,0,0,1,1,1,1,2,2,2,3,3,4}
{1,2,3,4,5,2,3,4,5,3,4,5,4,5,5}
{999999,986588,976757,988569,977678,999999,967675,947856,955856,999999,975956,956687,999999,979687,999999}
0
Returns: 999999

Submissions are judged against all 99 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TallShoes with a public method int maxHeight(int N, vector<int> X, vector<int> Y, vector<int> height, long long B) · 99 test cases · 2 s / 256 MB per case

Submitting as anonymous