5

1..N の番号が付けられた N 個の問題があり、それらを完了する必要があります。問題を難易度の高い順に並べ、i 番目の問題の推定難易度は i です。また、各問題に評価 vi を割り当てました。同様の vi 値を持つ問題は、本質的に似ています。毎日、問題のサブセットを選択して解決します。その日に解決する後続の問題は、その日に解決した前の問題よりも難しくする必要があると判断しました。また、退屈にならないように、連続して解く問題は vi 評価が少なくとも K 異なる必要があります。すべての問題を解くことができる最短の日数は?

入力: 最初の行にはテスト ケースの数 T が含まれます。T 個のテスト ケースが続きます。各ケースには、1 行目に整数 N と K が含まれ、2 行目に整数 v1,...,vn が続きます。

出力: すべての問題を解決できる最小日数を含む、テスト ケースごとに 1 行の T 行を出力します。

制約:
1 <= T <= 100
1 <= N <= 300
1 <= vi <= 1000
1 <= K <= 1000

サンプル入力:
2
3 2
5 4 7
5 1
5 3 4 5 6

サンプル出力:
2
1

これはinterviewstreetからの挑戦の1つです。
以下は私のアプローチです。
最初の質問から始めて、解決できる質問の最大数を見つけて、これらの質問を質問リストから削除します。残りのリストの最初の要素から再度開始し、質問リストのサイズが0になるまでこれを行います. このメソッドから間違った答えが得られるので、この課題を解決するためのアルゴリズムを探しています。

4

4 に答える 4

17

次の方法で問題のDAGを構築します。p iとp jを 2 つの異なる問題とする。次に、 p jが同じ日に連続してp iの直後に解決できる場合にのみ、p iからp jへの有向辺を描画します。つまり、次の条件を満たす必要があります。

  1. i < j、難易度の低い問題を早く解決する必要があるためです。
  2. | | v i - v j | >= K (評価要件)。

ここで、ある日に解決するために選択された問題の各サブセットが、その DAGの有向パスに対応していることに注意してください。最初の問題を選択し、エッジを段階的にたどります。パスの各エッジは、同じ日に連続して解決された問題のペアに対応しています。また、各問題は 1 回しか解決できないため、DAG 内のノードは 1 つのパスにのみ表示される可能性があります。そして、すべての問題を解決する必要があるため、これらのパスはすべての DAG をカバーする必要があります。

ここで、次の問題があります。n 個のノードの DAG が与えられた場合、この DAG を完全にカバーする交差しない有向パスの最小数を見つけます。これはパス カバーと呼ばれるよく知られた問題です。一般的に言えば、それは NP 困難です。ただし、有向グラフは非循環であり、非循環グラフの場合、マッチング問題への還元を使用して多項式時間で解くことができます。次に、最大マッチング問題は、 Hopcroft-Karp アルゴリズムなどを使用して解決できます。正確な削減方法は簡単で、Wikipediaなどで読むことができます。元の DAG の有向辺(u, v)ごとに、無向辺(a u ,ここで、{a i }と{ bi }はサイズ n の 2 つの部分です。

結果の 2 部グラフの各部分のノード数は、元の DAG のノード数nと等しくなります。Hopcroft-Karp アルゴリズムは、最悪の場合O(n 2.5 )で実行され、300 2.5 ≈ 1 558 845で実行されることがわかっています。100 回のテストの場合、このアルゴリズムは合計で 1 秒未満かかるはずです。

于 2012-04-24T18:53:56.817 に答える
2

アルゴリズムは単純です。まず、問題を で並べ替えv_i、次に各問題について、区間 内の問題の数を見つけます(v_i-K, v_i]。これらの数値の最大値が結果です。2 番目のフェーズは で実行できるO(n)ため、最もコストのかかる操作は並べ替えであり、アルゴリズム全体が になりますO(n log n)。スプレッドシート内のデータと K=35 に対するアルゴリズムの動作のデモンストレーションについては、こちらをご覧ください。

なぜこれが機能するのか

この問題をグラフの彩色の問題に再定式化しましょう。グラフ G を次のように作成します。頂点が問題になり、2 つの問題 iff の間にエッジが存在します |v_i - v_j| < K。

このようなグラフでは、独立したセットは、同じ日に実行可能な問題のセットに正確に対応しています。(<=) セットが1日で出来れば、きっと独立セットです。(=>) セットに K 差基準を満たさない 2 つの問題が含まれていない場合は、難易度に従って並べ替えて、この順序で解決できます。このように両方の条件が満たされます。

したがって、グラフ G の色付けは、各色が 1 日に対応する、異なる日の問題のスケジュールに正確に対応することが容易にわかります。

それで、グラフGの色度を見つけたいと思います。これは、グラフが間隔グラフであり、完全なグラフであり、それらの色度がクリークネスに等しく、両方が単純なアルゴリズムで見つけることができることを認識すると簡単になります。

区間グラフは実線上の区間のグラフで、エッジは交差する区間の間にあります。私たちのグラフは、簡単にわかるように、区間グラフです (問題ごとに interval を割り当てます(v_i-K, v_i]。この区間グラフのエッジが、まさにグラフのエッジであることは容易にわかります)。

補題 1 : 区間グラフには、近傍がクリークを形成する頂点が存在する。

証明は簡単です。すべての中で最も低い上限 (または最も高い下限) を持つ間隔を取るだけです。それと交差する任意の区間の上限はより高いため、最初の区間の上限はそれらすべての交点に含まれます。したがって、それらは互いに交差し、クリークを形成します。した

補題 2 : 誘導されたサブグラフで閉じられ、補題 1 (隣接する頂点がクリークを形成する頂点の存在) のプロパティを持つグラフのファミリでは、次のアルゴリズムは最小限の色付けを生成します。

  1. 近傍がクリークを形成する頂点xを見つけます。
  2. グラフからxを削除し、サブグラフ G' を作成します。
  3. G' を再帰的に色付けする
  4. 隣に見つからない最小の色で x に色を付ける

証明: (3) では、アルゴリズムは帰納仮説 + 帰納された部分グラフでの私たちの家族の近さによって、部分グラフ G' の最適な色付けを生成します。(4) では、 xの近傍にnサイズのクリークがある場合にのみ、アルゴリズムは新しい色を選択します。つまり、xの場合、G にはサイズのクリークがあるため、その色度は少なくとも でなければなりません。したがって、アルゴリズムによって頂点に与えられる色は常にです。これは、色付けが最適であることを意味します。(明らかに、アルゴリズムは有効な色を生成します)。したn-1nn<= chromaticity(G)

当然の結果 : 区間グラフは完全です (完全 <=> 色度 == クリークネス)

したがって、Gのクリークネスを見つける必要があります。これは、区間グラフにとって簡単です。区間境界を含まない実線のセグメントを処理し、そこで交差する区間の数を数えるだけです。これは、あなたの場合はさらに簡単です。区間の長さは均一です。これは、この投稿の冒頭で概説したアルゴリズムにつながります。

于 2012-05-09T00:05:46.583 に答える
0

本当にパスカバーに行く必要がありますか? LISと同様の戦略をたどることはできませんか。

入力は、複雑さの昇順です。毎日実行されるタスクのために、たくさんのキューを維持する必要があります。すべてのキューの最後の要素を比較することにより、入力のすべての要素が日に割り当てられます。「k」の違いが見つかった場合は常に、タスクをそのリストに追加します。

例: 5 3 4 5 6

1) 入力 -> 5 (空のリストなので新しいリストを開始)

5

2) 3 (リスト 5 & abs(5-3) のみが 2 (k) なので 3 を追加)

5--> 3

3) 4 (最後の vi、3 および abs(3-4) < k のリストのみ、新しいリストを開始)

5--> 3

4

4) 再び 5 (abs(3-5)=k 追加)

5-->3-->5

4

5) 再び 6 (abs(5-6) < k but abs(4-6) = k) 2 番目のリストに追加)

5-->3-->5

4-->6

各リストの最後の要素を持つ配列を維持する必要があるだけです。日の順序 (いつタスクを実行するかは重要ではありません) から、最後のタスクのソートされたリストを維持できるため、新しいタスクを挿入する場所を検索するには、実行できる abs(vi-k) の値を探すだけです。二分探索を介して。

複雑：

ループは N 要素に対して実行されます。最悪の場合、多数の入力 [i] に対して二分探索 (log i) を使用して ceil 値を照会することになる可能性があります。

したがって、T(n) < O( log N! ) = O(N log N) です。上限と下限も O( N log N ) であることを確認するために分析します。複雑さは THETA (N log N) です。

于 2012-11-22T13:56:20.847 に答える
0

必要な最小日数は、G (DAG) の相補 (無向) グラフの最長パスの長さと同じになります。これは、ディルワースの定理を使用して解決できます。

于 2015-12-01T18:05:17.100 に答える