约束条件下排列的存在性(访谈街头操纵数)

I am trying to solve this problem: https://www.interviewstreet.com/challenges/dashboard/#problem/4f9a33ec1b8ea

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

Suppose that A is a list of n numbers ( A1, A2, A3, ... , An) and B ( B1, B2, B3, .. ,Bn ) is a permutation of these numbers. We say B is K-Manipulative if and only if its following value:

假设A是一个n个数的列表(A1 A2 A3…)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 ) is not less than 2^K. You are given n number A1 to An, You have to find the biggest K such that there exists a permutation B of these numbers which is 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-操控性的。

Input:

输入:

In the first line of the input there is an integer N. In the second line of input there are N integers A1 to An N is not more than 100. Ai is non-negative and will fit in 32-bit integer.

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

Output:

输出:

Print an integer to the output being the answer to the test. If there is no such K print -1 to the output.

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

Sample Input

样例输入

3 13 3 10

3 13 3 10

Sample Output

样例输出

2

2

Sample Input

样例输入

4 1 2 3 4

4 1 2 3 4。

Sample Output

样例输出

1

1

Explanation

解释

First Sample test Here the list A is {13, 3, 10}. One possible permutation of A is, B = (10, 3, 13).

这里的第一个示例测试列表A是{13,3,10}。A可能的排列是，B = (10,3,13)

For 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.

对于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。

So there exist a permutation B of A such that M(B) is not less than 4 i.e 2^2. However there does not exist any permutation B of A such that M(B) is not less than 8 ie 2^3. So the maximum possible value of K is 2.

所以存在a的排列B使得M(B)不小于4i。e 2 ^ 2。然而,不存在任何这样的排列B M(B)不小于8(2 ^ 3。K的最大值是2。

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

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

Here are the attempts I have made so far.

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

---

Attempt 1: Greedy Algorithm

尝试1:贪婪算法

1. Place the input in an array A[1..n]
2. 将输入放入数组A[1..n]
3. Compute the value M(A). This gives the location of the min XOR value (i, (i + 1) % n)
4. 计算值M(A)。这给出了最小XOR值(i， (i + 1) % n)的位置
5. Check whether swapping A[i] or A[(i + 1) % n] with any other element of the array increases the value of M(A). If such an element exists, make the swap.
6. 检查交换A[i]或A[(i + 1) % n]与数组中的任何其他元素是否会增加M(A)的值。如果存在这样的元素，进行交换。
7. Repeat steps 2 & 3 until the value M(A) cannot be improved.
8. 重复步骤2和步骤3直到值M(A)不能被改进。

This gives a local maxima for sure, but I am not sure whether this gives the global maxima.

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

---

Attempt 2: Checking for the existence of a permutation given neighbor constraints

尝试2:检查给定邻居约束的置换是否存在

1. Given input A[1..n], For i = 1..n and j = (i+1)..n compute x_ij = A[i] XOR A[j]
2. 给定的输入(1 . .n]， i = 1。n和j = (i+1)n计算x_ij = A[i] XOR A[j]
3. Compute the max(x_ij). Note that 2^p <= max(x_ij) < 2^(p+1) for some p.
4. 计算最大(x_ij)。请注意,2 ^ p < = max(x_ij)< 2 ^(p + 1)p。
5. Collect all x_ij such that x_ij >= 2^p. Note that this collection can be treated as a graph G with nodes {1, 2, .. n} and nodes i and j have an undirected edge between them if x_ij >= 2^p.
6. 收集所有x_ij x_ij > = 2 ^ p。注意，该集合可以被视为节点{1,2，..n }和节点i和j它们之间有一个无向边如果x_ij > = 2 ^ p。
7. Check whether the graph G has a cycle which visits each node exactly once. If such a cycle exists, k = p. Otherwise, let p = p - 1, goto step 3.
8. 检查图G是否有一个循环，该循环访问每个节点一次。如果存在这样一个循环，则k = p。否则，让p = p - 1，然后执行步骤3。

This gives the correct answer, but note that in step 4 we are essentially checking whether a graph has a hamiltonian cycle which is a very hard problem.

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

---

Any hints or suggestions?

任何提示或建议吗?

2 个解决方案

#1

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, so G has the very special structure of being complete multipartite, with partition labels consisting of all but the K low order bits. A complete multipartite graph is Hamiltonian if and only if there is no majority partition. Plug this fact into Attempt 2.

跟进我的评论:B1 Xor B2 < 2 ^ K当且仅当B1和B2同意所有但K低阶位,G的非常特殊的结构是完整的多国参加的,与分区标签组成的K低阶位。一个完整的多部分图是哈密顿图，当且仅当没有多数分割时。把这个事实代入尝试2。

#2

It is possible to solve this problem without going deep into graph theory.

不深入研究图论就能解决这个问题。

Key inference

The property suggested by rich, is the key to solving this problem:

富人提出的财产，是解决这一问题的关键:

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

跟进我的评论:B1 Xor B2 < 2 ^ K当且仅当B1和B2同意K低阶位

Based on the above property, we only need to find the highest k for which there are at most n/2 occurrences of each unique higher order bits for every A[i].

基于上面的属性，我们只需要找到最高的k，对于每个A[i]，最多有n/2个唯一的高阶位。

In other words, amongst the group of values A[i] >> k, iff each of those values is repeated at most n/2 times, there exists a k-manipulative permutation with all the XOR values >= (2^k).

换句话说,在集团的价值观[我]> > k,敌我识别每一个值最多重复n / 2次,存在一个k-manipulative排列所有XOR值> =(2 ^ k)。

Why n/2

Suppose if you do have more than n/2 occurrences of any of the unique higher order bits, it is NOT possible to obtain a permutation B, with all the cyclic XORs being non-zero, i.e. there will be at least one B[i] XOR B[(i+1) % N] with all the higher order bits becoming zero, hence making M(B) < 2^k

假设如果你有超过n / 2出现的任何独特的高阶位,不可能获得一个排列B,所有非零循环XOR,即会有至少有一个B[我]XOR B[(i + 1)% n]所有的高阶位减为零,因此使M(B)< 2 ^ k

Pseudocode

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
    }
}

The time complexity for this solution is O(M * N) where M is the constant factor representing the maximum number of bits used to represent the numbers (32-bits, 64-bits, etc.), and N is the size of the input array A.

该解决方案的时间复杂度为O(M * N)，其中M是表示用于表示数字(32位、64位等)的最大比特数的常数因子，N是输入数组A的大小。