SRM 590 1 1000 FoxAndCity

Problem Statement

There is a country with n cities, numbered 0 through n-1. City 0 is the capital. The road network in the country forms an undirected connected graph. In other words: Some pairs of cities are connected by bidirectional roads.
For every city there is at least one sequence of consecutive roads that leads from the city to the capital. (Whenever two roads need to cross outside of a city, the crossing is done using a bridge, so there are no intersections outside of the cities.)

You are given a String[] linked that describes the road network. For each i and j, linked[i][j] is 'Y' if the cities i and j are already connected by a direct road, and it is 'N' otherwise.

The distance between two cities is the smallest number of roads one needs to travel to get from one city to the other. The people living outside of the capital are usually unhappy about their distance from the capital. You are also given a int[] want with n elements. For each i, want[i] is the desired distance between city i and the capital (city 0).

Fox Ciel is in charge of building new roads. Each new road must again be bidirectional and connect two cities. Once the new roads are built, the citizens will evaluate how unhappy they are with the resulting road network:
For each i: Let real[i] be the new distance between city i and the capital. Then the people in city i increase the unhappiness of the country by (want[i] - real[i])^2.

Return the minimal total unhappiness Ciel can achieve by building some (possibly zero) new roads.


(be sure your method is public)



Test cases

  1. input
    • linked {"NYN",
    • want { 0, 1, 1 }
    Returns 0
    Ciel can build a road between cities 0 and 2. Then real[1]=1, real[2]=1, and the total unhappiness is 0.
  2. input
    • linked {"NYNN",
    • want { 0, 3, 3, 3 }
    Returns 5
    The optimal solution is not to build any new roads. Then the total unhappiness will be (3-1)^2 + (3-2)^2 + (3-3)^2 = 5.
  3. input
    • linked {"NYNNNY",
    • want { 0, 2, 2, 2, 2, 2 }
    Returns 2
    One of the optimal solutions is to build a road between cities 1 and 3.
  4. input
    • linked {"NYY",
    • want { 0, 0, 0 }
    Returns 2
  5. input
    • linked {"NYNNNN",
    • want { 0, 1, 2, 3, 0, 3 }
    Returns 3
  6. input
    • linked {"NYNNNN",
    • want { 0, 1, 2, 4, 0, 4 }
    Returns 6
  7. input
    • linked {"NYNYYYYYYYY",
    • want { 0, 1, 2, 0, 0, 5, 1, 3, 0, 2, 3 }
    Returns 28

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)2003, TopCoder, Inc. All rights reserved.