RoadsReform | Topcoder Archive

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.

Definition

Class:: RoadsReform
Method:: getMax
Parameters:: int, int[], int[], int[], int[]
Returns:: int
Method signature:: int getMax(int n, int[] e1, int[] e2, int[] s, int[] t)
(be sure your method is public)

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).

{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

{1, 2, 7, 9, 10, 11, 11, 11, 12, 12, 12, 13, 13, 14, 14, 15, 16, 16, 17, 17, 18, 19, 19, 19, 19}

{0, 1, 5, 8, 4, 3, 8, 9, 5, 7, 10, 4, 10, 0, 6, 14, 0, 15, 3, 9, 1, 1, 3, 11, 13}

{2, 6, 7, 9, 12, 13, 14, 16, 19, 19}

{7, 19, 12, 15, 16, 4, 7, 0, 13, 14}

Returns: 7

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)2024, Topcoder, Inc. All rights reserved.