It's a bright, cheerful day in the whimsical town of Permexorpia. This peculiar place has a tradition that has never been seen before: friends exchange elaborate mathematical objects as tokens of affection. Today, we witness our dear friend Alice meticulously preparing a special present for her companion, Bob. Knowing Bob’s fondness for rare types of sequences, Alice has crafted an incredibly thoughtful and unique gift—a beautifully wrapped permutation.
In Permexorpia, a permutation of size $$$n$$$ is a list containing each of the numbers $$$0, 1, 2, ..., n-1$$$ exactly once (notice the list contains $$$0$$$ and does not contain $$$n$$$).
Upon receiving this extravagant gift, Bob, who is an avid enthusiast of unusual mathematical operations, decides to compute something truly intriguing: the XOR of the MEX of every single possible continuous subarray† of the permutation given by Alice. More formally, let $$$f(p)$$$ be the value calculated by Bob for a given permutation $$$p$$$. We have:
Where $$$p[i,j]$$$ denotes the subarray $$$[p_i, p_{i+1}, p_{i+2} ..., p_{j-1}, p_j]$$$, mex denotes the Minimum Excluded value and $$$\oplus$$$ denotes the XOR operation.
† A continuous subarray of an array $$$a$$$ is an array obtained by deletion of several (possibly zero) elements from the beginning of $$$a$$$ and several (possibly zero) elements from the end of $$$a$$$, while keeping the remaining elements in the same order.
Input
The first line contains an integer $$$t$$$ – the number of independent test cases ($$$1 \leq t \leq 10^4$$$).
Each test case consists of two lines. The first line of each test case contains an integer $$$ n $$$, the size of the permutation $$$p$$$.
The following line contains $$$n$$$ distinct integers $$$p_1, p_2, \dots, p_n$$$, each integer raging from $$$0$$$ to $$$n - 1$$$.
It is guaranteed that the sum of $$$n$$$ does not exceed $$$5 \cdot 10^5$$$ over all test cases.
Output
Output a single integer — the value of $$$f(p)$$$, the XOR of the MEX values of all possible continuous subarrays of the given permutation.
Example
Input
3
3
1 0 2
4
0 1 3 2
1
0
Output
1
5
1
Note
Recall that the MEX (Minimum EXcluded value) of a sequence is the smallest non-negative integer that does not appear in the sequence. For instance:
The MEX of
[0, 1, 2]is3.The MEX of
[1, 2]is0.The MEX of
[0, 2, 3]is1.
I think the problem can be solved given the constraints, but I am not sure to be completely honest (I haven't actually tried). This is supposed to be a joke regarding the excessive amount of XOR, MEX and permutation problems in codeforces. Also I could make a constructive version: build the array $$$p$$$ that minimizes $$$f(p)$$$ for a given $$$n$$$.
Edit: the problem can be solved in $$$O(n)$$$. See other comments if you need guidance.
Seems like an easier version of 2084E - Blossom in terms of the basic observation
LOL, truly a codeforces problem
Also the excessive verbosiness of some problems. Foo gives array to Bar, blah blah blah, then you speed read and miss a subtle but super important information to solve the problem. If you want to make the statement verbose at least make it funny!
And yet here you only need to look at the Output section. You can complicate problemsolving for yourself, but you aren't in any way forced to.
ahh I had the same variant in mind when I read half of the problem — "build the array p that minimizes f(p) for a given n". but maybe we'd find some trivial solution to that.
Like, I'm expecting some array with 0 at one end, and maybe 1 at the other. So, MEX would mostly be 0, and it would be 1 in (n-1) cases and n in only 1 case.
saptarshi1729 heyy man, Are u the same Saptarshi Mukherjee who i met in Mumbai during VVM National Competition?? You might remember me, Nikhil and Omprakash Behera.
@niku_raaz hey, might not be, I'm not sure. I did visit Mumbai recently, and met many IITians and others there, in a conference held at the Jio World Convention Centre. And the names you mentioned do ring a bell in my mind, but I'm a bit doubtful. Maybe he was different :)
saptarshi1729 orz
It is possible to solve this problem in $$$O(n)$$$.
Notice that $$$mex(p[i,j]) = \min(\min(p[1, i - 1]), \min(p[j + 1, n]))$$$, unless $$$i = 1$$$ and $$$j = n$$$.
For each $$$i$$$, find the number (say $$$d$$$) of indices $$$j$$$ such that $$$\min(p[j + 1, n]) \gt \min(p[1, i - 1])$$$, which can be done easily using two pointers. So, there are $$$d$$$ subarrays that start at index $$$i$$$ and have $$$mex = \min(p[1, i - 1])$$$.
You can do a similar thing for suffix minimums.
So, for each $$$x$$$ from $$$0$$$ to $$$n$$$, you know the number of pairs $$$(i, j)$$$ such that $$$mex(p[i,j]) = x$$$. You can then take the xor of all integers $$$x$$$ such that there are an odd number of subarrays for which $$$mex = x$$$.
Yes, I just tried the following and I think it solves the problem (it matches the simple test case I have done):
Yeah, I realised that I have solved this problem before. It is the same problem, but on a tree.
I think you could just loop over each possible MEX value: if you want the MEX to be exactly 1, the chosen subarray must contain 0 and cannot contain 1. If we want the MEX to be 2, the subarray must contain 0 and 1, but not 2. For each MEX value $$$x$$$, look at the positions of the values $$$0,1,2,...,x-1$$$, and denote the leftmost and rightmost positions as $$$l$$$ and $$$r$$$, and denote the location of the value $$$x$$$ as $$$i$$$. Given this, to obtain a MEX of $$$x$$$, our subarray must encompass $$$[l,r]$$$ and cannot touch $$$i$$$. Denote the leftmost/rightmost allowed values as $$$lo$$$ and $$$hi$$$, and we can then get the number of valid subarrays as $$$(l-lo+1) \cdot (hi-r+1)$$$.
To handle the xor part, for each MEX value $$$x$$$ with $$$n$$$ corresponding subarrays, you do
ans ^= x*(n%2).I have done exactly that, thanks! See this comment. Only difference is I simply calculated the number of arrays such that MEX is $$$\geq i$$$ and then subtracted from the next value to get the number where it is equal to $$$i$$$.
this is straight up E — blossom but the two pointer variation