Problem statement
Write a program to assign tables for first round of a rummy tournament.
- Each table will have 6 players
- Total no of tables: N {T1, T2, ........, TN)}
- Total no of players: 6N {P1, P2, ........, P6N}
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 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
Let’s use the example below:
There are 6 players A, B, C, D, E, F and they are plotted in graph using
their history games.
In this example:
Distance between A-B = 1
Distance between A-C = 1
Distance between A-D = 2
Distance between B-C = 1
Distance between B-D = 2
Distance between C-D = 1
Distance between E-F = 1
Distance between A-E = 3
Distance between A-F = 3
Distance between B-E = 3
Distance between B-F = 3
Distance between C-E = 3
Distance between C-F = 3
Distance between D-E = 3
Distance between D-F = 3
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
If we use the same figure above and we form a table of A, B, C, D, E, F then
Degree of separation of this table = 33
The condition on table formation is:
-
We have to create tables 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 for first round in a tournament is upto 1K
Use of open source:
-
You are free to use any open source that is not part of your algorithm.
-
You may use some open source that is part of your algorithm as long as
you can explain the functioning of that open source.
Evaluation criteria: Correct entries will be evaluated for:
-
Optimal algorithm
-
Quality and structure of code
Format of input:
History of past games:
This will be available in a MySQL DB table with this schema:
PlayerGameHistory{
PlayerId Integer
GameId Integer
}
List of players for the tournament:
This will be available in a MySQL DB table with this schema:
PlayerTournament{
TournamentId Integer
PlayerId Integer
}
Input to program will be provided via command line arguments in one line as:
$MySQL_IP_Address $MySQL_Port $SchemaName $Username $Password $TournamentId
Format of output:
Sum of (degree of separation of all the tables)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
