在约束条件下的存在性（面试街-----------------------操纵数

Question

我正在努力解决这个问题。https:/www.interviewstreet.comchallengesdashboard#problem4f9a33ec1b8ea

假设A是一个由n个数组成的列表( A1, A2, A3, ... , An)，B( B1, B2, B3, ... ,Bn )是这些数的排列组合。如果且仅当它的以下值时，我们说B是K-可操纵的。

M(B) = min( B1 Xor B2, B2 Xor B3, B3 Xor B4, ... , Bn-1 Xor Bn, Bn Xor B1 )不小于2^K.给你n个数字A1到An，你必须找到最大的K，使这些数字存在一个K-Manipulative的排列组合B。

输入。

在输入的第一行有一个整数N.在输入的第二行有N个整数A1到An，N不超过100。Ai是非负数，并将适合32位整数。

輸出

打印一个整数到输出是测试的答案。如果没有这样的K，则打印-1到输出。

输入示例

313 3 10

采样输出

2

样品输入

41 2 3 4

采样输出

1

解释

第一个样本测试这里列表A是{13，3，10}。A的一种可能的排列方式是，B = (10, 3, 13).

对于B，min( B1 xor B2，B2 xor B3，B3 xor B1 ) = min( 10 xor 3，3 xor 13，13 xor 10 ) = min( 9，14，7 ) = 7.

所以存在A的一个排列组合B，使得M(B)不小于4即2^2。但是不存在任何A的排列组合B，使得M(B)不小于8即2^3。所以 K 的最大可能值是 2。

==================================================================================

以下是我目前所做的尝试。

---

尝试1：贪心算法

1. 将输入的内容放入数组A[1...n] 中。
2. 计算值M(A)。这给出了最小XOR值的位置(i, (i + 1) % n)
3. 检查是否将A[i]或A[(i + 1) % n]与数组中的任何其他元素交换，会增加M(A)的值。如果存在这样的元素，进行交换。
4. 重复步骤2 &3，直到不能提高M(A)的值。

这肯定会给出一个局部最大值，但我不确定这是否能给出全局最大值。

---

尝试2。检查是否存在给定邻域约束的换元法.

1. 给定输入A[1...n]，对于i = 1...n，j = (i+1)...n，计算x_ij = A[i] XOR A[j] 。
2. 计算max(x_ij)。请注意，对于一些p，2^p <= max(x_ij) <2^(p+1)。
3. 收集所有x_ij，使x_ij >=2^p。注意，这个集合可以看作是一个图G，其节点为{1，2，......n}，如果x_ij >= 2^p，则节点i和j之间有一条不定向边。
4. 检查图G是否存在一个周期，该周期正好访问每个节点一次。如果存在这样的循环，则k = p. 否则，让p = p - 1，进入第三步。

这给出了正确的答案，但是请注意，在第4步中，我们本质上是在检查一个图是否有一个哈米尔顿循环，这是一个非常困难的问题。

---

有什么提示或建议吗？

Answer 1

不用深入研究图论，就可以解决这个问题。

关键推理

建议的财产 rich，是解决这个问题的关键。

根据我的评论： B1 Xor B2 < 2^K 如果且仅当B1和B2在K个低阶位以外的所有位子上都一致的话

根据上述性质，我们只需要找到最高的k，其中有最多的是 n/2 每一个A[i]的高阶位的出现次数。

换句话说，在这组值中 A[i] >> k，如果这些值中的每一个都最多重复使用 n/2 次，存在一个k操纵性的换元，有 all the XOR values >= (2^k).

为什么n2

假设如果你确实有超过 n/2 任何一个独特的高阶位的出现，它不可能得到一个组合B，所有的循环XOR都是非零，即至少有一个 B[i] XOR B[(i+1) % N] 所有的高阶位都变成了零，因此使 M(B) < 2^k

伪代码

k = -1
for (bit = (MAX_BITS - 1) to 0) {
    HashMap count
    for (i = 0 to N - 1) {
        higherOrderVal = A[i] >> bit
        if (higherOrderVal exists in count) {
            count[higherOrderVal] += 1
        }
        else {
            count[higherOrderVal] = 1
        }
    }

    isValid = true
    for (element in count) {
        if (element > N/2) {
            isValid = false
            break
        }
    }
    if (isValid) {
        k = bit
        break
    }
}

该方案的时间复杂度为 O(M * N) 哪儿 M 是代表用于表示数字的最大位数（32位、64位等）的常数因子，以及 N 是输入数组A的大小。

Answer 2

贯彻我的意见。B1 Xor B2 < 2^K 如果且仅当B1和B2在除K个低阶位以外的所有位子上达成一致时， 所以G具有非常特殊的结构，即是完全的多partite, 分区标签由除K个低阶位以外的所有位子组成。如果且仅当不存在多数派分区时，一个完整的多partite图是Hamiltonian。把这个事实插入到尝试2中。

Answer 3

贪婪的方法#优先级_队列

首先插入所有对xor值和连续的索引i和j ->pq.push(tuple(v[i]^v[j],i,j))现在弹出第一个maxm xor值并设置索引i和j现在再次弹出来自i或j的maxm xor值这个操作最多执行1到n然后返回第n个弹出的xor值。