Connection Status:
Competition Arena > KingdomMap

KingdomMap

SRM 439 · 2009-04-30 · by it4.kp

SRM 439 · 2009-04-30 · by it4.kp · Dynamic Programming, Graph Theory
Class Name: KingdomMap
Return Type: int[]
Method Name: getRoadsToRemove
Arg Types: (int, vector<string>)
Problem Statement

Problem Statement

The king of Byteland always gets confused when he sees maps of his own kingdom because roads often intersect with each other. So, he issued an order to create a new map. He wants the map to contain two vertical columns, each containing a list of towns. Each town in the kingdom must appear exactly once in the map. Each road in the map must be a straight line segment connecting a town from one column to a town in the other column. No two roads are allowed to intersect each other, except at their endpoints if they share a town.

Your task is to create this new map. You are given an int n, the number of towns in the kingdom (numbered 0 to n-1), and a String[] roads. Concatenate the elements of roads to get a String containing a comma-separated list of roads. Each road is formatted "u v" (quotes for clarity), where u and v are the numbers of the towns connected by that road. Roads are bidirectional, and there are no cycles. If it is impossible to draw the map so that it contains all of the original roads, you can choose to exclude some of the roads. You must exclude the minimum possible number of roads necessary to create a valid map. Return a int[] containing the numbers of the excluded roads (the roads are numbered starting from 0 in the same order as they appear in the concatenated String). If there are multiple solutions, return the one that comes first lexicographically.

Notes

  • int[] A comes before int[] B lexicographically if and only if A contains a smaller number at the first position where they differ.
  • A cycle is a sequence of cities that contains at least 3 cities and starts and ends in the same city. Each two cities that are consecutive in the sequence must be connected by a road and all these roads must be distinct.

Constraints

  • n will be between 1 and 300, inclusive.
  • roads will contain between 0 and 50 elements, inclusive.
  • Each element of roads will contain between 1 and 50 characters, inclusive.
  • The elements of roads, when concatenated together, will contain a comma-separated list of roads. Let's call the concatenated string R.
  • R will contain between 0 and n-1 roads, inclusive.
  • Each road in R will be formatted "u v" (quotes for clarity), where u and v are integers between 0 and n-1, inclusive, with no extra leading zeroes, and u is less than v.
  • All roads in R will be distinct.
  • There will be no cycles in the corresponding graph.
Examples
0)
5
{"0 1,1 2,2 3"}
Returns: { }

There is no need to exclude any roads.

1)
7
{"0 1,1 2,2 3,3 4,5 6,2 5"}
Returns: {0 }

In this case, we can draw a valid map after excluding any single road. Since we need the lexicographically smallest answer, we exclude the first road in the list, which has the number 0.

2)
20
{"8 17,9 12,4 7,2 7,2 19,3 12,6 12,1 9,5 18,0 12,6 1", "6,0 11,3 14,10 15,12 13,13 18,13 19,15 17,15 19"}
Returns: {1, 3, 5, 14 }

Note that you need to concatenate all elements of roads. When concatenating elements, don't put anything between them. In this case the town "16" in the road "6 16" was cut in half between two elements of roads.

3)
1
{}
Returns: { }

roads can be empty.

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

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

Coding Area

Language: C++17 · define a public class KingdomMap with a public method vector<int> getRoadsToRemove(int n, vector<string> roads) · 41 test cases · 2 s / 256 MB per case

Submitting as anonymous