Pororo789's blog

Problem
By Pororo789, history, 5 years ago, translation, In English

how to solve this problem:

given a n — numbers of players and their height h_i. You need to split to k teams that the incompatibility is minimal. Incompatibility is the sum of the mx(maximum height of team player)-h_i(height of other player)

n <= 10^5

k <= min(n,20)

h_i <= 10^6

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please give sample input/output and its explanation to understand the problem better.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Give some example input and result (or a link to the original problem) cause I'm not sure if I understand the problem properly. This is my idea: 1) Sort all the players by their heights increasingly. We can assume that the best solution always put players with similar heights to one team (because it's optimal) so our problem is just to divide this sorted array into segments. If some players should be in one team, they're consecutive segment in the array. 2) Calculate prefix sums for the sorted array. It let us to count incompatibility of a given team in O(1) 3) Apply dynamic programming to two-dimensional array with n columns and k rows. The solution will be in left-down corner of the array. Complexity is O(k*n). I think it's enough as it needs at most 2*10^6 operations.

→ Reply