### acc1's blog

By acc1, 11 years ago, I need to divide a set of players into two teams such that the team is balanced as far as possible .

Balancing is with respect to their skill values.

One of the team must have floor(n/2) players.

I initially thought it to be a NP-Complete problem , but I am now thinking that it a DP problem may be.

Can anyone tell how to solve this question.

Example:

Players: 5

Skill values:

Player 1 : 4

Player 2 : 1

Player 3 : 4

Player 4 : 56

Player 5 : 3

Optimal solution will have two teams of Total Skill values 11 and 57 respectively.

Now Constraints ( These contraints may also be helpful in solving the problems ):

Skill value of each player <= 570

Total Number of players  <  200

----------------------------------------------

Plz tell how to solve , any method You think of as the best  , plz write it . dp, Comments (8)
 First of all, an NP-complete problem may have a DP solution under certain constraints. In this particular one (which is NP-complete in general), suppose that you can count values possible[i][j], which is true if it is possible to take a subset of the first i players with summary skill j, and false otherwise. Then, to answer the problem you'd need to find the value of j closest to sum(skill[i])/2 for which possible[N/2][j] is true (the closer j is to the sum of skills, the more balanced your teams are). I propose you to find the recurrent relation of computing possible[i][j] yourself.
•  11 years ago, # ^ | ← Rev. 3 →   I believe, you meant "subset of size i", not "subset of the first i players", because otherwise possible[N/2][j] just gives info about the fact that we can or can not choose subset of first N/2 players with the given sum which is not what we need. Right?
•  Yep, was writing something similar to your idea and got lost in between :)
 11 years ago, # | ← Rev. 2 →   First idea that pops into mind - kind of knackpack:let F(i,j,k) be true if it is possible to choose j players out of first i such that sum of their skill is k. If F(i,j,k) is true, then F(i+1,j,k) and F(i+1,j+1,k+skill(i+1)) are also true. Once you fill all the table, you can find F(n,floor(n/2), k)=true such that k is as close to sum of all skils/2.0. However, this method has complexity O(M*N*N*N) where M is maximum possible skill and what I've described is not fast enough to fit in 1s if it is a contest problem.
 @maksay and gojira , Thank You for your precious time . So, as maksay described above , it can be solved in O(M*N*N*N) time and O(N*N*S/2) space.where N = no. of players.M = Max possible skills of any particular player.S = total_skill_sum .----------------------------------I need a bit faster (and if possible then , a space efficient) way of doing it.As this was a first idea that came to maksay's mind , can anyone (incl. maksay ) improve upon it (!).
•  11 years ago, # ^ | ← Rev. 3 →   If you need only total skills of team, then you can reduce memory to O(N*S), because when you process new player you need only in F[i][][] and F[i + 1][][].some idea:If we guess, that absolute value of skill sums of two teams in optimal solution <= M (maximal skill overall), then we can modify dp of maksay in the following way:f(n, first_team, diff) = true/false -- if it possible to make difference of skills equals to diff, and we choose first_team players for first team of the first n.In this way the complexity is O(n * n * m).But i'm not sure in my guess. Maybe someone can try to prove or disprove this? I'm thinking in the following way (a - is 1-indexed array of skills): 1) sort all skills from small to large. 2) for 0 players guess is right, for 2 players too, 3) for n player (n is even) we have next: if for (n - 2) players we can make |difference| <= M, then if difference < 0 then we add a[n] - a[n - 1] (n to first team, n - 1 to second team), if difference >= 0 then we add a[n - 1] - a[n] (n - 1 to first team, n to second team) and |difference| still <= M, so by induction it right for any n. 4) if n is odd, then we take solution for n - 1 and if difference(n - 1) >= 0 then add a[n] to second team (difference - a[n]), else to first team (difference + a[n]), and new |difference| will be <= a[n] and <= M.
 11 years ago, # | ← Rev. 2 →   Thank You cmd for your kind effort.Your proof seems correct to me.that max possible difference between two teams formed at last will be  <= M.M = max skill value of any particular player.Now, Can you provide a little bit more detail on how to implement your DP.i.e. how to go about finding f(n , first_team , diff) .maksay's dp was easier for me to implement. As it was starting from base case and kept on adding new elements ..by scanning through skills one by one.I would like to know how to go about your DP because it has diff as last parameter , I am a bit lost.Can anyone provide an insight.
•  Seems to be, that my dp is wrong, because intermediate difference can be more than M. For example: skills = 5 5 4 4 4 2 - if we process players in this order, then after two steps difference will be 10 (> 5), however the resulting difference < M.So it dp still O(n * n * s).