Connection Status:
Competition Arena > GameOnGraph

GameOnGraph

SRM 677 · 2015-11-03 · by cgy4ever

SRM 677 · 2015-11-03 · by cgy4ever · Graph Theory
Class Name: GameOnGraph
Return Type: int[]
Method Name: findSolution
Arg Types: (vector<string>, vector<int>)
Problem Statement

Problem Statement

You are given a strongly connected tournament graph on n nodes, labeled 0 through n-1.

A tournament graph is a special directed graph. In a tournament graph there are no self-loops and no multiple edges. Additionally, for each pair of nodes (i, j) the graph contains exactly one of the two possible edges between i and j. In other words, tournament graphs are precisely those graphs that can be obtained by taking a complete undirected graph and choosing a direction for each of its edges.

A graph is strongly connected iff you can reach any node from any other node. That is, for each pair of nodes (i, j) the graph contains a path from i to j.

The graph is given as a String[] graph. For each i and j, graph[i][j] is 'Y' if the graph contains the edge from i to j, or 'N' if that edge is not present in the graph.

We will use the graph as a game board for a game with tokens. At the beginning of the game, we leave node 0 empty and we place exactly one token onto each other node. For each i, the token initially placed on node i will have the label i.

The game is played by moving the tokens. In each step you may choose one of the tokens and slide it along an edge onto the node that is currently empty. (Formally, in each step you must choose nodes x and y such that node y is empty and there is an edge from x to y. Then, you move the token from x to y.)

You are given a int[] p that contains a permutation of 0 through n-1 with p[0]=0. This permutation describes one particular configuration of tokens: Node 0 must be empty and for each i > 0 node i must contain the token labeled p[i].

The goal of the game is to reach the configuration described by p in at most 2,500 steps. It is guaranteed that for the given constraints such a sequence of steps always exists. Find and return any valid sequence of steps that wins the game.

If your solution consists of k steps, please return a int[] with k elements: for each step, in order, the index of the node from which you moved the token. In other words, whenever you move a token from node x to node y, append x to the return value.

Constraints

  • n will be between 3 and 30, inclusive.
  • graph will contain exactly n elements.
  • Each element in graph will have exactly n characters.
  • Each character in graph will be 'Y' or 'N'.
  • For each valid i, graph[i][i] = 'N'.
  • If i!=j then exactly one of {graph[i][j], graph[j][i]} will be 'Y'.
  • The graph will be strongly connected (as defined in the statement).
  • p will contain exactly n elements.
  • Each element in p will be between 0 and n-1, inclusive.
  • p will be a permutation.
  • p[0] = 0.
Examples
0)
{"NYN",
 "NNY",
 "YNN"}
{0,2,1}
Returns: {2, 1, 0 }

The example output describes the following sequence of moves: Move the token from node 2 onto the currently empty node. Move the token from node 1 onto the currently empty node. Move the token from node 0 onto the currently empty node. Let's simulate this sequence of moves to see what happens. In the beginning, the configuration of tokens is {0, 1, 2}. That is, node 0 is empty. We move a token from node 2 onto the currently empty node 0. This is a valid move because graph[2][0] is 'Y'. After the move the configuration of tokens is {2, 1, 0}. That is, node 0 contains token 2, node 1 contains token 1, and node 2 is the currently empty node. We move a token from node 1 onto the currently empty node 2. Again, we may check that this is a valid move because graph[1][2] is 'Y'. After the second move the configuration of tokens is {2, 0, 1}. Finally, we move a token from node 0 onto the currently empty node 1. This produces the desired configuration {0, 2, 1}.

1)
{"NYN",
 "NNY",
 "YNN"}
{0,1,2}
Returns: {2, 1, 0, 2, 1, 0 }

Note that any valid output will be accepted. For example, in this test case you may also return {}: as the desired permutation is the same as the starting configuration, we can win the game without making any moves.

2)
{"NYYN",
 "NNYY",
 "NNNY",
 "YNNN"}
{0,3,2,1}
Returns: {3, 1, 0 }
3)
{"NNYYNNNY",
 "YNYYNYYY",
 "NNNNYYNY",
 "NNYNYNYY",
 "YYNNNYNY",
 "YNNYNNNN",
 "YNYNYYNY",
 "NNNNNYNN"}
{0,1,4,5,2,3,6,7}
Returns: {4, 2, 0, 5, 2, 3, 5, 2, 3, 0 }
4)
{"NNYYNNNY",
 "YNYYNYYY",
 "NNNNYYNY",
 "NNYNYNYY",
 "YYNNNYNY",
 "YNNYNNNN",
 "YNYNYYNY",
 "NNNNNYNN"}
{0,1,2,3,4,5,6,7}
Returns: {5, 7, 1, 4, 2, 6, 3, 0, 5, 7, 1, 4, 2, 6, 3, 0, 5, 7, 1, 4, 2, 6, 3, 0, 5, 7, 1, 4, 2, 6, 3, 0, 5, 7, 1, 4, 2, 6, 3, 0, 5, 7, 1, 4, 2, 6, 3, 0, 5, 7, 1, 4, 2, 6, 3, 0 }

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

Coding Area

Language: C++17 · define a public class GameOnGraph with a public method vector<int> findSolution(vector<string> graph, vector<int> p) · 81 test cases · 2 s / 256 MB per case

Submitting as anonymous