JOIN
Get Time

   Problem Statement  

 Problem Statement for BipartiteGraphGame

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.

 

Definition

    
Class:BipartiteGraphGame
Method:getMoves
Parameters:int[], int[]
Returns:int[]
Method signature:int[] getMoves(int[] red, int[] blue)
(be sure your method is public)
    
 

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:

  1. red node 0 - blue node 0
  2. red node 1 - blue node 0
  3. 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 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 667 Round 1 - Division I, Level Three