LebGeeks
You are not logged in.
- Topics: Active • Unanswered
#1 January 28 2011
- xterm
- Moderator
Exercise - Team Balancing
Given
- 10 players (Name, Rating) where name is text and rating is a positive integer.
Your program should
- Split the players into two teams of 5 with the closest Average rating possible for each team
- Print out the teams and average rating of each team and its respective percentage (e.g.: 51% - 49%)
Here's a screenshot of a game called Heroes of Newerth where the teams are unbalanced.
Here's another one after it got balanced.
Have fun.
#2 January 28 2011
- Padre
- Member
Re: Exercise - Team Balancing
do you want team locks too ?
#3 January 28 2011
- xterm
- Moderator
Re: Exercise - Team Balancing
do you want team locks too ?
No need.
#4 January 28 2011
- arithma
- Member
Re: Exercise - Team Balancing
It should go for an absolute optimal solution with a greedy twist for ties.
C++0x, compiles on Visual Studio 2010, didn't test with gcc.
Sample output:
[ 2 2 3 4 6 7 ] [ 5 8 10 ]
difference = 1#include <iostream>
#include <set>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct node {
vector<int> left;
vector<int> right;
int sum_left;
int sum_right;
bool operator<(node const & n) const{
return lexicographical_compare(left.begin(), left.end(), n.left.begin(), n.left.end());
}
int diff() const {
return sum_left - sum_right;
}
list<node> neighbours(){
list<node> result;
for(unsigned i = 0; i < left.size(); i++){
if(sum_left - left[i] > sum_right + left[i]){
node cpy(*this);
cpy.left.erase(cpy.left.begin() + i);
cpy.right.insert(lower_bound(cpy.right.begin(), cpy.right.end(), left[i]), left[i]);
cpy.sum_left -= left[i];
cpy.sum_right += left[i];
result.push_back(cpy);
}
}
return result;
}
};
struct node_less_optimal {
bool operator()(node const & a, node const & b){
return a.diff() > b.diff();
}
};
int main(){
int arr[] = {2, 3, 6, 2, 4, 5, 10, 8, 7};
vector<int> v(arr, arr+sizeof(arr)/sizeof(arr[0]));
sort(v.begin(), v.end());
node start;
start.left = v;
int sum = 0; for_each(start.left.begin(), start.left.end(), [&sum](int x){ sum += x;});
start.sum_left = sum;
start.sum_right = 0;
set<node> close;
priority_queue<node, vector<node>, node_less_optimal> open;
open.push(start);
node c;
node optimum = start;
node_less_optimal comp;
while(open.size() > 0){
c = open.top();
if(c.diff() == 0){
optimum = c;
break;
}
close.insert(c);
if(comp(optimum, c))
optimum = c;
open.pop();
auto ns = c.neighbours();
for_each(ns.begin(), ns.end(), [&close, &open](node n){
if(close.find(n)==close.end())
open.push(n);
});
}
cout << "[ ";
for_each(optimum.left.begin(), optimum.left.end(), [](int x){cout << x << " ";});
cout << "] [ ";
for_each(optimum.right.begin(), optimum.right.end(), [](int x){cout << x << " ";});
cout << "]" << endl;
cout << "difference = " << optimum.diff() << endl;
return 0;
}
#5 January 28 2011
- Georges
- Member
Re: Exercise - Team Balancing
Here's the code. It's a simple algorithm that consists of generating 10 random values for ratings, sorting them, and then, splitting them into 2.
- First rating : 1st rating, 3rd, fifth, ..., 9th.
- Second Rating : 2nd, 4th, ..., 10th.
Edit: Written in C#, Visual Studio 2010.
ArrayList allTeams = new ArrayList();
Random rand = new Random();
int first = 0, second = 0, rating1 = 0, rating2 = 0;
for (int i = 0; i < 10; i++) // Generates random numbers between 25 and 75. (the larger the range, the lower the presicion)
allTeams.Add(rand.Next(25, 75));
allTeams.Sort();
for (int i = 0; i < allTeams.Count; i += 2)
{
first += (int)allTeams[i];
second += (int)allTeams[i + 1];
}
for (int i = 0; i < allTeams.Count; i++) // Displays generated numbers...
Console.Write(allTeams[i].ToString() + " ");
Console.Write("\n\n");
int x = allTeams.Count / 2;
rating1 = first / x;
rating2 = second / x;
int middle = rating2 + rating1; // Gets the middle value of the 2 ratings to calculate %
rating2 = rating2 * 100 / middle; // Gets the % of each value...
rating1 = 100 - rating2;
Console.Write("Rating 1: {0}\nRating 2: {1}", rating1, rating2);
Console.ReadKey();This is a primitive algorithm... Will think of a better implementation later...
Last edited by Georges (January 29 2011)
#6 January 29 2011
- MSD
- Member
Re: Exercise - Team Balancing
This is the simplest yet most specific solution I could come up with, will see if I can generalize it more C#
[Edit]Edited to make less bulky and more organized[/Edit]
[Edit]This code now can be switched to more dimensions, I tried 14 players split into 7 player teams and it worked nicely[/Edit]:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace SplitTeams
{
class Program
{
class Player
{
public string Name { get; set; }
public int Rating { get; set; }
}
const int PLAYER_COUNT = 10;
static void Split(Player[] original, Player[] team1, Player[] team2)
{
int[, , , ,] matrix = new int[PLAYER_COUNT, PLAYER_COUNT, PLAYER_COUNT, PLAYER_COUNT, PLAYER_COUNT];
int length = PLAYER_COUNT;
int[] matches = new int[PLAYER_COUNT / 2];
for (int i = 0; i < matches.Length; i++)
matches[i] = i;
float midPoint = ((float)original.Sum(x => x.Rating)) / 2;
for (int i = 0; i < length; i++)
{
for (int j = i + 1; j < length; j++)
for (int k = j + 1; k < length; k++)
for (int l = k + 1; l < length; l++)
for (int m = l + 1; m < length; m++)
{
if(m != l && m != l && m != k && m != j && l != k && l != j && l != i && k != j && k != i && j != i)//avoid duplicate
{
matrix[i, j, k, l, m] = original[i].Rating + original[j].Rating + original[k].Rating + original[l].Rating + original[m].Rating;
if (Math.Abs(matrix[matches[0], matches[1], matches[2], matches[3], matches[4]] - midPoint) > Math.Abs(matrix[i, j, k, l, m] - midPoint))
{
matches[0] = i;
matches[1] = j;
matches[2] = k;
matches[3] = l;
matches[4] = m;
}
}
}
}
int team1Counter = 0, team2Counter = 0;
for (int i = 0; i < original.Length; i++)
{
if (matches.Contains(i))
team1[team1Counter++] = original[i];
else
team2[team2Counter++] = original[i];
}
}
static void Main(string[] args)
{
Player[] players = new Player[]
{
new Player{Name="A", Rating=1567},
new Player{Name="B", Rating=1696},
new Player{Name="C", Rating=1697},
new Player{Name="D", Rating=1653},
new Player{Name="E", Rating=1813},
new Player{Name="F", Rating=1664},
new Player{Name="G", Rating=1664},
new Player{Name="H", Rating=1620},
new Player{Name="I", Rating=1665},
new Player{Name="J", Rating=1747},
};
Player[] team1 = new Player[PLAYER_COUNT / 2];
Player[] team2 = new Player[PLAYER_COUNT / 2];
Split(players, team1, team2);
float sum1 = team1.Sum(x => x.Rating);
float sum2 = team2.Sum(x => x.Rating);
float perc1 = (sum1 * 100) / (sum1 + sum2);
float perc2 = (sum2 * 100) / (sum1 + sum2);
Console.WriteLine(string.Format("Team 1: ({0:f2}%)", perc1));
foreach (Player p in team1)
Console.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
Console.WriteLine(string.Format("Team 2: ({0:f2}%)", perc2));
foreach (Player p in team2)
Console.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
Console.Read();
}
}
}Last edited by MSD (January 29 2011)
#7 January 29 2011
- arithma
- Member
Re: Exercise - Team Balancing
Apparently I solved another problem: specifically, splitting a team into two teams that have the closest summed up rank regardless of the count of players. I am still thinking of an optimal solution for the half/half split without having to use those open/close graph athletics, though I am skeptical of my efforts.
@MSD: Can you please explain your technique. The five dimensional matrix is interesting. (You will need at least 36GB to solve a problem that has 100 members).
#8 January 29 2011
- Ayman
- Member
Re: Exercise - Team Balancing
Nice exercise, will give it a shot if I have time tonight, btw xterm, is there a scale for the player rating? I mean is the rating out 5, 10, 100 for each player just like the team rating is out of 100? Thanks :)
#9 January 29 2011
- Georges
- Member
Re: Exercise - Team Balancing
Just out of curiosity, how to know which algorithm is the best and there's no better solution for a set of ratings...
I suggest using 10 predefined ratings, ranging between 25 and 75. and test each algorithm on these ratings.
#10 January 29 2011
- MSD
- Member
Re: Exercise - Team Balancing
@arithma: as I mentioned that was an an initial solution for the specific 10 player scenario. On the other hand here is another general solution that does not use any arrays:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace SplitTeams
{
class Program
{
class Player
{
public string Name { get; set; }
public int Rating { get; set; }
}
class Match : List<int>
{
public int Sum { get; set; }
public Match() { }
public Match(Match from)
: base(from)
{
this.Sum = from.Sum;
}
}
private static int _TotalPlayers;
private static Random rnd = new Random(DateTime.Now.Millisecond);
private static float _Half;
private static Player[] _Players;
private static bool _Finished = false;
private static void loop(ref Match bestMatch, Match current, int depth, int start)
{
if (depth == (_TotalPlayers / 2) - 1)
{
current.Sum = 0;
for (int i = 0; i < current.Count; i++)
current.Sum += _Players[current[i]].Rating;
if (Math.Abs(bestMatch.Sum - _Half) > Math.Abs(current.Sum - _Half))
{
bestMatch = new Match(current);
_Finished = bestMatch.Sum == _Half;
}
}
else
{
//using a copy so we don't modify current and it retains same values as when it was passed as parameter
Match copy = new Match(current);
for (copy[depth] = depth >= 1 ? copy[depth - 1] + 1 : 0; !_Finished && copy[depth] < _TotalPlayers; copy[depth]++)
{
bool duplicate = false;
int val = copy[depth];
for (int i = 0; i < copy.Count && !(duplicate = (i != depth && copy[i] == val)); i++) ;
if (!duplicate)
loop(ref bestMatch, copy, depth + 1, start + 1);
}
}
}
private static void Split(Player[] team1, Player[] team2)
{
Match current = new Match(), match = new Match();
//initialize
for (int i = 0; i < _TotalPlayers / 2; i++)
{
match.Add(i);
current.Add(i);
}
_Half = ((float)_Players.Sum(x => x.Rating)) / 2;
_Players = Fold(_Players);
loop(ref match, current, 0, 0);
int team1Counter = 0, team2Counter = 0;
for (int i = 0; i < _Players.Length; i++)
{
if (match.Contains(i))
team1[team1Counter++] = _Players[i];
else
team2[team2Counter++] = _Players[i];
}
}
private static Player[] Fold(Player[] players)
{
players = players.OrderBy(x => x.Rating).ToArray();
int foldedIndex = 0;
bool rightLeft = false;
Player[] folded = new Player[players.Length];
for (int i = 0; i < players.Length/2; i+=(rightLeft ? 1 : 0), rightLeft = !rightLeft)
{
folded[foldedIndex++] = rightLeft ? players[i] : players[players.Length - i - 1];
}
return folded;
}
private static Player[] GeneratePlayers()
{
Player[] result = new Player[_TotalPlayers];
for (int i = 0; i < result.Length; i++)
result[i] = new Player { Name = "Player" + i.ToString(), Rating = rnd.Next(2000) };
return result;
}
static void Main(string[] args)
{
_TotalPlayers = 10;
if (args.Length > 0)
int.TryParse(args[0], out _TotalPlayers);
if (_TotalPlayers % 2 != 0)
throw new Exception("Invalid PLAYER_COUNT, must be even.");
DateTime start = DateTime.Now;
_Players = GeneratePlayers();
DateTime end = DateTime.Now;
TimeSpan diff = end.Subtract(start);
Console.WriteLine(string.Format("Generated {0} players in {1} milliseconds", _TotalPlayers, diff.TotalMilliseconds));
Player[] team1 = new Player[_TotalPlayers / 2];
Player[] team2 = new Player[_TotalPlayers / 2];
start = DateTime.Now;
Split(team1, team2);
end = DateTime.Now;
diff = end.Subtract(start);
Console.WriteLine(string.Format("Split {0} players into 2 {1} player teams in {2} milliseconds.", _TotalPlayers, _TotalPlayers / 2, diff.TotalMilliseconds));
float sum1 = team1.Sum(x => x.Rating);
float sum2 = team2.Sum(x => x.Rating);
float perc1 = (sum1 * 100) / (sum1 + sum2);
float perc2 = (sum2 * 100) / (sum1 + sum2);
Console.WriteLine(string.Format("Team 1: ({0:f2}%)", perc1));
foreach (Player p in team1)
Console.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
Console.WriteLine(string.Format("Team 2: ({0:f2}%)", perc2));
foreach (Player p in team2)
Console.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
Console.Read();
}
}
}About this solution:
* I used a recursive technique to simulate the nested loops while keeping that number of loops dynamic (using a depth parameter)
* I am trying to find the closest sum to half the sum of all player ratings, if I find an exact match I quit, this means that only one solution is considered
* I am using a Fold method that will rearrange the players according to their ratings. The rearrangement can be visualized as a sorted list being folded in half, thus the min and max are next to each other, then the first number greater than min is adjacent to the first number less than max and so on... The benefit of using this method is not certain to me yet, just a shot in the dark...
* I was not able to bench mark this and get consistent times since sometimes a 50 player scenario would be solved in less than a second and in other times it takes about 2 minutes. Feel free to benchmark it and post some results if you want .
Last edited by MSD (January 29 2011)
#11 January 29 2011
- arithma
- Member
Re: Exercise - Team Balancing
Some theory to start with
Let's assume that we have an even number of players, say 50. The number of ways we can take from these 50 players into the first team is given by:
combinations_players(50) = 50! / 25! / 25! = 126,410,606,437,752
Compare to: combinations_players(20) = 20! / 10! / 10! = 184,756
Since there's apparently no greedy solution to the problem (not proved, not to discourage), the problem disintegrates into a problem of generating all combinations, checking each of them for their sum property, and taking out the minimum.
@George: I think I am starting to build a hunch for this elusive problem. It's not easy to benchmark it since some cases return almost immediately (when there's an exact match for a half) or almost never return when using large inputs.
So for, my first trial with reorienting the first piece of code to work with missed constraints has failed. Teams of fifty are crashing the app without any return. I have one solution that uses almost no memory, but I am more inclined to generic graph solutions.
I was hoping I could find a greedy algorithm to fit, but apparently I can't connect all the dots correctly. I am stuck with a failing solution for the time being. None the less, it handles odd counts of people, and returns partitions that are one item in length apart.
Here's what I got so far (for an input of 20 scores, it has to close 388593 of some kind of steps. Not cool.
closed nodes 388593
[ 27 34 36 42 45 58 62 64 67 69 ] [ 0 5 24 27 41 61 78 81 91 95 ]
difference = 1The number of closed nodes (which includes the incomplete partial nodes in my solution (such as a left containing 12 and right containing 8)) resembles the number of combinations. So effectively, I am not doing anything special yet with this solution.
C++0x, VS2010
#include <iostream>
#include <set>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct node {
vector<int> left;
vector<int> right;
int sum_left;
int sum_right;
bool operator<(node const & n) const{
return lexicographical_compare(left.begin(), left.end(), n.left.begin(), n.left.end());
}
int diff() const {
return sum_left - sum_right;
}
list<node> neighbours(){
list<node> result;
for(unsigned i = 0; i < left.size(); i++){
if((left.size() >= right.size()) && (sum_left - left[i] > sum_right + left[i])){
node cpy(*this);
cpy.left.erase(cpy.left.begin() + i);
cpy.right.insert(lower_bound(cpy.right.begin(), cpy.right.end(), left[i]), left[i]);
cpy.sum_left -= left[i];
cpy.sum_right += left[i];
result.push_back(cpy);
}
}
return result;
}
};
struct node_less_optimal {
bool operator()(node const & a, node const & b){
return a.diff() > b.diff();
}
};
int main(){
//int arr[] = {2, 3, 6, 2, 4, 5, 10, 8, 7};
vector<int> v; //(arr, arr+sizeof(arr)/sizeof(arr[0]));
for(int i = 0; i < 20; i++){
v.push_back(rand()%100);
}
sort(v.begin(), v.end());
node start;
start.left = v;
int sum = 0; for_each(start.left.begin(), start.left.end(), [&sum](int x){ sum += x;});
start.sum_left = sum;
start.sum_right = 0;
set<node> close;
priority_queue<node, vector<node>, node_less_optimal> open;
open.push(start);
node c;
node optimum = start;
node_less_optimal comp;
while(open.size() > 0){
c = open.top();
if((c.left.size() <= c.right.size() + 1) && c.diff() == 0){
optimum = c;
break;
}
close.insert(c);
if((c.left.size() <= c.right.size() + 1) && comp(optimum, c))
optimum = c;
open.pop();
auto ns = c.neighbours();
for_each(ns.begin(), ns.end(), [&close, &open](node n){
if(close.find(n)==close.end())
open.push(n);
});
}
cout << "closed nodes " << close.size() << endl;
cout << "[ ";
for_each(optimum.left.begin(), optimum.left.end(), [](int x){cout << x << " ";});
cout << "] [ ";
for_each(optimum.right.begin(), optimum.right.end(), [](int x){cout << x << " ";});
cout << "]" << endl;
cout << "difference = " << optimum.diff() << endl;
return 0;
}Last edited by arithma (January 29 2011)
#12 January 30 2011
- MSD
- Member
Re: Exercise - Team Balancing
Benchmarking my solution, as I said, sometimes getting fast solutions for a 50 player case, while others like this last time it took 5872628.9062 milliseconds to solve (about 98 minutes).
Generated 60 players in 0.9766 milliseconds
Split 60 players into 2 30 player teams in 5872628.9062 milliseconds.
Team 1: (50.00%)
Name: Player17, Rating: 1910
Name: Player57, Rating: 29
Name: Player55, Rating: 1898
Name: Player10, Rating: 44
Name: Player3, Rating: 1875
Name: Player0, Rating: 53
Name: Player37, Rating: 1815
Name: Player40, Rating: 62
Name: Player34, Rating: 1790
Name: Player56, Rating: 82
Name: Player6, Rating: 1786
Name: Player46, Rating: 139
Name: Player39, Rating: 1780
Name: Player36, Rating: 149
Name: Player49, Rating: 1774
Name: Player21, Rating: 155
Name: Player45, Rating: 1743
Name: Player50, Rating: 296
Name: Player51, Rating: 1718
Name: Player8, Rating: 306
Name: Player43, Rating: 1673
Name: Player16, Rating: 486
Name: Player1, Rating: 1671
Name: Player5, Rating: 489
Name: Player25, Rating: 1661
Name: Player38, Rating: 551
Name: Player54, Rating: 1616
Name: Player26, Rating: 1600
Name: Player22, Rating: 1588
Name: Player59, Rating: 1122
Team 2: (50.00%)
Name: Player18, Rating: 494
Name: Player41, Rating: 1659
Name: Player15, Rating: 505
Name: Player48, Rating: 1626
Name: Player35, Rating: 553
Name: Player23, Rating: 589
Name: Player42, Rating: 606
Name: Player29, Rating: 1583
Name: Player53, Rating: 608
Name: Player19, Rating: 1544
Name: Player2, Rating: 618
Name: Player52, Rating: 1543
Name: Player47, Rating: 731
Name: Player11, Rating: 1497
Name: Player24, Rating: 768
Name: Player31, Rating: 1461
Name: Player4, Rating: 784
Name: Player9, Rating: 1322
Name: Player33, Rating: 885
Name: Player13, Rating: 1288
Name: Player44, Rating: 973
Name: Player27, Rating: 1249
Name: Player12, Rating: 1009
Name: Player32, Rating: 1240
Name: Player20, Rating: 1046
Name: Player30, Rating: 1198
Name: Player7, Rating: 1079
Name: Player14, Rating: 1161
Name: Player58, Rating: 1107
Name: Player28, Rating: 1134[Edit]This last one was (obviously) a 60 player scenario[/Edit]
Last edited by MSD (January 30 2011)
#13 January 30 2011
- arithma
- Member
Re: Exercise - Team Balancing
This is the thing I've been rambling about a little while ago. Just a combination generator. Nothing to be proud of.
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
struct Solver{
int sum;
int sum_half;
vector<int> v;
vector<int> opt;
int opt_sum;
Solver(vector<int> const & _v) : v(_v), sum(0), sum_half(0){
sort(v.begin(), v.end());
opt.insert(opt.begin(), v.begin(), v.begin()+v.size()/2);
int _opt_sum = 0;
for_each(opt.begin(), opt.end(), [&_opt_sum](int x){ _opt_sum += x;});
opt_sum = _opt_sum;
int _sum = 0;
for_each(v.begin(), v.end(), [&_sum](int x){ _sum += x;});
sum = _sum;
sum_half = sum/2;
solve();
}
void solve(int offset = 0, vector<int> comb = vector<int>(), int comb_sum = 0){
if(comb.size() == v.size()/2){
if(sum_half - comb_sum < sum_half - opt_sum){
opt = comb;
opt_sum = comb_sum;
}
}
else
{
int remain = v.size()/2 - comb.size();
for(int i = offset; i <= v.size() - remain; i++){
vector<int> cpy(comb);
cpy.push_back(v[i]);
int cpy_sum = comb_sum + v[i];
if(cpy_sum<sum_half)
solve(i+1, cpy, cpy_sum);
}
}
}
};
int main(){
vector<int> v;
for(int i = 0; i < 30; i++){
v.push_back(i);//rand()%100);
}
Solver s(v);
for_each(s.v.begin(), s.v.end(), [](int x){ cout << x << " ";});
cout << endl;
for_each(s.opt.begin(), s.opt.end(), [](int x){ cout << x << " ";});
cout << endl;
}
#14 January 30 2011
- arithma
- Member
Re: Exercise - Team Balancing
@MSD: This 98minutes could be just a lucky guess with the algorithm. I do not think our combination technique could really hold against the huge combinatorial explosion we're dealing with.
So here's a challenge now:
Balance teams from a pool of ranks growing from 0 to 999 inclusive.
I got the difference down to 2. PS: No, I have not asked google for an answer yet. Computation time [wrong]~10 seconds[/wrong][correct]instantaneous[/correct].
I can not pledge that it is optimal however.
-Note, again: This solution is definitely not optimal since if you split the array in half, and take every other element from each array, and then join them, they'll return a difference of zero (always for any sequential array). This means we need another method to evaluate heuristic algorithms. Am satisfied enough with this algo, though I wish I could find some academic material for such a problem.
diff = 2
on the left
6 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27 28 29 30 32 33 34 35 36 37 38 39 40 42 43 45 47 50 57 58 60 65 67 69 70 74 75 77 78 79 81 86 87 89 90 93 97 102 105 106 107 108 110 111 112 116 119 123 125 126 127 130 133 135 136 137 139 140 141 142 143 145 147 148 149 152 154 158 161 162 164 165 167 169 170 171 173 175 176 177 180 182 183 184 188 189 192 194 195 196 200 201 203 204 205 206 207 209 210 211 214 216 217 218 219 221 226 228 229 231 234 239 242 243 247 248 251 252 253 254 255 262 263 265 266 267 268 270 271 273 277 279 280 282 284 290 293 295 298 300 303 304 312 314 315 316 317 318 320 322 325 326 335 336 339 341 343 345 346 348 349 351 352 353 354 357 358 359 360 363 366 367 368 374 376 377 379 380 381 383 384 385 390 391 396 397 403 405 406 408 411 413 415 417 420 422 425 426 427 429 433 434 438 440 442 445 447 448 449 451 459 460 461 465 467 468 469 472 473 475 479 484 485 487 491 492 493 495 497 500 501 503 506 512 514 515 518 519 523 529 535 536 537 538 539 540 544 549 551 552 553 554 555 556 557 559 562 565 568 570 571 576 577 578 579 582 586 592 593 594 595 601 602 603 605 609 610 614 617 618 622 623 624 626 629 630 632 633 634 635 638 642 643 644 646 647 649 651 656 657 659 661 663 664 666 668 671 675 677 678 679 682 683 685 686 687 692 693 694 699 700 704 705 706 707 708 710 712 713 714 715 716 717 718 719 721 722 723 724 725 726 728 729 730 731 732 734 735 736 737 739 742 744 745 746 748 750 753 754 756 759 760 761 762 763 767 769 771 772 774 775 776 777 778 781 782 784 788 790 792 793 794 795 796 797 800 807 810 813 814 816 817 818 820 821 823 824 825 831 833 834 835 836 837 838 839 840 842 844 845 847 849 854 855 856 858 859 861 862 863 865 866 870 871 872 874 880 881 888 892 893 896 897 900 902 905 906 907 908 909 910 912 913 915 920 921 925 927 931 934 935 938 941 944 945 946 949 951 953 954 956 959 961 966 971 972 974 976 977 978 979 980 981 984 986 988 989 992 993 994 997 998 999
-----------
on the right
0 1 2 3 4 5 7 9 16 25 31 41 44 46 48 49 51 52 53 54 55 56 59 61 62 63 64 66 68 71 72 73 76 80 82 83 84 85 88 91 92 94 95 96 98 99 100 101 103 104 109 113 114 115 117 118 120 121 122 124 128 129 131 132 134 138 144 146 150 151 153 155 156 157 159 160 163 166 168 172 174 178 179 181 185 186 187 190 191 193 197 198 199 202 208 212 213 215 220 222 223 224 225 227 230 232 233 235 236 237 238 240 241 244 245 246 249 250 256 257 258 259 260 261 264 269 272 274 275 276 278 281 283 285 286 287 288 289 291 292 294 296 297 299 301 302 305 306 307 308 309 310 311 313 319 321 323 324 327 328 329 330 331 332 333 334 337 338 340 342 344 347 350 355 356 361 362 364 365 369 370 371 372 373 375 378 382 386 387 388 389 392 393 394 395 398 399 400 401 402 404 407 409 410 412 414 416 418 419 421 423 424 428 430 431 432 435 436 437 439 441 443 444 446 450 452 453 454 455 456 457 458 462 463 464 466 470 471 474 476 477 478 480 481 482 483 486 488 489 490 494 496 498 499 502 504 505 507 508 509 510 511 513 516 517 520 521 522 524 525 526 527 528 530 531 532 533 534 541 542 543 545 546 547 548 550 558 560 561 563 564 566 567 569 572 573 574 575 580 581 583 584 585 587 588 589 590 591 596 597 598 599 600 604 606 607 608 611 612 613 615 616 619 620 621 625 627 628 631 636 637 639 640 641 645 648 650 652 653 654 655 658 660 662 665 667 669 670 672 673 674 676 680 681 684 688 689 690 691 695 696 697 698 701 702 703 709 711 720 727 733 738 740 741 743 747 749 751 752 755 757 758 764 765 766 768 770 773 779 780 783 785 786 787 789 791 798 799 801 802 803 804 805 806 808 809 811 812 815 819 822 826 827 828 829 830 832 841 843 846 848 850 851 852 853 857 860 864 867 868 869 873 875 876 877 878 879 882 883 884 885 886 887 889 890 891 894 895 898 899 901 903 904 911 914 916 917 918 919 922 923 924 926 928 929 930 932 933 936 937 939 940 942 943 947 948 950 952 955 957 958 960 962 963 964 965 967 968 969 970 973 975 982 983 985 987 990 991 995 996Last edited by arithma (January 30 2011)
#15 January 30 2011
- MSD
- Member
Re: Exercise - Team Balancing
Here is my final solution, and I think this is the one, it works on big numbers of players in a very fast time, I really enjoyed this one ;)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.IO;
namespace SplitTeams
{
class Program
{
class Player
{
public string Name { get; set; }
public int Rating { get; set; }
}
private static int _TotalPlayers;
private static Random rnd = new Random(DateTime.Now.Millisecond);
private static Player[] _Players;
private static bool FindSwappables(Player[] team1, Player[] team2, int diff, out int player1, out int player2)
{
player1 = 0;
player2 = 0;
int? maxDiff = null;
double halfDiff = Math.Abs(Math.Ceiling((float)diff / 2));
for (int i = 0; i < team1.Length; i++)
{
for (int j = 0; j < team2.Length; j++)
{
int currentDiff = team1[i].Rating - team2[j].Rating;
if (currentDiff > 0 && diff > 0 || currentDiff < 0 && diff < 0)//elligible swap (same sign)
{
currentDiff = Math.Abs(currentDiff);
if (currentDiff <= halfDiff && (!maxDiff.HasValue || currentDiff > maxDiff))
{
maxDiff = currentDiff;
player1 = i;
player2 = j;
}
}
}
}
return maxDiff != null;
}
private static void Cut(Player[] team1, Player[] team2)
{
for (int i = 0; i < _Players.Length / 2; i++)
team1[i] = _Players[i];
for (int i = _Players.Length / 2, counter = 0; i < _Players.Length; i++, counter++)
team2[counter] = _Players[i];
}
private static void Swap(Player[] team1, Player[] team2, int team1Index, int team2Index, ref int sum1, ref int sum2)
{
Player temp = team1[team1Index];
team1[team1Index] = team2[team2Index];
team2[team2Index] = temp;
sum1 += team1[team1Index].Rating - team2[team2Index].Rating;
sum2 += team2[team2Index].Rating - team1[team1Index].Rating;
}
private static void Split(Player[] team1, Player[] team2)
{
Cut(team1, team2);
int s1, s2, sum1, sum2;
sum1 = team1.Sum(x => x.Rating);
sum2 = team2.Sum(x => x.Rating);
int diff = sum1 - sum2;
while (diff != 0 && FindSwappables(team1, team2, diff, out s1, out s2))
{
Swap(team1, team2, s1, s2, ref sum1, ref sum2);
diff = sum1 - sum2;
}
}
#region Util
private static void GeneratePlayers()
{
DateTime start = DateTime.Now;
_Players = new Player[_TotalPlayers];
for (int i = 0; i < _Players.Length; i++)
_Players[i] = new Player { Name = "Player" + i.ToString(), Rating = rnd.Next(2000) };
DateTime end = DateTime.Now;
TimeSpan diff = end.Subtract(start);
Console.WriteLine(string.Format("Generated {0} players in {1} milliseconds", _TotalPlayers, diff.TotalMilliseconds));
}
private static void SplitAndReporttoConsole()
{
Player[] team1 = new Player[_TotalPlayers / 2];
Player[] team2 = new Player[_TotalPlayers / 2];
DateTime start = DateTime.Now;
Split(team1, team2);
DateTime end = DateTime.Now;
TimeSpan diff = end.Subtract(start);
Console.WriteLine(string.Format("Split {0} players into 2 {1} player teams in {2} milliseconds.", _TotalPlayers, _TotalPlayers / 2, diff.TotalMilliseconds));
float sum1 = team1.Sum(x => x.Rating);
float sum2 = team2.Sum(x => x.Rating);
float perc1 = (sum1 * 100) / (sum1 + sum2);
float perc2 = (sum2 * 100) / (sum1 + sum2);
Console.WriteLine(string.Format("Team 1: ({0:f2}%)", perc1));
foreach (Player p in team1)
Console.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
Console.WriteLine(string.Format("Team 2: ({0:f2}%)", perc2));
foreach (Player p in team2)
Console.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
}
private static void SplitAndReportToFile()
{
FileInfo fi = new FileInfo("C:\\output.txt");
FileStream fs = null;
if (!fi.Exists)
fs = new FileStream("C:\\output.txt", FileMode.Create);
else
fs = File.Open("C:\\output.txt", FileMode.Truncate);
StreamWriter sw = new StreamWriter(fs);
Player[] team1 = new Player[_TotalPlayers / 2];
Player[] team2 = new Player[_TotalPlayers / 2];
DateTime start = DateTime.Now;
Split(team1, team2);
DateTime end = DateTime.Now;
TimeSpan diff = end.Subtract(start);
Console.WriteLine(string.Format("Split {0} players into 2 {1} player teams in {2} milliseconds.", _TotalPlayers, _TotalPlayers / 2, diff.TotalMilliseconds));
float sum1 = team1.Sum(x => x.Rating);
float sum2 = team2.Sum(x => x.Rating);
float perc1 = (sum1 * 100) / (sum1 + sum2);
float perc2 = (sum2 * 100) / (sum1 + sum2);
sw.WriteLine(string.Format("Team 1: ({0:f2}%)", perc1));
foreach (Player p in team1)
sw.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
sw.WriteLine(string.Format("Team 2: ({0:f2}%)", perc2));
foreach (Player p in team2)
sw.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
sw.Close();
fs.Close();
}
private static void InsureTotalPlayers(string[] args)
{
if (args.Length > 0)
int.TryParse(args[0], out _TotalPlayers);
if (_TotalPlayers % 2 != 0)
throw new Exception("Invalid PLAYER_COUNT, must be even.");
}
#endregion
static void Main(string[] args)
{
/* _Players = new Player[]
{
new Player{Name="A", Rating=500},
new Player{Name="A", Rating=1},
new Player{Name="A", Rating=233},
new Player{Name="A", Rating=10},
new Player{Name="A", Rating=71},
new Player{Name="A", Rating=112},
new Player{Name="A", Rating=9},
new Player{Name="A", Rating=46}
};*/
_TotalPlayers = 1000;
_Players = new Player[_TotalPlayers];
for (int i = 0; i < _TotalPlayers; i++)
_Players[i] = new Player { Name = i.ToString(), Rating = i };
InsureTotalPlayers(args);
GeneratePlayers();
SplitAndReportToFile();
Console.Write("Press any key to exit.");
Console.Read();
}
}
}You can generate players randomly or have them preset like in the above code ( I used arithma's suggestion and got a clear cut split 50/50).
Generated 1000 players in 0 milliseconds
Split 1000 players into 2 500 player teams in 41.9922 milliseconds.[Edit]Modified to avoid overflow (need to test for more extreme cases).[/Edit]
Last edited by MSD (January 30 2011)
#16 January 30 2011
- arithma
- Member
Re: Exercise - Team Balancing
And here's mine.
I just tried it with 10,000 random values (between 0 and 0x7fff), it returns on the spot.
@MSD: I just tried your code with 10,000, but I think there's an overflow with currentDiff * diff > 0. I replaced it with
if((currentDiff > 0) == (diff > 0))Still the algorithm doesn't return. I would really appreciate it if you'd look at it for a bit, as I am comparing something in the algo's, and seeing if a particular thing I did spared me quadratic growth or not.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Solver{
vector<int> left;
vector<int> right;
int lsum;
int rsum;
Solver(vector<int> & v){
left.insert(left.begin(), v.begin(), v.begin() + v.size()/2);
right.insert(right.begin(), v.begin() + v.size()/2, v.end());
sort(left.begin(), left.end());
sort(right.begin(), right.end());
lsum = 0;
rsum = 0;
for(int i = 0; i < left.size(); i++)
lsum += left[i];
for(int i = 0; i < right.size(); i++)
rsum += right[i];
if(lsum > rsum){
swap(left, right);
swap(lsum, rsum);
}
while(step());
}
bool step(){
int diff = rsum - lsum;
for(auto curr = right.rbegin(); curr != right.rend(); curr++){
auto found = lower_bound(left.begin(), left.end(), *curr - diff/2);
if(found != left.end() && (diff + 2 * *found - 2 * *curr > 0) && (*found - *curr < 0)){
lsum += + *curr - *found;
rsum += - *curr + *found;
diff = rsum - lsum;
swap(*found, *curr);
sort(left.begin(), left.end());
sort(right.begin(), right.end());
return true;
}
}
return false;
}
};
int main(){
vector<int> v;
int const K = 10000;
for(int i = 0; i < K; i++){
v.push_back(rand());
}
vector<int> shuffled(K);
for(int i = 0; i < K; i++){
int index = rand()%v.size();
shuffled[i] = v[index];
v.erase(v.begin()+index);
}
Solver s(shuffled);
cout << "diff = " << s.rsum - s.lsum << endl;
cout << "on the left\n";
for_each(s.left.begin(), s.left.end(), [](int x){ cout << x << " ";});
cout << endl;
cout << "-----------\n";
cout << "on the right\n";
for_each(s.right.begin(), s.right.end(), [](int x){ cout << x << " ";});
cout << endl;
return 0;
}
#17 January 30 2011
- MSD
- Member
Re: Exercise - Team Balancing
And here's mine.
@MSD: I just tried your code with 10,000, but I think there's an overflow with currentDiff * diff > 0.
@arithma: please check if it solves your problem now
#18 January 30 2011
- the_pessimist
- Member
Re: Exercise - Team Balancing
- Sort the 10 players according to their rating: p1 p2 p3 ... p10:
Team1 = p1 p10, p3 p8, p5
Team2 = p2 p9, p4 p7, p6
Observe how I chose the indices of each team.
#19 January 30 2011
- MSD
- Member
Re: Exercise - Team Balancing
- Sort the 10 players according to their rating: p1 p2 p3 ... p10:
Team1 = p1 p10, p3 p8, p5
Team2 = p2 p9, p4 p7, p6Observe how I chose the indices of each team.
I that a solution or a question?
#20 January 30 2011
- arithma
- Member
Re: Exercise - Team Balancing
I put the code neck to neck on my machine, compiled both in Release mode, both taking in arrays ranging from 1 to 10,000.
My program solves it with the following output:
shuffled
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
2499975000 - 2499975000 = 0It does so in less than a minute.
It also got rid of those annoying "2" differences from the output.
Both programs have been changed to use 64-bit integers.
I am sorry MSD, but your program has yet to return
To change MSD's code, just replace int with long to handle those pesky large 100,000 values.
64-bit, arithma's code.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Solver{
vector<_int64> left;
vector<_int64> right;
_int64 lsum;
_int64 rsum;
Solver(vector<_int64> & v){
left.insert(left.begin(), v.begin(), v.begin() + v.size()/2);
right.insert(right.begin(), v.begin() + v.size()/2, v.end());
sort(left.begin(), left.end());
sort(right.begin(), right.end());
lsum = 0;
rsum = 0;
for(_int64 i = 0; i < left.size(); i++)
lsum += left[i];
for(_int64 i = 0; i < right.size(); i++)
rsum += right[i];
if(lsum > rsum){
swap(left, right);
swap(lsum, rsum);
}
int steps = 0;
while(step()){
steps++;
if(steps%1000==0)
cout << "1000 steps done" << endl;
}
cout << rsum << " - " << lsum << " = " << rsum - lsum << endl;
}
bool step(){
_int64 diff = rsum - lsum;
for(auto curr = right.rbegin(); curr != right.rend(); curr++){
auto found = lower_bound(left.begin(), left.end(), *curr - diff/2);
//if(found != left.end() && (diff + 2 * *found - 2 * *curr < diff) && (*found - *curr < 0)){
if(found != left.end() && (abs(diff + 2 * *found - 2 * *curr) < diff)){
lsum += + *curr - *found;
rsum += - *curr + *found;
diff = rsum - lsum;
swap(*found, *curr);
sort(left.begin(), left.end());
sort(right.begin(), right.end());
if(lsum > rsum){
swap(left, right);
swap(lsum, rsum);
}
return true;
}
}
return false;
}
void randomswaps(_int64 n){
for(_int64 i = 0; i < n; i++){
_int64 l = rand()%left.size();
_int64 r = rand()%right.size();
lsum += right[r] - left[l];
rsum += left[l] - right[r];
swap(left[l], right[r]);
}
if(lsum > rsum){
swap(left, right);
swap(lsum, rsum);
}
}
};
int main(){
vector<_int64> v;
_int64 const K = 100000;
for(_int64 i = 0; i < K; i++){
v.push_back(i);//rand());
}
vector<_int64> shuffled(K);
for(_int64 i = 0; i < K; i++){
_int64 index = rand()%v.size();
shuffled[i] = v[index];
v.erase(v.begin()+index);
}
cout << "shuffled" << endl;
Solver s(shuffled);
return 0;
cout << "diff = " << s.rsum - s.lsum << endl;
cout << "on the left\n";
for_each(s.left.begin(), s.left.end(), [](_int64 x){ cout << x << " ";});
cout << endl;
cout << "-----------\n";
cout << "on the right\n";
for_each(s.right.begin(), s.right.end(), [](_int64 x){ cout << x << " ";});
cout << endl;
return 0;
}Last edited by arithma (January 30 2011)
#21 January 30 2011
- MSD
- Member
Re: Exercise - Team Balancing
@arithma: OK, I'll take that and I will raise you. Added the Fold method again (since a sequence is a worst case scenario) which I think (did not check your code thoroughly) is equivalent to your shuffle, and voiala:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.IO;
namespace SplitTeams
{
class Program
{
class Player
{
public string Name { get; set; }
public int Rating { get; set; }
}
private static int _TotalPlayers;
private static Random rnd = new Random(DateTime.Now.Millisecond);
private static Player[] _Players;
private static bool FindSwappables(Player[] team1, Player[] team2, int diff, out int player1, out int player2)
{
player1 = 0;
player2 = 0;
int? maxDiff = null;
double halfDiff = Math.Abs(Math.Ceiling((float)diff / 2));
for (int i = 0; i < team1.Length; i++)
{
for (int j = 0; j < team2.Length; j++)
{
int currentDiff = team1[i].Rating - team2[j].Rating;
if (currentDiff > 0 && diff > 0 || currentDiff < 0 && diff < 0)//elligible swap (same sign)
{
currentDiff = Math.Abs(currentDiff);
if (currentDiff <= halfDiff && (!maxDiff.HasValue || currentDiff > maxDiff))
{
maxDiff = currentDiff;
player1 = i;
player2 = j;
}
}
}
}
return maxDiff != null;
}
private static void Cut(Player[] team1, Player[] team2)
{
for (int i = 0; i < _Players.Length / 2; i++)
team1[i] = _Players[i];
for (int i = _Players.Length / 2, counter = 0; i < _Players.Length; i++, counter++)
team2[counter] = _Players[i];
}
private static void Swap(Player[] team1, Player[] team2, int team1Index, int team2Index, ref int sum1, ref int sum2)
{
Player temp = team1[team1Index];
team1[team1Index] = team2[team2Index];
team2[team2Index] = temp;
sum1 += team1[team1Index].Rating - team2[team2Index].Rating;
sum2 += team2[team2Index].Rating - team1[team1Index].Rating;
}
private static Player[] Fold(Player[] players)
{
players = players.OrderBy(x => x.Rating).ToArray();
int foldedIndex = 0;
bool rightLeft = false;
Player[] folded = new Player[players.Length];
for (int i = 0; i < players.Length / 2; i += (rightLeft ? 1 : 0), rightLeft = !rightLeft)
{
folded[foldedIndex++] = rightLeft ? players[i] : players[players.Length - i - 1];
}
return folded;
}
private static void Split(Player[] team1, Player[] team2)
{
_Players = Fold(_Players);
Cut(team1, team2);
int s1, s2, sum1, sum2;
sum1 = team1.Sum(x => x.Rating);
sum2 = team2.Sum(x => x.Rating);
int diff = sum1 - sum2;
while (diff != 0 && FindSwappables(team1, team2, diff, out s1, out s2))
{
Swap(team1, team2, s1, s2, ref sum1, ref sum2);
diff = sum1 - sum2;
}
}
#region Util
private static void GeneratePlayers()
{
DateTime start = DateTime.Now;
_Players = new Player[_TotalPlayers];
for (int i = 0; i < _Players.Length; i++)
_Players[i] = new Player { Name = "Player" + i.ToString(), Rating = rnd.Next(2000) };
DateTime end = DateTime.Now;
TimeSpan diff = end.Subtract(start);
Console.WriteLine(string.Format("Generated {0} players in {1} milliseconds", _TotalPlayers, diff.TotalMilliseconds));
}
private static void SplitAndReporttoConsole()
{
Player[] team1 = new Player[_TotalPlayers / 2];
Player[] team2 = new Player[_TotalPlayers / 2];
DateTime start = DateTime.Now;
Split(team1, team2);
DateTime end = DateTime.Now;
TimeSpan diff = end.Subtract(start);
Console.WriteLine(string.Format("Split {0} players into 2 {1} player teams in {2} milliseconds.", _TotalPlayers, _TotalPlayers / 2, diff.TotalMilliseconds));
float sum1 = team1.Sum(x => x.Rating);
float sum2 = team2.Sum(x => x.Rating);
float perc1 = (sum1 * 100) / (sum1 + sum2);
float perc2 = (sum2 * 100) / (sum1 + sum2);
Console.WriteLine(string.Format("Team 1: ({0:f2}%)", perc1));
foreach (Player p in team1)
Console.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
Console.WriteLine(string.Format("Team 2: ({0:f2}%)", perc2));
foreach (Player p in team2)
Console.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
}
private static void SplitAndReportToFile()
{
FileInfo fi = new FileInfo("C:\\output.txt");
FileStream fs = null;
if (!fi.Exists)
fs = new FileStream("C:\\output.txt", FileMode.Create);
else
fs = File.Open("C:\\output.txt", FileMode.Truncate);
StreamWriter sw = new StreamWriter(fs);
Player[] team1 = new Player[_TotalPlayers / 2];
Player[] team2 = new Player[_TotalPlayers / 2];
DateTime start = DateTime.Now;
Split(team1, team2);
DateTime end = DateTime.Now;
TimeSpan diff = end.Subtract(start);
Console.WriteLine(string.Format("Split {0} players into 2 {1} player teams in {2} milliseconds.", _TotalPlayers, _TotalPlayers / 2, diff.TotalMilliseconds));
float sum1 = team1.Sum(x => x.Rating);
float sum2 = team2.Sum(x => x.Rating);
float perc1 = (sum1 * 100) / (sum1 + sum2);
float perc2 = (sum2 * 100) / (sum1 + sum2);
sw.WriteLine(string.Format("Team 1: ({0:f2}%)", perc1));
foreach (Player p in team1)
sw.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
sw.WriteLine(string.Format("Team 2: ({0:f2}%)", perc2));
foreach (Player p in team2)
sw.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
sw.Close();
fs.Close();
}
private static void InsureTotalPlayers(string[] args)
{
if (args.Length > 0)
int.TryParse(args[0], out _TotalPlayers);
if (_TotalPlayers % 2 != 0)
throw new Exception("Invalid PLAYER_COUNT, must be even.");
}
#endregion
static void Main(string[] args)
{
/* _Players = new Player[]
{
new Player{Name="A", Rating=500},
new Player{Name="A", Rating=1},
new Player{Name="A", Rating=233},
new Player{Name="A", Rating=10},
new Player{Name="A", Rating=71},
new Player{Name="A", Rating=112},
new Player{Name="A", Rating=9},
new Player{Name="A", Rating=46}
};*/
_TotalPlayers = 10000;
InsureTotalPlayers(args);
_Players = new Player[_TotalPlayers];
for (int i = 0; i < _TotalPlayers; i++)
_Players[i] = new Player { Name = i.ToString(), Rating = i };
//GeneratePlayers();
SplitAndReportToFile();
Console.Write("Press any key to exit.");
Console.Read();
}
}
}and check the time :
Split 10000 players into 2 5000 player teams in 12.6953 milliseconds.That is expected but what about a random input instead of a sequence:
Split 10000 players into 2 5000 player teams in 127.9297 milliseconds.Beat that !!! ;)
#22 January 30 2011
- arithma
- Member
Re: Exercise - Team Balancing
LOL, this is hilarious. My fiance will beat me with a stick for playing away for so long. I'll see into this at night, expect some classic ass beating
#23 January 30 2011
- MSD
- Member
Re: Exercise - Team Balancing
LOL, this is hilarious. My fiance will beat me with a stick for playing away for so long. I'll see into this at night, expect some classic ass beating
LOL, I will be waiting ;)
#24 January 30 2011
- jsaade
- Member
Re: Exercise - Team Balancing
In most games, the array of teams is already sorted according to ratings by the server (when a team is selected) this minimizes time on the server.
anyways greed is good :)
#include <iostream>
#include <vector>
using namespace std;
void main(void){
vector<int> a;
int const K = 10000;
for(int i = 0; i < K; i++){
a.push_back(rand());
}
vector<int> TL;
vector<int> TR;
TL.push_back(a[0]);
TR.push_back(a[1]);
size_t idx = 2;
int maxSum = a[0];
int minSum = a[1];
vector<int> *currentMax = &TL;
vector<int> *currentMin = &TR;
while(idx < a.size()){
(*currentMin).push_back(a[idx]);
minSum += a[idx];
if(minSum > maxSum){
int tmpSum = minSum;
minSum = maxSum;
maxSum = tmpSum;
vector<int> *tmp = currentMin;
currentMin = currentMax;
currentMax = tmp;
}
idx++;
}
cout<<minSum<<endl<<maxSum<<endl;
cout<<(*currentMin).size()<<endl<<(*currentMax).size()<<endl;
}Edit: forgot to restrict team members to be equal , might do it later
Last edited by ZeRaW (January 30 2011)
#25 January 30 2011
- jsaade
- Member
Re: Exercise - Team Balancing
(rating is always positive).
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
using namespace std;
void main(void){
vector<int> a;
int const K = 1999500;
for(int i = 0; i < K; i++){
a.push_back(rand());
}
sort(a.begin(),a.end());
clock_t start;
start = clock();
vector<int> TL;
vector<int> TR;
TL.push_back(a[0]);
TR.push_back(a[1]);
size_t idx = 2;
unsigned int maxSum = a[0];
unsigned int minSum = a[1];
vector<int> *currentMax = &TL;
vector<int> *currentMin = &TR;
while(idx < a.size()){
(*currentMin).push_back(a[idx]);
minSum += a[idx];
if(minSum > maxSum || (*currentMin).size() > (*currentMax).size()){
int tmpSum = minSum;
minSum = maxSum;
maxSum = tmpSum;
vector<int> *tmp = currentMin;
currentMin = currentMax;
currentMax = tmp;
}
idx++;
}
cout<<"Execution Time: "<<( double(clock() - start)/CLOCKS_PER_SEC )<<endl;
cout<<minSum<<endl<<maxSum<<endl;
cout<<(*currentMin).size()<<endl<<(*currentMax).size()<<endl;
}Execution Time: 0.038
3505837259
3505853690
999750
999750