CareerCup

Write an algorithm to create tables of a given set of players (i.e divide the players into groups) for a game in the following manner. Each table will have 6 players. Total number of players will be a multiple of 6. There are some conditions that must be fulfilled to decide which player takes which table. These conditions are defined later and requires some definitions that we will look into first.

'Distance' between the players:
Since these players have been playing with each other in the past, we have history (available in a data set) about who played with whom in the past. Using this player game history we can plot a graph of players where each player is a node in the graph. A player is connected to another player if they have played on the same table in the past. In such a case distance between them is 1.

For example: If Pi and Pj have played on the same table in the past then they are connected with each other and 'Distance' between Pi and Pj is 1. Distance between any 2 players is defined as length of the shortest path between 2 players. If 2 players are not connected then distance between them is same as maximum of distance between any 2 players + 1

Degree of separation of a table
Degree of separation of a table is defined as sum of (Distances of all players taken 2 at a time)
Example: For a table of 6 players: Degree of separation = Sum of all 15 distances (6 choose 2)

The condition on table formation is:
We have to create tables (i.e divide the players into groups) such that Sum of (degree of separation of all the tables) is minimum.

The constraints on data size:
Number of history records is upto 100M records
Number of unique players in history upto 200K
Number of tables possible in the solution is upto 1K