Problem Statement:
https://www.facebook.com/hackercup/problem/740733162607577/
Solution:
We just need to implement it correctly and simulate the algorithms as specified in the problem statement.
In the example solution below we prepare
Player class, for example:
class Player
{
public string Name;
public int ShotPct;
public int Height;
public int Team;
public int Draft;
public int PlayTime;
}
We then order the players by
shot_percentage, and then by
height. By using LINQ, we could do it easily:
allPlayers = allPlayers.OrderByDescending ( p => p.ShotPct ).ThenByDescending ( p => p.Height ).ToList ( );
We then assign the player into team 1 or 2 based on whether its draft number is odd or even.
We then provide four HashSets to separate the players into 4 groups:
- team1Playing
- team1Sitting
- team2Playing
- team2Sitting
We then run the game for M minutes and do player replacement every minute if needed.
When a player is replaced, we remove it from
teamXPlaying set and put it into
teamXSitting set.
We also remove the new player from
teamXSitting set and add it into
teamXPlaying set.
At the end of the game, we get the players currently playing in both
team1Playing and
team2Playing sets.
Example codes:
for ( int t = 0; t < T; t++ )
{
int N = inp.NextInt ( );
int M = inp.NextInt ( );
int P = inp.NextInt ( );
List<Player> allPlayers = new List<Player> ( );
for ( int i = 0; i < N; i++ )
{
Player p = new Player ( );
p.Name = inp.NextString ( );
p.ShotPct = inp.NextInt ( );
p.Height = inp.NextInt ( );
allPlayers.Add ( p );
}
allPlayers = allPlayers.OrderByDescending ( p => p.ShotPct ).ThenByDescending ( p => p.Height ).ToList ( );
for ( int i = 0; i < N; i++ )
{
allPlayers[i].Draft = i + 1;
if ( allPlayers[i].Draft % 2 == 1 )
allPlayers[i].Team = 1;
else
allPlayers[i].Team = 2;
}
HashSet<int> team1Playing = new HashSet<int> ( allPlayers.Where ( p => p.Team == 1 ).
OrderBy ( p => p.Draft ).Take ( P ).Select ( p => p.Draft ) );
HashSet<int> team2Playing = new HashSet<int> ( allPlayers.Where ( p => p.Team == 2 ).
OrderBy ( p => p.Draft ).Take ( P ).Select ( p => p.Draft ) );
HashSet<int> team1Sitting = new HashSet<int> ( allPlayers.Where ( p => p.Team == 1 ).
OrderBy ( p => p.Draft ).Skip ( P ).Select ( p => p.Draft ) );
HashSet<int> team2Sitting = new HashSet<int> ( allPlayers.Where ( p => p.Team == 2 ).
OrderBy ( p => p.Draft ).Skip ( P ).Select ( p => p.Draft ) );
for ( int i = 0; i < M; i++ )
{
//update playtime
foreach ( int draft in team1Playing )
{
Player p = allPlayers[draft - 1];
p.PlayTime++;
}
foreach ( int draft in team2Playing )
{
Player p = allPlayers[draft - 1];
p.PlayTime++;
}
if ( team1Playing.Count + team1Sitting.Count > P )
{
ReplacePlayer ( allPlayers, team1Playing, team1Sitting );
}
if ( team2Playing.Count + team2Sitting.Count > P )
{
ReplacePlayer ( allPlayers, team2Playing, team2Sitting );
}
}
List<string> names=new List<string>();
foreach ( int draft in team1Playing )
names.Add ( allPlayers[draft - 1].Name );
foreach ( int draft in team2Playing )
names.Add ( allPlayers[draft - 1].Name );
names.Sort ( );
string ans=string.Join ( " ", names.ToArray ( ) );
Console.WriteLine ( "Case #{0}: {1}", t + 1, ans );
}
private static void ReplacePlayer ( List<Player> allPlayers, HashSet<int> team1Playing, HashSet<int> team1Sitting )
{
//get who out
List<Player> p1 = new List<Player> ( );
foreach ( int draft in team1Playing )
p1.Add ( allPlayers[draft - 1] );
Player pout = p1.OrderByDescending ( p => p.PlayTime ).ThenByDescending ( p => p.Draft ).First ( );
//get who in
List<Player> p1s = new List<Player> ( );
foreach ( int draft in team1Sitting )
p1s.Add ( allPlayers[draft - 1] );
Player pin = p1s.OrderBy ( p => p.PlayTime ).ThenBy ( p => p.Draft ).First ( );
team1Playing.Remove ( pout.Draft );
team1Playing.Add ( pin.Draft );
team1Sitting.Remove ( pin.Draft );
team1Sitting.Add ( pout.Draft );
}
