Connection Status:
Competition Arena > OldBridges

OldBridges

SRM 556 · 2012-06-05 · by wata

SRM 556 · 2012-06-05 · by wata · Graph Theory
Class Name: OldBridges
Return Type: String
Method Name: isPossible
Arg Types: (vector<string>, int, int, int, int, int, int)
Problem Statement

Problem Statement

Alice and Bob live in a country that consists of N islands. The islands are numbered 0 through N-1. Several pairs of islands are connected by bridges. Some of the bridges are very old. They will collapse after the second passage. The other bridges are new and never collapse. Only one person can cross a bridge at a time.

You are given a String[] bridges. Character j of element i of bridges is 'O' (uppercase letter o) if the island i and the island j are connected by an old bridge; 'N' if they are connected by a new bridge; and 'X' if they are not connected by a bridge.

Alice wants to make an round trips between the islands a1 and a2. That is, she wants to make an consecutive trips, where each trip starts at a1, gets somehow to a2, and after some more steps ends back at a1. At the same time, Bob wants to make bn round trips between the islands b1 and b2. Each round trip may use any sequence of consecutive bridges. Different round trips may, but don't have to, use the same sequence of bridges. Of course, each old bridge may only be used at most twice. (I.e., it may be used twice by Alice, or twice by Bob, or once by each of them, or just once, or not at all.)

You are given the String[] bridges and the ints a1, a2, an, b1, b2, and bn. If it is possible to plan all the round trips for Alice and Bob, return "Yes", otherwise return "No".

Constraints

  • bridges will contain between 4 and 50 elements, inclusive.
  • Each element of bridges will contain exactly N characters, where N is the number of elements of bridges.
  • Each character in each element of bridges will be 'O', 'N', or 'X'.
  • For each i, the i-th character of the i-th element of bridges will be 'X'.
  • For each i and j, the i-th character of the j-th element of bridges will be equal to the j-th character of the i-th element of bridges.
  • The country will be connected, i.e., there will exist a path consisting of one or more bridges between any pair of islands.
  • a1, a2, b1, and b2 will be between 0 and N-1, inclusive.
  • a1, a2, b1, and b2 will be pairwise distinct.
  • an and bn will be between 1 and 50, inclusive.
Examples
0)
{"XOXX","OXOX","XOXO","XXOX"}
0
1
1
2
3
1
Returns: "Yes"

Alice can travel from the island 0 to the island 1 and go back to the island 0, and Bob can travel from the island 2 to the island 3 and go back to the island 2.

1)
{"XOXX","OXOX","XOXO","XXOX"}
0
2
1
1
3
1
Returns: "No"

In order to make a round trip between the island 0 and the island 2, Alice must use the old bridge between the island 1 and the island 2 twice. So Bob cannot travel from the island 1 to the island 3.

2)
{"XOXO","OXOX","XOXO","OXOX"}
0
2
1
1
3
1
Returns: "Yes"

One possible pair of tours is 0->1->2->3->0 for Alice and 1->2->3->0->1 for Bob.

3)
{"XNXO","NXOX","XOXO","OXOX"}
0
2
1
1
3
2
Returns: "No"
4)
{"XOXOO","OXOXO","XOXOO","OXOXO","OOOOX"}
0
2
2
1
3
2
Returns: "Yes"

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

Coding Area

Language: C++17 · define a public class OldBridges with a public method string isPossible(vector<string> bridges, int a1, int a2, int an, int b1, int b2, int bn) · 122 test cases · 2 s / 256 MB per case

Submitting as anonymous