Let's look at all possible pairs of elements in the array. The minimum XOR is achieved in one of those pairs where the length of the common prefix in the bit representation is the longest. This is because it corresponds to the maximum prefix of zeros at the beginning of the XOR. Hence, the minimum XOR is achieved in one of such pairs. Now, notice that for any such pair, it is true that its elements are consecutive in the sorted array because the elements have the form $$$prefix0 \dots$$$ and $$$prefix1 \dots$$$ If there were at least one more element $$$a_i$$$ between them, the common prefix of $$$a_i$$$ with one of the elements of the pair would be greater than the prefix of the pair. $$$(a_i = prefix0\dots\ or\ prefix1\dots)$$$ But we initially considered pairs with the longest matching bit prefix. Contradiction!

Amazing E problem, thank you BledDest !

Stefan2417, problem E editorial is incorrect.

Let $$$n = 3$$$ and only one edge $$$1 \leftarrow 2$$$. According to the text solution $$$1$$$ will be white and $$$2$$$ will be black (or vice versa). Then the red stack is empty, but no vertexes are reachable from the 3rd. You said such a situation is impossible, but here it is.

well-balanced div3 round, GL for all participants 🏆

I encountered the exact same question and here's the solution I came up with.

We're only interested in the last case, when there is an inequality $$$x \lt a[i] \le y$$$. We know that with the current arrays $$$A$$$ and $$$B$$$, we can complement them in such a way as to achieve the optimal solution. Let this optimal solution be achievable if we add $$$a[i]$$$ after $$$x$$$, not $$$y$$$. Let's demonstrate that we can obtain a solution no worse by adding $$$a[i]$$$ after $$$y$$$.

For better understanding, the optimal solution looks like: $$$[\ldots,\ y,\ \ldots],\ [\ldots,\ x,\ a[i],\ \ldots]$$$.

First, try adding all numbers from $$$a[i + 1]$$$ to $$$a[n]$$$ into the same arrays (as in the editorial). The penalty will differ only by the penalty between $$$y$$$ and the next number added after $$$y$$$ (if it exists) and by the penalty between $$$a[i]$$$ and the next number added after $$$a[i]$$$ (if it exists). Because all other numbers go exactly in the same order in the same arrays.

Let's denote the number after $$$y$$$ as $$$next_y$$$ and the number after $$$a[i]$$$ as $$$next_{a[i]}$$$ in optimal solution. Thus, the penalty may differ from the optimal by no more than 1 and only in the case if $$$y \ge next_y$$$ and $$$a[i] \ge next_{a[i]}$$$, but $$$a[i] \lt next_y$$$ and $$$x \lt next_{a[i]}$$$. Because optimal solution has $$$1$$$ extra penalty from $$$x \lt a[i]$$$.

For better understanding, the optimal solution looks like: $$$[\ldots,\ y,\ next_y,\ \ldots],\ [\ldots,\ x,\ a[i],\ next_{a[i]},\ \ldots]$$$, our solution looks like: $$$[\ldots,\ y,\ a[i],\ next_y,\ \ldots],\ [\ldots,\ x,\ next_{a[i]},\ \ldots]$$$.

Such a situation can indeed occur: it's exactly what was described by flakes24. So if we try to use the method described above, our arrays will look like this: $$$[\ldots,\ y,\ a[i],\ next_y,\ \ldots],\ [\ldots,\ x,\ next_{a[i]},\ \ldots]$$$. Inequalities arise: $$$a[i] \lt next_y$$$ and $$$x \lt next_{a[i]}$$$.

In this case, we'll swap the suffixes of the arrays $$$A$$$ and $$$B$$$, without changing the relative order of the numbers from $$$a[i + 1]$$$ to $$$a[n]$$$. Since $$$a[i] \ge next_{a[i]}$$$, we will achieve no more than $$$1$$$ penalty (maybe $$$x \lt next_y$$$) in our solution. Optimal solution has at least $$$1$$$ penalty ($$$x \lt a[i]$$$), so our solution is no worse.

problems links are incorrect for example https://codeforc.es/contest/1956/problem/E2, dot between codeforc, es

D accepted solution in $$$\mathcal{O}(n^2k)$$$ in C++20 254217379

Endagorion, big thanks to you for enchanting problemset!

ty very much

look at E/C first solver's handles

Can anyone explain how to solve E?

I have ML without it

I need $$$[650][2 \cdot 10^5]$$$ array of $$$32$$$-bit integeres. This is $$$4$$$ byte $$$\cdot 650 \cdot 2 \cdot 10^5 = 520000000$$$ byte = $$$520$$$ MB.

Really dissapointed by B problem (Div. 1). There is 4 sec TL, and my $$$\mathcal{O}(n\sqrt{n})$$$ solution with hashmap doesn't pass. I tried to optimize it many times, using fast hashmaps, different pragmas and other methods.

Judging by standings I can conclude that I'm not the only one with this problem. But some people have achieved +5/+10/+20, others not.

TL 4 sec implies that $$$2 \cdot 10^5 \cdot 650 \cdot [hashmap time] = 1.3 \cdot 10^8 \cdot [hashmap time]$$$ will pass!

If author's solution has another complexity TL must be 1sec. If author's solution is just 2 times faster for example you can't ban people with $$$\mathcal{O}(n\sqrt{n})$$$ solution — this is not Codeforces politics.

So, AB were good tasks, C was interesting too, but I just waste all time to speed up B, it was terrible round.

Agree with you, Div. 1 B1 was as hard as usual B. But you just get /2 points.

Come on, why we still have rounds like this on Codeforces? Last round by Igor_Parfenov was with 5 math tasks. There we have ABC Div. 1 about subsegments. Seriously, maybe stop doing rounds with 1 task pattern?

Problem Div1A can be solved another way. Let’s think how the subsequence is organized. It can be created greedy: let the last included integer be a[i]. 1) if a[i+1] > a[i], so the next subsequence’s number will be a[i+1]. 2) else we need to find the first j such that a[j] < a[j+1], and the next subsequence’s numbers will be a[j] and a[j+1]. This observation can be used to calculate next[i]. So the answer is built by jumping from l to next[l], next[next[l]]… while <= r. To answer queries fast we can just count binary jumps on next[] array.

Thank you for 5 math tasks and constructive D