SquadConstructor2
SRM 731 · 2018-03-16 · by subscriber
Problem Statement
In the game there are n strategies a team can play. Each of Hero's players can only play some subset of those strategies well. For each player the subset of strategies they can play well is different from the others.
A set of strategies can be encoded into an n-bit number: If we number the strategies 0 through n-1, the code of a set of strategies will be the number that has, in base 2, ones on positions that correspond to the strategies in the set.
For example, the set {0,3,4} is encoded as the number 11001 in base 2. (Bits 0, 3, and 4 are ones and the remaining bits of this number are zeros.) The value of this number in base 10 is 2^4 + 2^3 + 2^0 = 25.
You are given the
Finally, you are given an
The strength of a squad is calculated as follows: For each strategy, compute the square of the number of players on the squad that play that strategy well. The strength of the squad is the sum of all those squares.
Compute and return the largest possible strength of a k-player squad.
Constraints
- n will be between 3 and 8, inclusive.
- k will be between 2 and 8, inclusive.
- friends will contain between k and 2^n elements, inclusive.
- Each element in friends will be between 0 and 2^n-1, inclusive.
- All elements in friends will be distinct.
Statement by TopCoder, Inc. — view the original on the archive.
3
4
{0,1,2,3}
Returns: 8
As there are only four players and Hero needs a four-player squad, he has to select all four players. Two of them can play strategy 0 well, two of them can play strategy 1 well, and nobody can play strategy 2 well. Thus, the total strength of this squad is 2^2 + 2^2 + 0^2 = 8.
3
4
{0,1,2,3,5}
Returns: 14
Select everyone except for the player who cannot play any strategy well. This produces a squad with the strength 3^2 + 2^2 + 1^2 = 14.
8
4
{0,1,2,3,7}
Returns: 19
8
4
{3,4,7,8,9,10,11,15,16,17,18,19,20,21,23,26,27,28,29,33,35,37,41,42,43,45,47,48,49,53,54,55,56,57,58,60,61,62,64,66,67,68,72,74,75,78,80,81,82,83,87,89,90,91,93,94,95,98,99,100,101,103,105,108,111,112,113,115,118,119,121,122,123,125,127,128,129,130,131,137,143,144,147,148,151,152,155,156,160,163,167,169,171,172,173,178,179,180,182,186,188,190,192,193,194,195,196,198,199,204,207,208,212,213,215,217,219,220,221,225,228,231,233,237,240,243,244,245,246,247,249,251,252,254}
Returns: 100
3
5
{0,1,2,3,5}
Returns: 14
Submissions are judged against all 106 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SquadConstructor2 with a public method int teamget(int n, int k, vector<int> friends) · 106 test cases · 2 s / 256 MB per case