TrySail
SRM 694 · 2016-06-25 · by IH19980412
Problem Statement
There are N students in your class.
The strength of each student is a small nonnegative integer.
You are given these strengths in the
You are going to divide all students into three teams for the boat race "TrySail". Each student must be assigned to exactly one of the three teams. Teams cannot be empty.
Strangely enough, in this race the strength of a team is the bitwise xor of the strengths of its members. You want to maximize the sum of strengths of the three teams. Compute and return the largest possible sum of the teams' strengths.
Constraints
- N will be between 3 and 50, inclusive.
- strength will contain exactly N elements.
- Each element of strength will be between 0 and 255, inclusive.
{2,3,3}
Returns: 8
There are only three students. The only way to create three nonempty teams is to put each student into a different team. In that case the sum of teams' strengths will be 2+3+3 = 8.
{7,3,5,2}
Returns: 17
There are 6 ways to make 3 teams: · {0},{1},{2,3}: sum of strengths is 7+3+(5 xor 2) = 17 · {0},{2},{1,3}: sum of strengths is 7+5+(3 xor 2) = 13 · {0},{3},{1,2}: sum of strengths is 7+2+(3 xor 5) = 15 · {1},{2},{0,3}: sum of strengths is 3+5+(7 xor 2) = 13 · {1},{3},{0,2}: sum of strengths is 3+2+(7 xor 5) = 7 · {2},{3},{0,1}: sum of strengths is 5+2+(7 xor 3) = 11 Therefore, the answer is 17.
{13,13,13,13,13,13,13,13}
Returns: 26
{114,51,4,191,9,81,0,89,3}
Returns: 470
{108,66,45,82,163,30,83,244,200,216,241,249,89,128,36,28,250,190,70,95,117,196,19,160,255,129,10,109,189,24,22,25,134,144,110,15,235,205,186,103,116,191,119,183,45,217,156,44,97,197}
Returns: 567
Submissions are judged against all 88 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TrySail with a public method int get(vector<int> strength) · 88 test cases · 2 s / 256 MB per case