SumOfXor
2016 TCO India Regional · 2016-03-24 · by cgy4ever
2016 TCO India Regional · 2016-03-24 · by cgy4ever · Advanced Math, Greedy
Problem Statement
Problem Statement
There are n cards, the i-th one has number x[i] write on it. And there are 2 bags. For each card, you must choose one bag and put that card into that bag.
Suppose the XOR of all numbers in bag 1 is s1, and the XOR of all numbers in bag 2 is s2, your goal is to find the maximal value of (s1 + s2). Note that it is ok if one bag contains no cards, in that case the XOR is 0.
Suppose the XOR of all numbers in bag 1 is s1, and the XOR of all numbers in bag 2 is s2, your goal is to find the maximal value of (s1 + s2). Note that it is ok if one bag contains no cards, in that case the XOR is 0.
Notes
- You can assume the result will fit into 64 bits signed integer.
Constraints
- x will contain between 1 and 1,000 elements, inclusive.
- Each element in x will be between 0 and 1,000,000,000,000,000 (i.e. 10^15), inclusive.
Examples
0)
{1,3,2}
Returns: 6
We need to put {1,2} into one bag and {3} into another, then we can get 3+3 = 6.
1)
{1,2,4,8,16,32}
Returns: 63
One optimal solution is to put everything into one bag.
2)
{123,456,789,101112,131415,161718,192021}
Returns: 323412
3)
{1000000000000000,1000000000000000,1000000000000000,1000000000000000}
Returns: 2000000000000000
4)
{0}
Returns: 0
Submissions are judged against all 95 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SumOfXor with a public method long long maxSum(vector<long long> x) · 95 test cases · 2 s / 256 MB per case