TopXorer
SRM 723 · 2017-11-17 · by cgy4ever
SRM 723 · 2017-11-17 · by cgy4ever · Math
Problem Statement
Problem Statement
Like Topcoder, TopXorer uses a rating system.
The rating of each person is a non-negative integer.
You are a coach. You want to select an n-person team. The team members will be labeled 0 through n-1. You have a set of constraints decribed by theint[] x with n elements.
For each valid i, the rating of team member i must be between 0 and x[i], inclusive.
As the name suggests, the rating of a team in TopXorer is computed as the bitwise xor of the ratings of all team members.
You are given theint[] s x.
Please compute and return the maximal team rating your team can have.
You are a coach. You want to select an n-person team. The team members will be labeled 0 through n-1. You have a set of constraints decribed by the
As the name suggests, the rating of a team in TopXorer is computed as the bitwise xor of the ratings of all team members.
You are given the
Constraints
- x will contain between 1 and 50 elements, inclusive.
- Each element in x will be between 0 and 1,000,000,000, inclusive.
Examples
0)
{2,2,2}
Returns: 3
One optimal solution is to select people with ratings (2, 0, 1). The team rating will then be (2 xor 0 xor 1) = 3.
1)
{1,2,4,8,16}
Returns: 31
This time the only optimal solution is to select people with the largest possible ratings.
2)
{1024,1024}
Returns: 2047
3)
{7,4,12,33,6,8,3,1}
Returns: 47
4)
{0}
Returns: 0
Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TopXorer with a public method int maximalRating(vector<int> x) · 107 test cases · 2 s / 256 MB per case