Connection Status:
Competition Arena > MagicianTour

MagicianTour

SRM 191 · 2004-04-24 · by Ishan

SRM 191 · 2004-04-24 · by Ishan · Dynamic Programming, Graph Theory
Class Name: MagicianTour
Return Type: int
Method Name: bestDifference
Arg Types: (vector<string>, vector<int>)
Problem Statement

Problem Statement

You are a magician who has two different shows. You are planning a tour of a series of cities. Given the population of each city and the roads between cities, you must plan the tour such that no two cities directly connected by a road are assigned the same show and such that the difference between the number of people who see show 1 and those who see show 2 is minimized. You have to return the difference between the number of people who will see show 1 and those who will see show 2.

The roads between the cities are specified in the String[] roads. roads[i][j] is '1' if there is a road between the ith and jth cities and is '0' if there is no road. You are guaranteed that you can pull this off. (You can schedule the shows such that no two adjacent cities are assigned the same show.) Keep in mind that each city must be assigned one of the two shows. The population of each city is specified by the int[] populations whose ith element is the population of the ith city.

Notes

  • You, the magician, can travel between two cities regardless of whether or not they are connected by a road.

Constraints

  • populations contains between 1 and 50 elements, inclusive.
  • roads contains exactly n elements, each of which has exactly n characters, where n is the number of elements in populations.
  • Each element of populations will be between 0 and 20, inclusive.
  • Each element of roads will only contain the characters '0' and '1'.
  • You are guaranteed that you can schedule the shows such that no two adjacent cities are assigned the same show.
  • No city will have a road to itself.
  • The graph is undirected. Hence, if there is a road from city a to city b then there has to be a road from city b to city a. As a result, roads[i][j] and roads[j][i] must be the same.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{"01","10"}
{15,20}
Returns: 5

There are two cities of populations 15 and 20. Perform show 1 in the first and show 2 in the second or vice versa.

1)
{"0100",
"1000",
"0001",
"0010"}
{2,4,1,5}
Returns: 2
2)
{"0100",
 "1000",
 "0001",
 "0010"}
{2,4,2,4}
Returns: 0

There are four cities of populations 2, 4, 2 and 4. Perform show 1 in the first and fourth cities and perform show 2 in the second and third cities.

3)
{"0010",
 "0001",
 "1000",
 "0100"}
{2,2,2,2}
Returns: 0
4)
{"000",
 "000",
 "000"}
{6,7,15}
Returns: 2

There are no roads! To keep it balanced, perform show 1 in the first and second cities and show 2 in the third city.

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

Coding Area

Language: C++17 · define a public class MagicianTour with a public method int bestDifference(vector<string> roads, vector<int> populations) · 30 test cases · 2 s / 256 MB per case

Submitting as anonymous