algorithm - 存在约束下的排列(Interview Street - Manipulative Numbers)

Question

我正在尝试解决这个问题:https://www.interviewstreet.com/challenges/dashboard/#problem/4f9a33ec1b8ea

假设 A 是 n 个数字(A1、A2、A3、...、An)的列表，而 B(B1、B2、B3、...、Bn)是这些数字的排列。我们说 B 是 K-Manipulative 当且仅当它的值如下:

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，使得存在这些数字的排列 B，即 K-Manipulative。

输入:

在输入的第一行有一个整数N。第二行输入有N个整数A1到AnN不大于100。Ai 是非负的，适合 32 位整数。

输出:

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

示例输入

313 3 10

示例输出

2

示例输入

41 2 3 4

示例输出

1

解释

第一个 sample 测试这里的列表 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)。这给出了最小异或值的位置 (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. 计算最大值(x_ij)。请注意，对于某些 p，2^p <= max(x_ij) < 2^(p+1)。
3. 收集所有 x_ij 使得 x_ij >= 2^p。请注意，如果 x_ij >= 2^p，则此集合可以被视为具有节点 {1, 2, .. n} 且节点 i 和 j 之间具有无向边的图 G。
4. 检查图 G 是否有一个循环访问每个节点恰好一次。如果存在这样的循环，则 k = p。否则，令 p = p - 1，转到步骤 3。

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

---

有什么提示或建议吗？

Answer 1

无需深入研究图论就可以解决这个问题。

关键推断

rich 建议的属性，是解决这个问题的关键:

Following up on my comment: B1 Xor B2 < 2^K if and only if B1 and B2 agree on all but the K low order bits

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

换句话说，在一组值中 A[i] >> k , 当且仅当这些值中的每一个最多重复 n/2次，存在一个 k-操纵排列 all the XOR values >= (2^k) .

为什么是 n/2

假设你有超过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的大小。