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

Xor problem
Автор bassuniz, история, 6 месяцев назад, По-английски

Yesterday, I was curious about this problem Given an array

$$$ a = [a_1, a_2, \dots, a_n] $$$

Construct another array

$$$ b = [b_1, b_2, \dots, b_n] $$$

such that the value

$$$ (a_1 \oplus b_1) \oplus (a_2 \oplus b_2) \oplus \dots \oplus (a_n \oplus b_n) $$$

is maximized.

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

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

Auto comment: topic has been updated by bassuniz (previous revision, new revision, compare).

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

lets say you are having array A of length 100. so usually if we assume all elements <= 10^18 then try to construct array B like Ai xor Bi will be something like this...

from i = 0,

2^63, 2^62, ....2^1, 2^0 (for remaining i construct 0 only) so at last the answer of xor of all this elements will be maximum. because if n >= 64 then it may be having value 2^64-1 not less then that (according to number of elements).

so construct array b as... 

b[0] = 2^63  xor A[0]

b[1] = 2^62 xor A[1]
.
.
.
b[63] = 1 xor A[63]... 
then b[i] = A[i] from i > 63 onwards.

this will be giving maximum answer of expression at last.

→ Ответить