PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
This problem is the easiest one in this set. Given an array Score[1…11] of eleven elements and an integer K, find the number of ways in which a subset of exactly K elements can be selected such that the sum of its elements is the maximum possible. Its easy to see that to get the maximum sum, we need to pick the elements in non-increasing order. We start picking elements and suppose there are M players with score S and we need to still pick K more players. If K > M, then all the players having score S should be taken, otherwise K ? M and we need to select K players from these M players. This is the only choice we have to make. All players having score greater than S must be taken. Players having score less than S must not be taken, as it only decreases the total sum. So the number of ways is binomial(M,K). See setters code for a simple implementation of this idea.
Alternate Solution : As the number of players is only 11, we can try all possible K element subsets and find the sum of scores. We maintain the maxSum and count ( number of subsets so far with sum = maxSum ). If the current_sum is greater than maxSum, update the maxSum = current_sum and count = 1, else if its equal update count++; Refer tester’s code for this.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.