Sprague-Grundy numbers#11794
Lucy hates problems about Sprague-Grundy numbers. After encountering yet another problem involving Sprague-Grundy numbers in a contest, she became upset and decided to create a problem about XOR and MEX, without Sprague-Grundy numbers. Here is her problem:
Given a beautiful array of integers of length . Define a function on its subarrays as [ f(l, r) = a_l a_l+1 a_r. ]
We call an array beautiful if and only if there do not exist three distinct pairs of indices (l_1, r_1), (l_2, r_2), (l_3, r_3) such that l_1 \leq r_1, l_2 \leq r_2, l_3 \leq r_3, and [ f(l_1, r_1) = f(l_2, r_2) = f(l_3, r_3) < n. ]
It is required to partition the array into contiguous subarrays such that:
The subarrays do not overlap.
Each element belongs to exactly one subarray.
Your goal is to maximize \operatorname{mex}(f(l_1, r_1), f(l_2, r_2), \dotsc, f(l_k, r_k)), where is the number of subarrays in your partition, l_1 = 1, r_k = n, and r_i + 1 = l_{i+1} for 1 \leq i < k.
The mex (minimum excluded value) of a set of non-negative integers is the smallest non-negative integer not present in the set. For example, \operatorname{mex}(\{1, 0, 2, 4\}) = 3, \operatorname{mex}(\{1, 2, 3\}) = 0, and \operatorname{mex}(\{0, 2, 3\}) = 1.
The first line contains one integer (1 \leq n \leq 10^5) — the length of the array .
The second line contains integers a_i (0 \leq a_i < 2^{60}) — the elements of the array .
Output the maximum value of \operatorname{mex}(f(l_1, r_1), f(l_2, r_2), \dotsc, f(l_k, r_k)).
Example 1
Example 2
In the second sample, we can split the array into the following subarrays: , , , , achieving the value \operatorname{mex}(f(1, 2), f(3, 4), f(5, 5), f(6, 6)) = \operatorname{mex}(2, 0, 16, 1) = 3. It can be shown that this is the best answer.
( points): n \leq 5;
( points): n \leq 10;
( points): n \leq 20;
( points): n \leq 1000;
( points): n \leq 10^5;