Блог пользователя Red_Before_GTA6

Автор Red_Before_GTA6, история, 2 года назад, По-английски

Did you know that the minimum XOR pair of an array can be found by sorting the array, then checking the XOR of adjacent elements.

Can anyone prove why?

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +8 Проголосовать: не нравится

Consider a greedy algorithm on a 0-1 Trie.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится
»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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!

»
2 года назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

does anyone has list of problems like this where you can learn new XOR properties , such as state above.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

https://atcoder.jp/contests/abc308/tasks/abc308_g

you can go through the editorial of this problem

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I've understood it from the above comments now. Cheers

»
2 года назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

Similar approach can be applied to find a maximal AND pair.

»
2 года назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

Given some set of non-negative integers $$$S$$$, we want to show the following:

$$$a \oplus b = \min_{x, y \in S} x \oplus y \implies \not \exists c \in S, \text{such that } a \lt c \lt b$$$

We strive for a contradiction. Suppose there does exist such a $c \in S$. Let $$$i$$$ be the first (leftmost) index such that $$$c_i = 0$$$ and $$$b_i = 1$$$, where $$$x_i$$$ represents the $$$i$$$-the digit from the left in the binary representation of $$$x$$$. Now if $$$a_i = 0$$$, then $$$a \oplus c \lt a \oplus b$$$. If $$$a_i = 1$$$, then there must exist some $$$j \lt i$$$ such that $$$b_j = 1$$$ and $$$a_j = 0$$$ (since $$$a \lt c \lt b$$$). Here, $$$a_j \oplus b_j = 1$$$ but $$$b_j = c_j \implies b_j \oplus c_j = 0$$$. Thus $$$b \oplus c \lt a \oplus b$$$. In both cases, we have arrived at a contradiction. $$$\square$$$