Connection Status:
Competition Arena > SpaceshipEvacuation

SpaceshipEvacuation

SRM 476 · 2009-12-03 · by gojira_tc

SRM 476 · 2009-12-03 · by gojira_tc · Dynamic Programming, Graph Theory
Class Name: SpaceshipEvacuation
Return Type: int
Method Name: additionalCabins
Arg Types: (int, vector<string>, int)
Problem Statement

Problem Statement

Manao is an engineer of a new spaceship. He is responsible for crew safety, particularly during a possible evacuation. The spaceship consists of N units numbered from 0 to N-1. The units are connected by passages, but during evacuation, moving through them is too slow and therefore is prohibited. Some pairs of units are connected by tunnels which contain emergency cabins. There are several emergency cabins at each end of each tunnel. A cabin is designed for a single person and may only be used once for security reasons. A cabin at one end of a tunnel can only be used to reach the other end of that same tunnel.

The tunnel network has a special layout. Consider a sequence of units U0, U1, ..., UK with K &ge 3 and U0=UK. If all U0, U1, ..., UK-1 are pairwise distinct and for each i, 0 &le i &lt K, Ui and Ui+1 are connected by a tunnel, this sequence is called a cycle. A cycle is called canonical if U0 &lt Ui for 1 &le i &lt K and U1 &lt UK-1. Each unit in the spaceship will be a part of at most one canonical cycle. The tunnel network is given as String[] tunnelNetwork, where each element describes a tunnel and contains four space-separated integers A, B, C, D. This means that there is a tunnel between units A and B and there are C emergency cabins in the tunnel from unit A's side and D emergency cabins from unit B's side.

The crew of the spaceship consists of crewSize members. Each of them might be in any of the N units when the evacuation is announced. Unit 0 is connected to the rescue boat, so every person reaching this unit is considered evacuated. The distribution of emergency cabins within the tunnels is called an evacuation plan. An evacuation plan is called acceptable if there exists a way to evacuate the whole crew for any possible distribution of crew members over the units at the moment when the evacuation is announced. The current evacuation plan might not be acceptable. Manao may demand a number of additional emergency cabins at each end of each tunnel, but he is not allowed to change the location of emergency cabins that are already present in the spaceship. Return the minimum total number of emergency cabins Manao has to add to obtain an acceptable evacuation plan from the current one. If it is impossible, return -1.

Constraints

  • N will be between 2 and 50, inclusive.
  • tunnelNetwork will contain between 1 and 50 elements, inclusive.
  • Each element of tunnelNetwork will contain between 7 and 50 characters, inclusive.
  • Each element of tunnelNetwork will be formatted "A B C D" (quotes for clarity), where A, B, C and D are integers formatted without extra leading zeros.
  • In each element of tunnelNetwork, A and B will be distinct integers between 0 and N-1, inclusive.
  • In each element of tunnelNetwork, C and D will each be between 0 and 100,000, inclusive.
  • The unordered pairs {A,B} in tunnelNetwork will be distinct.
  • Each unit will be a part of at most one canonical cycle.
  • crewSize will be between 1 and 100,000, inclusive.
Examples
0)
3
{"0 1 5 3",
 "2 1 0 0"}
5
Returns: 7

Adding 2 cabins to the tunnel between units 0 and 1 from unit 1's side and 5 cabins to the tunnel between units 2 and 1 from unit 2's side ensures that wherever the crew members happen to be when evacuation begins, they will be able to reach unit 0.

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

An optimal evacuation scheme can be obtained by adding 3 emergency cabins to the 0-1 tunnel and 1 emergency cabin to the 0-2 tunnel.

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

One of the possible ways to obtain an optimal evacuation scheme is to add 5 cabins to the 1-2 tunnel from unit 2's side and 1 cabin to the 2-3 tunnel from unit 3's side.

3)
10
{"0 1 11 101",
 "1 2 0 100",
 "2 3 20 100",
 "3 4 0 107",
 "4 1 66 0",
 "3 5 104 2",
 "4 6 82 0",
 "5 7 25 25",
 "7 8 14 42",
 "8 9 0 94",
 "9 5 17 92"}
110
Returns: 376
4)
3
{"0 1 0 0"}
1
Returns: -1

The only crew member has no chance if he is in unit 2 at the moment of evacuation.

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

Coding Area

Language: C++17 · define a public class SpaceshipEvacuation with a public method int additionalCabins(int N, vector<string> tunnelNetwork, int crewSize) · 63 test cases · 2 s / 256 MB per case

Submitting as anonymous