XorAndLIS
SRM 729 · 2018-02-08 · by cgy4ever
SRM 729 · 2018-02-08 · by cgy4ever · Advanced Math
Problem Statement
Problem Statement
Let LIS(S) denote the length of the longest increasing subsequence of the sequence S.
Note that the subsequence does not have to be contiguous.
For example, for S1 = {10,0,20,0,30} we have LIS(S1) = 3 and for S2 = {1,1,1} we have LIS(S2) = 1.
You are given along[] x: a sequence of nonnegative integers.
You are allowed to modify this sequence by performing a sequence of zero or more updates.
In each update, you select an index i between 0 and |x|-2, inclusive, and you change x[i+1] into (x[i+1] xor x[i]).
Your goal is to make LIS(x) as large as possible. Please compute and return this maximal value.
You are given a
Your goal is to make LIS(x) as large as possible. Please compute and return this maximal value.
Constraints
- x will contain between 1 and 100 elements, inclusive.
- Each element in x will be between 0 and 10^18, inclusive.
Examples
0)
{4,2,1}
Returns: 3
You can do x[1] = x[1] xor x[0], the sequence will be {4,6,1}. Then you do x[2] = x[2] xor x[1] and the sequence becomes {4,6,7}.
1)
{0,0,0,0,0,0,0,0,0,0}
Returns: 1
Whatever you do, the sequence never changes, and the LIS is 1.
2)
{1,2,3,4,5,6,7,8,9,10}
Returns: 10
This time you don't need to do anything.
3)
{7,3,1}
Returns: 2
4)
{1008,42,7,5,2,9,75,0,0,12,3,6,81,4,3}
Returns: 12
Submissions are judged against all 138 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class XorAndLIS with a public method int maximalLength(vector<long long> x) · 138 test cases · 2 s / 256 MB per case