私はこの問題を解決しようとしています：https ：//www.interviewstreet.com/challenges/dashboard/#problem/4f9a33ec1b8ea
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以上です。あなたはAnにn個の数A1を与えられます、あなたはK-操作的であるこれらの数の順列Bが存在するような最大のKを見つけなければなりません。
入力：
入力の最初の行には整数Nがあります。入力の2番目の行にはN個の整数があります。A1からAnNは100以下です。Aiは負ではなく、32ビット整数に収まります。
出力：
テストの答えである出力に整数を出力します。そのようなKがない場合は、出力に-1を出力します。
サンプル入力
3 13 3 10
サンプル出力
2
サンプル入力
4 1 2 3 4
サンプル出力
1
説明
最初のサンプルテストここで、リストAは{13、3、10}です。Aの可能な順列の1つは、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。
したがって、M（B）が4、つまり2^2以上になるようなAの順列Bが存在します。ただし、M（B）が8以上、つまり2^3であるようなAの順列Bは存在しません。したがって、Kの可能な最大値は2です。
================================================== ================================
これが私がこれまでに行った試みです。
試行1：欲張りアルゴリズム
- 入力を配列A[1..n]に配置します
- 値M（A）を計算します。これにより、最小XOR値の位置がわかります（i、（i + 1）％n）
- A[i]またはA[（i + 1）％n]を配列の他の要素と交換すると、M（A）の値が増加するかどうかを確認します。そのような要素が存在する場合は、スワップを行います。
- 値M（A）が改善できなくなるまで、ステップ2と3を繰り返します。
これは確かに極大値を与えますが、これが大域的最大値を与えるかどうかはわかりません。
試行2：隣接制約が与えられた場合の順列の存在を確認する
- 入力A[1..n]が与えられた場合、i =1..nおよびj=（i + 1）.. nの場合、x_ij = A [i] XORA[j]を計算します。
- max（x_ij）を計算します。一部のpについては、2 ^ p <= max（x_ij）<2 ^（p + 1）であることに注意してください。
- x_ij> = 2^pとなるようにすべてのx_ijを収集します。このコレクションは、ノード{1、2、.. n}を持つグラフGとして扱うことができ、x_ij> = 2 ^ pの場合、ノードiとjの間に無向エッジがあることに注意してください。
- グラフGに各ノードを1回だけ訪問するサイクルがあるかどうかを確認します。そのようなサイクルが存在する場合、k=pです。それ以外の場合は、p = p-1とし、手順3に進みます。
これで正解が得られますが、ステップ4では、グラフにハミルトン閉路があるかどうかを基本的にチェックしていることに注意してください。これは非常に難しい問題です。
ヒントや提案はありますか？