Connection Status:
Competition Arena > BipartiteGraphGame

BipartiteGraphGame

SRM 667 · 2015-08-28 · by lg5293

SRM 667 · 2015-08-28 · by lg5293 · Search
Class Name: BipartiteGraphGame
Return Type: int[]
Method Name: getMoves
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

You have a bipartite graph. One partition of the graph consists of n red nodes, labeled 0 through n-1. The other partition consists of m blue nodes, labeled 0 through m-1. There are at least two nodes of each color. There are exactly n*m edges: each red vertex is connected to each blue vertex.

There is exactly one token on each node. Each token has a color and a number. At the beginning, each red node contains a red token and each blue node contains a blue token. The numbers on the red tokens are given in the int[] red with n elements. For each i, the token on the red node i has the number red[i]. The numbers on red tokens are a permutation of 0 through n-1. Similarly, the numbers on the blue tokens are a permutation of 0 through m-1 and they are given in the int[] blue.

You would like to move the tokens so that each token matches its node both in color and in number. That is, for each valid i the red node i should contain the red token i, and for each valid j the blue node j should contain the blue token j.

You can only move the tokens in a single way: In each turn, you can select one edge of the bipartite graph and exchange the tokens in the two nodes it connects.

For a while you played this game with the following additional rule: "During the game, you may only use each edge at most once." However, you then noticed that for some initial configurations it is not possible to win the game. Hence, you relaxed the rule slightly: you have allowed yourself to use at most one edge twice. In this new version of the game it can be shown that any valid test case (i.e., one conforming to the constraints specified below) has a solution that consists of at most 1,000 turns. Find and return any such solution.

More precisely, find and return any sequence of edges such that if you select those edges in that order you will reach the state in which each token is on its corresponding node. Note that this sequence does not have to be the shortest sequence possible: any valid sequence of at most 1,000 edges will be accepted. If your sequence contains X edges, return a int[] with 2X elements: for each edge, in order, write the number of the red node followed by the number of the blue node connected by the edge.

Constraints

  • n,m will be between 2 and 100, inclusive.
  • red will be a permutation of {0,...,n-1}.
  • blue will be a permutation of {0,...,m-1}.
Examples
0)
{0,1}
{0,1}
Returns: { }

Nothing needs to be done here.

1)
{1,0}
{0,1}
Returns: {0, 0, 1, 0, 0, 0 }

In the example output we selected the edges in the following order: red node 0 - blue node 0 red node 1 - blue node 0 red node 0 - blue node 0 Note that the edge 0-0 was used twice during the game. Here is a picture showing the moves made. The purple edge denotes which edge we chose in the current move. The color and numbers shown are the token value and colors. The background color represents the actual node colors, with the top row being nodes labeled 0, and bottom row being nodes labeled 1.

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

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

Coding Area

Language: C++17 · define a public class BipartiteGraphGame with a public method vector<int> getMoves(vector<int> red, vector<int> blue) · 101 test cases · 2 s / 256 MB per case

Submitting as anonymous