RoadsReform

TCO 2014 Semifinal 2 · 2014-03-26 · by w10d

TCO 2014 Semifinal 2 · 2014-03-26 · by w10d · Graph Theory

Show categories

Class Name: RoadsReform

Return Type: int

Method Name: getMax

Arg Types: (int, vector<int>, vector<int>, vector<int>, vector<int>)

Problem Statement

King Kazimierz is going to reorganize the road infrastructure in his kingdom. There are n towns in the kingdom. The towns are labeled 0 through n-1. Some pairs of towns are connected by bidirectional dirt roads. It is possible to travel between every pair of towns using the roads.

You are given a description of the roads in the int[]s e1 and e2. For each valid i, there is a road between the towns e1[i] and e2[i].

The king wants to modernize all the roads. Unfortunately, after modernization the roads won't be wide enough for two-way traffic, so each of the roads will have to become a one-way road. The king now needs to choose the direction for each of the new one-way roads.

Kazimierz's adviser Zbyszek has prepared a list of strategic connections. You are given this list in the int[]s s and t. For each valid i, being able to travel (either directly or indirectly) from the town s[i] to the town t[i] is important for the country.

For any assignment of directions to the current roads we can compute its score: the number of strategic connections that will be possible. Return the largest possible score.

Constraints

n will be between 2 and 50, inclusive.
e1 and e2 will have the same number of elements which will be between 1 and 500, inclusive.
No road will appear twice. Pairs (u, v) and (v, u) describe the same road.
There will be no loops i.e. for each pair (u, v) describing a road, u and v will be different.
The graph represented by e1 and e2 will be connected.
s and t will have the same number of elements which will be between 1 and 20, inclusive.
No connection will appear twice. Pairs (u, v) and (v, u) describe different connections.
For each i, t[i] and s[i] will be different.
Each element of e1, e2, s and t will be between 0 and n - 1, inclusive.

Examples

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

We have two towns and a single road that connects them. We also have two strategic connections: "getting from 0 to 1" and "getting from 1 to 0". Regardless of which direction we choose for the 0-1 road, we will only enable one of the two strategic connections.

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

An optimal solution here is to direct the roads as follows: from 0 to 2, from 1 to 2, and from 2 to 3. This will make two strategic connections possible: people will be able to travel from 0 to 3 (via 2), and they will be able to travel from 1 to 3 (also via 2).

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

Here it is possible to have both strategic connections at the same time. One such solution is to choose the directions 0->1, 1->2, 3->1, 2->4, 4->3, and 5->4. If the king chooses these directions for the roads, people will be able to travel from 0 to 4 (via 1 and 2) and also from 5 to 1 (via 4 and 3).

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

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

25)

10
{0,1,2,3,0,1,2,1,1,3}
{1,2,3,0,4,5,6,7,8,9}
{4,6,8}
{5,7,9}
Returns: 3

Counterexample for SnapDragon's original DFS-based solution.

26)

24
{8,20,13,3,10,22,12,2,5,10,3,0,22,12,16,6,8,21,2,21,1,19,11,1,18,18,9,14,3}
{17,21,1,1,8,19,13,5,7,7,21,6,3,23,11,4,14,16,10,10,0,15,20,4,23,13,17,9,15}
{1,0,5,3,13,20,11,22,18,23,6,19,2,10,21}
{0,4,2,22,18,16,20,15,12,18,0,22,7,2,20}
Returns: 15

High-probability failure for DFS solutions.

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

Coding Area

Language: C++17 · define a public class RoadsReform with a public method int getMax(int n, vector<int> e1, vector<int> e2, vector<int> s, vector<int> t) · 269 test cases · 2 s / 256 MB per case