在限制条件下存在一个排列的问题（面试街 - 操作性数字）

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到An

N不超过100。

Ai为非负数，并适合32位整数。

输出：

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

示例输入

3 13 3 10

示例输出

2

示例输入

4 1 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）。请注意，2 ^ p <= max（x_ij）<2 ^（p + 1）对于某些p。
3. 收集所有x_ij，使得x_ij> = 2 ^ p。请注意，此集合可以视为具有节点{1,2，..n}的图G，并且节点i和j之间具有无向边，如果x_ij> = 2 ^ p，则存在。
4. 检查图G是否具有访问每个节点恰好一次的循环。如果存在这样的循环，则k = p。否则，让p = p-1，转到步骤3。

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

---

有任何提示或建议吗？

- user1154735

---

贪心算法如原文所述并不能正常运作。考虑A = [2, 2, 4, 4, 2, 2, 4, 4]，没有任何单次交换会改变M(A) = 0，但是当然用B = [2, 4, 2, 4, 2, 4, 2, 4]，你有M(B) = 6且B是2-manipulative的。如果您将条件更改为增加所涉及项目的XOR的最小值(或者实际上是XOR的最高设置位的最小值，假装0具有设置为“-1”的位)，则它可能有效，但我不太确定。 - Daniel Fischer

同意，我提到贪心算法是一种解决方案的尝试。感谢您提供一个示例，表明它不起作用。 - user1154735

当且仅当B1和B2在除了K个低位之外的所有位上达成一致时，B1 Xor B2 < 2^K，因此G具有非常特殊的完全多部分结构。 - rich

Answer 1

不需要深入研究图论，也可以解决这个问题。

关键推论

rich 提出的特性是解决这个问题的关键：

根据我的评论：当且仅当 B1 和 B2 在除了 K 个低位以外的所有位上都相同时，B1 Xor B2 < 2^K。

基于上述特性，我们只需要找到最高的 k，对于每个 A[i] 的每个唯一高位比特位，最多有 n/2 次出现。

换句话说，在值组 A[i] >> k 中，如果每个值最多重复 n/2 次，则存在一个 k-操纵排列，所有 XOR 值 >= (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的大小。

- Tuxdude

---

你的代码有一个小错误：if (element > N/2) 需要替换为 if (element > N/2-1) 才能通过所有测试用例。 - Arsenius

Answer 2

回复我的评论：当且仅当B1和B2在除了K个低位之外的所有位上达成一致时，B1 Xor B2 < 2^K，因此G具有非常特殊的结构，即完全多部分图，其分区标签由除了K个低位之外的所有位组成。如果没有大多数分区，则完全多部分图是哈密顿图。将这个事实代入尝试2中。

- rich

---

你能再澄清一下吗？请注意，当p>0时，G可能不是完全图。当Attempt 2的第3步首次运行时，G可能没有(n \ choose 2)条边。 - user1154735

你能解释一下G的部分集会是什么吗？ - user1154735

每个数字x都属于分区(x >>> k)，其中k是我们正在测试可行性的当前K值。 - rich

这个问题要求证明完备的 k-部分图具有哈密顿回路，当且仅当不存在大多数划分。有了这个事实，这个问题现在可以相当容易地解决。我惊讶于解决这个问题需要像这样的事实。 - user1154735

Answer 3

贪心算法 #优先队列

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

- Rahul Kumar