CavePassage

SRM 422 · 2008-10-18 · by mateuszek

SRM 422 · 2008-10-18 · by mateuszek · Graph Theory, Search, Simple Math

Show categories

Class Name: CavePassage

Return Type: int

Method Name: minimalTime

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

Problem Statement

Several travelers are standing at the entrance of a dark cave. The travelers must all pass through the cave and stand together at the exit. Unfortunately, a variety of circumstances can make it impossible for them to all pass through the cave together at the same time. Therefore, they may have to take turns going through the cave in smaller groups. There is only one map though, and it is impossible to navigate the cave without it, so whenever a group of travelers is inside the cave, one member of that group must be holding the map.

When a group of travelers walks through the cave, either from the entrance or the exit, they must traverse an old bridge to get to the other side of the cave. The entire group inside the cave must cross the bridge together at the same time. The bridge cannot hold more than bridgeStrength kilograms, or it will collapse. You are given a int[] travelersWeights, where the i-th element is the weight of the i-th traveler in kilograms.

Travelers may walk through the cave alone. Although, when travelers walk through the cave in a group of two or more, each traveler must trust at least one of the other travelers in the group. You are given a String[] trustTable, where the j-th character of the i-th element is 'Y' if traveler i trusts traveler j, and 'N' otherwise. Note that the trust relation is not necessarily symmetric.

Travelers walk at different speeds, but when they go through the cave, they must stick together and walk at the same speed. Therefore, when a group of travelers walks through the cave, they must walk at the speed of the slowest traveler in the group. You are given a int[] travelersTimes, where the i-th element is the amount of time it takes the i-th traveler to walk through the cave in any direction.

Return the minimal total time required for all the travelers to end up together at the exit of the cave. If it is impossible, return -1 instead.

Constraints

travelersWeights will contain between 1 and 13 elements, inclusive.
Each element of travelersWeights will be between 1 and 1000, inclusive.
travelersTimes will contain the same number of elements as travelersWeights.
Each element of travelersTimes will be between 1 and 1000, inclusive.
trustTable will contain the same number of elements as travelersWeights.
Each element of trustTable will contain exactly n characters, where n is the number of elements in trustTable.
Each element of trustTable will contain only uppercase letters 'Y' and 'N'.
The i-th character of the i-th element of trustTable will always be 'Y'.
bridgeStrength will be between 1 and 5000, inclusive.

Examples

{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
{ "YYYYYYYYYYYYY","YYYYYYYYYYYYY","YYYYYYYYYYYYY","YYYYYYYYYYYYY","YYYYYYYYYYYYY","YYYYYYYYYYYYY","YYYYYYYYYYYYY","YYYYYYYYYYYYY","YYYYYYYYYYYYY","YYYYYYYYYYYYY","YYYYYYYYYYYYY","YYYYYYYYYYYYY","YYYYYYYYYYYYY" }
13
Returns: 1

{ 1, 1, 1 }
{ 2, 3, 4 }
{ "YYY", "YYY", "YYY" }
2
Returns: 9

The travelers can achieve the goal as follows. First, traveler 0 and traveler 2 go through the cave together. It normally takes 2 time units for traveler 0 to go through the cave, and it takes 4 time units for traveler 2. Since they are traveling together in a group, they must walk at the speed of the slower traveler. So, after 4 time units, both travelers are at the exit. Then, traveler 0 takes the map and goes back through the cave to the entrance. This time, it only takes 2 time units because he is alone. Finally, traveler 0 and traveler 1 go through the cave together in 3 time units and all the travelers end up together at the exit. The total time is 4 + 2 + 3 = 9.

{ 1, 1, 1 }
{ 2, 3, 4 }
{ "YYY", "YYY", "NYY" }
2
Returns: 10

Here things become a little bit more complicated, because traveler 2 doesn't trust traveler 0.

{ 1, 1, 1 }
{ 7, 13, 19 }
{ "YYN", "NYY", "YNY" }
3
Returns: 19

{ 5, 3, 2, 1, 1 }
{ 3, 3, 5, 7, 7 }
{ "YYYYY", "YYYYY", "YYYYY", "YYYYY", "YYYYY" }
10
Returns: 13

28)

{45,30,129,105,107}
{130,366,355,195,259}
{"YNNYN",
"NYNNN",
"NNYYY",
"NNNYY",
"NNNYY"}
1393
Returns: 1369

In the following 10 cases it's wrong to always go back alone.

38)

{40,403,545,533,114,324,544,319,112,315,488,52,479}
{1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}
{"YNNNYNNNNNNNN",
"YYNNNYNNYNNNN",
"NYYNNNNNNNNYN",
"YNNYNNNYNNNNN",
"NNNNYNNNNNNNN",
"NNNNNYNYNYNNN",
"NNNNNNYNNNNNN",
"NNNNNNNYNNNNN",
"NNNNNNNNYNNNN",
"NNNYNNNNNYNNN",
"NNNNNNNNNNYNN",
"NYYNYNNNYNNYN",
"YYNYNNNNNNNNY"}
4907
Returns: 45000

45 moves to do

39)

{43}
{23}
{"Y"}
43
Returns: 23

some trivial cases

43)

{632,538,274}
{60,59,60}
{"YYY",
"YYY",
"YYY"}
1325
Returns: 179

In the following cases it's wrong to mark states visited when putting them into the queue.

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

Coding Area

Language: C++17 · define a public class CavePassage with a public method int minimalTime(vector<int> travelersWeights, vector<int> travelersTimes, vector<string> trustTable, int bridgeStrength) · 115 test cases · 2 s / 256 MB per case