algorithm - 嘘つきのパズル

Question

Interviewstreetでパズルを解こうとしています。しかし、今のところ問題の手がかりがありません。誰かが私にヒントを与えることができれば素晴らしいことです。

パズルは次のとおりです。1 から N までの番号が付けられた N 人の兵士がいます。各兵士は嘘つきか正直者のどちらかです。それらに関する M セットの情報があります。情報の形式は次のとおりです。

各行には、A、B、C の 3 つの整数が含まれます。これは、{A、A+1、A+2、...、B} と番号が付けられた兵士のセットで、正確に C 人が嘘つきであることを意味します。上記のようなM行があります。

嘘つき兵士の総数を L とします。L の正確な値を見つけることができないため、L の最小値と最大値を見つける必要があります。

入力：

入力の最初の行には、2 つの整数 N と M が含まれます。次の M 行のそれぞれには、3 つの整数 - A、B、C (1 <= Ai <= Bi <= n) および (0 <= Ci <= Bi-Ai) が含まれます。 ）。ここで、Ai、B i および C i は、それぞれ i 行目の A、B および C の値を指し、N および M は 101 以下であり、与えられた情報が満足できることが保証されています。与えられた情報を満たす状況をいつでも見つけることができます。

出力：

2 つの整数 Lmin と Lmax を出力に出力します。

サンプル入力

3 2
1 2 1
2 3 1

サンプル出力

1 2

サンプル入力

20 11
3 8 4
1 9 6
1 13 9
5 11 5
4 19 12
8 13 5
4 8 4
7 9 2
10 13 3
7 16 7
14 19 4

サンプル出力

13 14

説明

最初のサンプル テストケースでは、最初の行は「3 2」です。これは、3 人の兵士がいて、2 つの情報セットがあることを意味します。最初の情報は、兵士の集合 {1, 2} の 1 人が嘘つきであるということであり、2 番目の情報は、兵士の集合 {2,3} の 1 人が嘘つきであるということです。このシナリオには 2 つの可能性があります。1 番と 3 番の兵士が嘘つきであるか、2 番の兵士が嘘つきです。したがって、嘘つきの最小数は 1 であり、嘘つきの最大数は 2 です。したがって、答えは 1 2 です。

Answer 1

これはまた別の動的プログラミングの問題です。ヒューリスティックは必要ありません。

iから0までのそれぞれでn、現在開いているすべての条件をどれだけ満たすことができるかによって、嘘つきの最小数と最大数を追跡する必要があります。(開放条件とは、「ここからもっと嘘つきjが必要だ」という形のことです。)k

の解がある場合は、部分解ごとに次のようにi移動します。i+1

1. 到達して満たしたすべての条件をドロップします。
2. この番号のすべての新しい条件を追加します。新しい条件が既存のソリューションと競合する場合は、この部分的なソリューションを破棄してください。jby you need kliar と by j'you need k'liar withという条件の間の競合のルールは次のj <= j'とおりです。
   1. k < k'競合がある場合。j（嘘つきを増やしてから減らすことはできませんj'。
   2. j' - j < k' - k競合がある場合。(兵士にk' - k嘘つきを追加することはできません。)j' - j
   3. そうでなければ、競合はありません。
3. j兵士によって嘘つきを追加する必要があるという条件がない場合はj-i、現在のステップに、現在の兵士が嘘つきではない部分的な解決策を追加できます。(ここでの「追加」とは、「この状態が追跡されていることを確認し、追跡されていない場合は必要に応じて最大/最小を更新する」ことを意味します。)
4. 0将来の時点で兵士を追加するという条件がない場合は、現在のステップに、現在の兵士が嘘つきである部分的な解決策を追加できます。(このソリューションでは、最初に状態を変更して、すべての条件で嘘つきを 1 つ減らす必要があることを伝えます。これは、嘘つきを 1 つ追加したためです。その後、前と同じように続行します。)

あなたの開始条件は、嘘つきで解決策i = 0があり、条件がまったくないことです。10

の解から、、、 ... 、0の部分解の生成を開始します。そしてあなたがたどり着いたとき、あなたはあなたの答えを持っています。12nn

(注: 適度な変更を加えることで、最大値と最小値だけでなく、解が正確にいくつあるかを把握できます。)

Answer 2

これらの原則を使用して、90% の方法を取得できます。

1. セット内の嘘つきの数がゼロに等しい場合、そのセットをサイズ 1 のセットに分解し、それぞれの嘘つきの数がゼロに等しいようにします。そしてと になり1 3 0ます。1 1 02 2 03 3 0

2. セット内の嘘つきの数がセットのサイズと等しい場合、そのセットをサイズ 1 のセットに分解し、それぞれの嘘つきの数は 1 に等しい。そしてとと になり2 5 4ます。2 2 13 3 14 4 15 5 1

3. 任意の 2 つのセット A と B について、A が B の部分集合である場合、B から A のすべての要素を削除し、B の嘘つきの数から A の嘘つきの数を引きます。

これらの原則を使用して、2 つのサンプル問題の長い方を解決します。与えられた入力を取得し、それらを一連のインデックスに変換することから始めます。

    3 4 5 6 7 8                                         [4]
1 2 3 4 5 6 7 8 9                                       [6]
1 2 3 4 5 6 7 8 9 10 11 12 13                           [9]
        5 6 7 8 9 10 11                                 [5]
      4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19         [12]
              8 9 10 11 12 13                           [5]
      4 5 6 7 8                                         [4]
            7 8 9                                       [2]
                  10 11 12 13                           [3]
            7 8 9 10 11 12 13 14 15 16                  [7]
                              14 15 16 17 18 19         [4]

4 5 6 7 8は のサブセットな3 4 5 6 7 8ので、一方を他方から引きます。

    3                                                   [1]
1 2 3 4 5 6 7 8 9                                       [6]
1 2 3 4 5 6 7 8 9 10 11 12 13                           [9]
        5 6 7 8 9 10 11                                 [5]
      4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19         [12]
              8 9 10 11 12 13                           [5]
      4 5 6 7 8                                         [4]
            7 8 9                                       [2]
                  10 11 12 13                           [3]
            7 8 9 10 11 12 13 14 15 16                  [7]
                              14 15 16 17 18 19         [4]

7 8 9、10 11 12 13、および14 15 16 17 18 19はすべて のサブセットな4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19ので、それらを減算します。

    3                                                   [1]
1 2 3 4 5 6 7 8 9                                       [6]
1 2 3 4 5 6 7 8 9 10 11 12 13                           [9]
        5 6 7 8 9 10 11                                 [5]
      4 5 6                                             [3]
              8 9 10 11 12 13                           [5]
      4 5 6 7 8                                         [4]
            7 8 9                                       [2]
                  10 11 12 13                           [3]
            7 8 9 10 11 12 13 14 15 16                  [7]
                              14 15 16 17 18 19         [4]

4 5 6には嘘つきが 3 人いるので、それらを個別のセットに分解します。

    3                                                   [1]
      4                                                 [1]
        5                                               [1]
          6                                             [1]
1 2 3 4 5 6 7 8 9                                       [6]
1 2 3 4 5 6 7 8 9 10 11 12 13                           [9]
        5 6 7 8 9 10 11                                 [5]
              8 9 10 11 12 13                           [5]
      4 5 6 7 8                                         [4]
            7 8 9                                       [2]
                  10 11 12 13                           [3]
            7 8 9 10 11 12 13 14 15 16                  [7]
                              14 15 16 17 18 19         [4]

それらを含むすべてのセットから 3、4、5、および 6 を減算します。

    3                                                   [1]
      4                                                 [1]
        5                                               [1]
          6                                             [1]
1 2         7 8 9                                       [2]
1 2         7 8 9 10 11 12 13                           [5]
            7 8 9 10 11                                 [3]
              8 9 10 11 12 13                           [5]
            7 8                                         [1]
            7 8 9                                       [2]
                  10 11 12 13                           [3]
            7 8 9 10 11 12 13 14 15 16                  [7]
                              14 15 16 17 18 19         [4]

7 8から引く7 8 9

    3                                                   [1]
      4                                                 [1]
        5                                               [1]
          6                                             [1]
                9                                       [1]
1 2         7 8 9                                       [2]
1 2         7 8 9 10 11 12 13                           [5]
            7 8 9 10 11                                 [3]
              8 9 10 11 12 13                           [5]
            7 8                                         [1]
                  10 11 12 13                           [3]
            7 8 9 10 11 12 13 14 15 16                  [7]
                              14 15 16 17 18 19         [4]

それを含むすべてのセットから 9 を引きます。

    3                                                   [1]
      4                                                 [1]
        5                                               [1]
          6                                             [1]
                9                                       [1]
1 2         7 8                                         [1]
1 2         7 8   10 11 12 13                           [4]
            7 8   10 11                                 [2]
              8   10 11 12 13                           [4]
            7 8                                         [1]
                  10 11 12 13                           [3]
            7 8   10 11 12 13 14 15 16                  [6]
                              14 15 16 17 18 19         [4]

7 8両方を含むセットから減算します。

    3                                                   [1]
      4                                                 [1]
        5                                               [1]
          6                                             [1]
                9                                       [1]
1 2                                                     [0]
1 2               10 11 12 13                           [3]
                  10 11                                 [1]
              8   10 11 12 13                           [4]
            7 8                                         [1]
                  10 11 12 13                           [3]
                  10 11 12 13 14 15 16                  [5]
                              14 15 16 17 18 19         [4]

1 2嘘つきは 0 人なので、それらを個々のセットに分解します。

1                                                       [0]
  2                                                     [0]
    3                                                   [1]
      4                                                 [1]
        5                                               [1]
          6                                             [1]
                9                                       [1]
1 2               10 11 12 13                           [3]
                  10 11                                 [1]
              8   10 11 12 13                           [4]
            7 8                                         [1]
                  10 11 12 13                           [3]
                  10 11 12 13 14 15 16                  [5]
                              14 15 16 17 18 19         [4]

それらを含む他のすべてのセットから 1 と 2 を減算します。

1                                                       [0]
  2                                                     [0]
    3                                                   [1]
      4                                                 [1]
        5                                               [1]
          6                                             [1]
                9                                       [1]
                  10 11                                 [1]
              8   10 11 12 13                           [4]
            7 8                                         [1]
                  10 11 12 13                           [3]
                  10 11 12 13 14 15 16                  [5]
                              14 15 16 17 18 19         [4]

10 11両方を含むセットから減算します。

1                                                       [0]
  2                                                     [0]
    3                                                   [1]
      4                                                 [1]
        5                                               [1]
          6                                             [1]
                9                                       [1]
                  10 11                                 [1]
              8         12 13                           [3]
            7 8                                         [1]
                        12 13                           [2]
                        12 13 14 15 16                  [4]
                              14 15 16 17 18 19         [4]

8 12 13には 3 つの嘘つきがいるので、それらを個別のセットに分解し、それらを含む他のセットからそれらを差し引きます。

1                                                       [0]
  2                                                     [0]
    3                                                   [1]
      4                                                 [1]
        5                                               [1]
          6                                             [1]
            7                                           [0]
              8                                         [1]
                9                                       [1]
                  10 11                                 [1]
                        12                              [1]
                           13                           [1]
                              14 15 16                  [2]
                              14 15 16 17 18 19         [4]

14 15 16から引く14 15 16 17 18 19。

1                                                       [0]
  2                                                     [0]
    3                                                   [1]
      4                                                 [1]
        5                                               [1]
          6                                             [1]
            7                                           [0]
              8                                         [1]
                9                                       [1]
                  10 11                                 [1]
                        12                              [1]
                           13                           [1]
                              14 15 16                  [2]
                                       17 18 19         [2]

結果のセットはすべて互いに素です。それらを結合すると、次のようになります。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19         [13]

1 から 19 までの嘘つきの数は 13 であることがわかります。

この手法は、すべての場合に問題を完全に解決するわけではありません。たとえば、2 つのサンプル入力の短い方では、この手法は文字通り何もしません。ただし、より大きな問題の場合、セットをよりモジュール化された形式に分解します。これにより、総当たり攻撃がより簡単/高速になると思います。たとえば、より大きなサンプルでは、​​問題空間を正確に 2 つの可能性に分解しました。

1. there are 13 liars among soldiers 1-19, and Soldier 20 is not a liar.
2. there are 13 liars among soldiers 1-19, Soldier 20 is a liar.

これら 2 つのケースを簡単に評価して、嘘つきの数の最小値が 13、最大値が 14 であることを判断できます。

Answer 3

これは整数線形計画法として簡単に定式化できます。制約行列は完全にユニモジュラーであるため、任意の ILP ソルバーですばやく解決できます。