What does it mean?

Dammn bro, you have unlocked "Advanced Observation Haki".

I have solved problem D1 using binary search. I think there must be binary search tag in problem D1. :) Total time complexity is nlog^2(n)

// Muallif: Mansuraliyev Husanboy Murotali o'g'li  >> NamPS
//#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(a) a.begin(), a.end()
#define F first
#define S second
// 0-9 >> 48-57;    A-Z>>65-90   and   a-z>>97-122 respectively;



void solve(){
	vector<int> comp;
	int L,n; cin>>L>>n;
	 for(int i=0;i<=n;i++) {
		int x; cin>>x; comp.push_back(x);
	}sort(all(comp));
	int l=0,r=n;
	while(l<=r){
		int m=(l+r)/2;
		vector<int> v;
		for(int i=0;i<=n;i++){
			int k=comp[m]^i;
			v.push_back(k); 
		}
		sort(all(v));
		if(v==comp){
			cout<<comp[m]<<"\n"; return;
		}else{
			if(v<comp) l=m+1;else r=m-1;
		}
	}
}


int main(){
	ios;
	int t; cin>>t; while(t--)
	solve();
}

believe me bro

One way to build a satisfying permutation: After rotating the array c[], write the numbers 1 to n one-by-one from the position(s) with highest c[i] to lowest c[i]. If there exists multiple positions with the same value, go from the largest index to the smallest.

Probably not the easiest way to do it, but one of them. Assume we are adding elements from 1 to N — 1 in front of element N. Now, let's make the permutation. From now on, f[i] equals number of different prefix maximums after we add i elements (so, if N is in position k, then f[1] = c[k + 1] etc.). Claim: if we put element N — 1 into position num, then: A) f[num] = 2 — it will be bigger than all elements at the front, and smaller than N. B) if pos1 > num, then f[pos1] > f[num] (otherwise, this element is bigger than N + 1) So, we put N — 1 into position [k + num]. Then, we have divided our sequence into two parts. If the length of the first one is l1, and the second one l2 (l1 + l2 = N — 2), then let the values of the first sequence be one of a permutation[1:l1], and the second [l1 + 1; l2]. Solve for them recursively. So, we have constructed a permutation which satisfies our condition.

Let 'c' be an array satisfying the necessary conditions. Rotate 'c' such that its first position is 1 without loss of generality. We will explicitly construct a permutation p obeying c. The first element of p is N.

let a = no. of 2s in array c, b = no. of 3s in array c and so on.

s[2] = {N-1,N-2,N-3...N-a} s[3] = {N-a-1, N-a-2, N-a-b} and so on.

Now traverse the array c from 2nd position.

if the element of c is k, place the lowest element of s[k] at the last available position of p and remove that element from s[k].

We're done.

This is an example of how the construction would go: Suppose n = 8, c array = 1 2 3 4 5 3 4 2

We always start with the largest element:

• [8, _, _, _, _, _, _, _] 1

• [7, 8, _, _, _, _, _, _] 2

• [6, 7, 8, _, _, _, _, _] 3

• [5, 6, 7, 8, _, _, _, _] 4

• [4, 5, 6, 7, 8, _, _, _] 5

• [6, 3, 4, 5, 7, 8, _, _] 3 (rightmost r where c_r = 3, leftmost l where c_l = 5. Decrement l to r by 1. (l,r) = (0, 2). Add original a_r to first position.)

• [6, 5, 2, 3, 4, 7, 8, _] 3 ((l, r) = (0, 0))

• [7, 5, 4, 1, 2, 3, 6, 8] 2 ((l, r) = (0, 6))

We can check this is correct:

• [8, 7, 5, 4, 1, 2, 3, 6] 1

• [6, 8, 7, 5, 4, 1, 2, 3] 2

• [3, 6, 8, 7, 5, 4, 1, 2] 3

• [2, 3, 6, 8, 7, 5, 4, 1] 4

• [1, 2, 3, 6, 8, 7, 5, 4] 5

• [4, 1, 2, 3, 6, 8, 7, 5] 3

• [5, 4, 1, 2, 3, 6, 8, 7] 3

• [7, 5, 4, 1, 2, 3, 6, 8] 2

Sketch of Formal Proof: To be added.

can you explain more

Why take the min of all x and not stop when you find the first one?

I did the same thing: 233974285
But I am assuming that $$$a_i = l \oplus x$$$ and checking if $$$x = a_i \oplus l$$$ for each $$$i$$$ like in the editorial.
You seem to be checking if $$$x = a_0 \oplus i$$$ for each $$$i$$$. Why does that work?

Okay while writing this I understood you are just trying to find the $$$i$$$ for which $$$x \oplus i = a_0$$$.
Amazing solution!

@variety-jones In this ticket the expected and the actual output seem to be the same but still it says they're different. What am I missing?

In this problem, we use trie(or similar structures) to calculate the number of $$$a_i$$$ such that $$$a_i \oplus x\in [l,r]$$$. So it is sufficient to calculate the number of $$$a_i$$$ satisfying $$$a_i \oplus x < r$$$.

In such queries, we can enumerate the longest common prefix of $$$a_i \oplus x$$$ and $$$r$$$ (in binary, of course, starting from the highest bit). Say this common prefix ends at the $$$k$$$-th bit.

Then we know exactly what the highest $$$17-k$$$ bits for $$$a_i$$$ should be, since $$$a_i \oplus x$$$ share the same bits with $$$r$$$. And the $$$k-1$$$-th bit in $$$r$$$ must be equal to $$$1$$$ (for the $$$0$$$ bits, just skip them), while the same bit in $$$a_i \oplus x$$$ should be $$$0$$$. The last several bits (from $$$k-2$$$ to $$$0$$$) no longer matters.

Thus, for each $$$k$$$, all we need to do is to precaculate the number of $$$a_i$$$ with some specific highest $$$18-k$$$ bits. This can be done using trie or simple arrays.

Trie : the number we wanted is equal to the number of leaves in a specific subtree, which can be precalculated during the trie building part. To find the subtree, just go down the trie while decreasing $$$k$$$. See my code for details.

Arrays : you can precalculate the number using arrays of size $$$2^{17-k}$$$ for each $$$k$$$ (or simply cnt[17][1<<17]). It's like a counting machine. Each $$$a_i$$$ will only contribute to one position in this array for each $$$k$$$. The time and space complexity should be the same as trie.

(Sorry for my poor English. The details in my explanation may not be very clear. Hope you understand the method.)

You can also use trie or arrays to solve "the max and min of $$$a_i \oplus x$$$" problem, which is mentioned in other comments.

BTW, I've been wondering whether $$$x$$$ is fixed when $$$r-l+1$$$ is odd, since $$$\oplus a_i=\oplus_{l\le i\le r} (i\oplus x)$$$. Hope I'm not alone.

Think in a permutation of lenght 5 like {5 4 3 2 1}, whose power is 1, now is there a way so in just one shift the power becomes 3? there isn't since whichever number you choose to put in fisrt place {x 5 ...} the five will make the array b = { x 5 5 5 5}. in other words, you can sum 1 to the power by sifhting the last number x where x < P[0], because this number will be counted in the power but for summing two you need to put at least two numbers in the beginning so that the b of the permutation becomes b = {x, y, 5, 5, 5} where x < y < 5 which is impossible with one shift (you only sifht one number).

This isn`t to mathematical and I only did this with a permutation of lenght 5, but i think it could be intuitive.

Sharing again!

Let 'c' be an array satisfying the necessary conditions. Rotate 'c' such that its first position is 1 without loss of generality. We will explicitly construct a permutation p obeying c. The first element of p is N.

let a = no. of 2s in array c, b = no. of 3s in array c and so on.

s[2] = {N-1,N-2,N-3...N-a} s[3] = {N-a-1, N-a-2, N-a-b} and so on.

Now traverse the array c from 2nd position.

if the element of c is k, place the lowest element of s[k] at the last available position of p and remove that element from s[k].

We're done.

l<=x<=r

Nope

Come on, guys. That was just a joke for anime fandom

Ok, let me try to rewrite and add some pictures and examples too. Sorry for the inconvenience right now.

Agreed, I haven't seen an editorial so cryptic in a long time, it took me a while to realize what they're getting at. Here's an attempt at explaining the idea.

Note: all variable names will either be the same ones used in the problem statement or explicitly defined.

Part 1: How many zeros and ones are in the answer?

Let the number of ones in $$$s$$$ be $$$ones$$$. The cuteness of the entire string by definition is $$$\frac{ones}{n}$$$. The concatenated string of length $$$m$$$ that we're looking for has the same cuteness, so the number of ones in it is $$$\frac{ones}{n} \cdot m$$$. Therefore, there is no answer if that value is not an integer (i.e. $$$ones \cdot m \not \equiv 0 \bmod n$$$).

Part 2: How do we find the answer with the minimum number of parts?

Let $$$x = \frac{ones}{n} \cdot m$$$.

Let's also assume the string is circular for now. Consider any length $$$m$$$ subarray in this circular string, including subarrays that wrap around. If we can find a subarray with exactly $$$x$$$ ones, then the minimum number of parts we need is either $$$1$$$ or $$$2$$$, depending on whether or not it wraps around. And both can be checked with sliding window/prefix sums.

It turns out such a subarray always exists. Let $$$c_i$$$ be the number of ones in $$$s[i \dots i + m - 1]$$$ if $$$i \leq n - m + 1$$$, or $$$s[1 \dots m - (n - i + 1)] + s[i \dots n]$$$ otherwise (basically, subarrays that wrap around versus subarrays that don't). Note that $$$|c_{i+1} - c_i| \leq 1$$$ for all $$$1 \leq i < n$$$ and $$$|c_1 - c_n| \leq 1$$$. This is because if we slide the subarray we're considering from $$$i$$$ to $$$i + 1$$$, we exclude $$$s_i$$$ and include $$$s_{((i+m-1) \bmod n) + 1}$$$. So the number of ones in our subarray can only increase or decrease by at most $$$1$$$. The implication of this is that there exists some $$$c_i = y$$$ for all $$$\min c_i \leq y \leq \max c_i$$$ because there's no way to go from a small to large $$$c_i$$$ while "skipping" over the values in the middle.

It holds that $$$\max c_i \geq x$$$ and $$$\min c_i \leq x$$$, implying some $$$c_i = x$$$. Assume that $$$\max c_i < x$$$. This means $$$\sum_{i=1}^n c_i < n \cdot x$$$. Furthermore, each index is included in exactly $$$m$$$ different subarrays. So $$$\sum_{i=1}^n c_i = m \cdot ones$$$. Thus, $$$m \cdot ones < n \cdot x$$$, or $$$x > m \cdot \frac{ones}{n}$$$ which is a contradiction by definition of $$$x$$$. Similarly, assume $$$\min c_i > x$$$. $$$\sum_{i=1}^n c_i = m \cdot ones > n \cdot x$$$, or $$$x < m \cdot \frac{ones}{n}$$$ which is a contradiction. Therefore, $$$\max c_i \geq x$$$ and $$$\min c_i \leq x$$$.

It doesn't work on a test $$$l=1$$$, $$$r=2$$$, $$$a = [0, 3]$$$.

You cannot form any substring of length >= 2 in a string of length 1 as the statement says

correct

Think about this case

1 4

0 2 3 5

The answer is 1 and with bit count the answer should be 0.

1 4

2 1 0 7

Another case, answer = 3 and with bit count should be 0.

According to me, if we solve D2 using bit count (method to solve D1) , there will not be any issue if bit count at any position for actual array and xored-array will be different. But if at any position, bit count will be same, we can't directly take (any of) 0 or 1 as the value of bit at that position for x ( as we did in D1 ).

LET'S CONSIDER THIS TEST CASE:

l=1 r=4

2 3 0 5 ( xored-array )

If we solve it using method used in D1, we will get output 0, but it's answer should be 1.

Please verify if I am correct.

I just realized that the "next cyclic shift" is not created by moving the first element to last position, but instead by moving the last element to first position.

Thank you so much for your explanation.The tutorial for D2 didn't tell why initialize ans to l or r(Line 23-25 in C++ code), so I was confused. You explain this in your solution(Line 11-12). Now I understant that because the number we can't pair(i.e.a[i]^1 is not in the set) must used to be either l or r(when l%2!=0&&r%2!=1). So that we can initialize ans so.

Another thing, there may a typo in your solution: in Line 12-"similarly, if r = 2*i+1", "2*i+1" should be revice to "2*i"?

thanks, you save my day!

You said what I want to say.

Oh, I understand. How stupid I am!

I think maybe it's a normal method to deal with the absolute value.

We can transform from 2d Manhattan distance metric to Chebyshev distance by transforming all the points $$$(x, y)$$$ to $$$(x+y, x-y)$$$. I think its relatively well known

Consider all points at distance at most $$$k$$$. Actually, this points form a diamond shape. It's hard to work with diamond, so we can rotate the plane by 45 degrees ($$$(x,y)$$$ -> $$$(x+y,x-y)$$$), and now all points at distance at most $$$k$$$ form a square shape. So after this we have a different function for distance: $$$|x_1-x_2| + |y_1-y_2|$$$ -> $$$max(|x_1'-x_2'|, |y_1'-y_2'|$$$, where $$$x' = x+y$$$ and $$$y' = x-y$$$.

How it can be used in this problem? After the transformation we need to know is there any winning points outside the rectangle (it's the same as: are all winning points inside the rectangle). This problem can be easily solved with 2D BIT, for example (but there are simpler solutions, as mentioned in the editorial).

Think about xor-ing 1 to 3,4,5,6

The contest is great , but the editorial is not so good .

In feedback I mean.

Sorry but what is conclusion problems?

Have you known the answer now, I have the same question.

Let me check for this

In test 156 I generated only testcases that give $$$k = 2$$$ as answer

You can try this testcase I just manually make

Actually, when $$$m = \frac{n}{2}$$$ and $$$b, w$$$ are even then your guess is correct and provable.

Let $$$D[x] = $$$ (number of '1' in $$$s[x \dots x + m - 1]$$$)

If $$$D[x] = m$$$ then we are done

Otherwise WLOG $$$D[x] < m < D[x + m]$$$

Since $$$|D[x + 1] - D[x]| \leq 1$$$ then applying IVT you can prove there is $$$y$$$ in $$$[x + 1, x + m - 1]$$$ that $$$D[y] = m$$$

There is another solution without using IVT and an overkill solution for an even more generalized F problem, if you are interested then I will make a blog about it.

after taking an hour of reading the codes, seeming there are 3 guys make that same wrong guess, but I dont know how to prove for $$$m < \frac{n}{2}$$$ can make $$$k = 2$$$ test using math. I will try to brute-forces for some small cases then..

Thank you. Also, if you find this problem interested you enough, do you wanna try its generalized problem for $$$k$$$ colors and $$$n = 2 \cdot k$$$ ?