algorithm - 骗子之谜

Question

我一直在尝试解决Interviewstreet中的一个难题。但我现在不知道这个问题。如果有人可以给我一个提示，那就太好了。

谜题是：你有 N 个士兵，从 1 到 N 编号。你的每个士兵要么是骗子，要么是诚实的人。你有 M 组关于它们的信息。信息格式如下：

每行包含 3 个整数 - A、B 和 C。这意味着在编号为 {A, A+1, A+2, ..., B} 的士兵集合中，恰好有 C 个是骗子。像上面这样有M行。

让 L 是你的说谎者士兵的总数。由于您无法找到 L 的确切值，因此您希望找到 L 的最小值和最大值。

输入：

输入的第一行包含两个整数 N 和 M。接下来的 M 行中的每一行包含三个整数 - A、B 和 C (1 <= Ai <= Bi <= n) 和 (0 <= Ci <= Bi-Ai ）。其中Ai、Bi、Ci分别指第i行中A、B、C的值，N、M不大于101，保证给定信息可满足。您总能找到满足给定信息的情况。

输出：

将两个整数 Lmin 和 Lmax 打印到输出。

样本输入

3 2
1 2 1
2 3 1

样本输出

1 2

样本输入

样本输出

13 14

解释

在第一个示例测试用例中，第一行是“3 2”，表示有 3 名士兵，我们有两组信息。第一个信息是在士兵集合 {1, 2} 中有一个是骗子，第二个信息是在士兵集合 {2,3} 中又有一个骗子。现在这种情况有两种可能性：1号和3号士兵是骗子或2号士兵是骗子。所以说谎者的最小数量是 1，说谎者的最大数量是 2。因此答案是 1 2。

score 7 · Accepted Answer

这是又一个动态规划问题。不需要启发式。

在每个ifrom0到n，您距离满足所有当前打开的条件有多远，您需要跟踪骗子的最小和最大数量。（开放条件是某种形式，“从这里到j我需要k更多的骗子。”）

如果您有的解决方案，对于您拥有的每个部分解决方案i，移动到i+1如下：

放弃你已经达到并满足的所有条件。
为此号码添加所有新条件。如果新条件与您现有的解决方案冲突，请丢弃此部分解决方案。以下是条件之间的冲突规则，即j你需要k骗子和j'你需要k'骗子j <= j'：
1. 如果k < k'有冲突。（你不能有更多的说谎者，j然后再减少j'。
2. 如果j' - j < k' - k有冲突。（你不能在士兵中添加k' - k骗子。）j' - j
3. 否则不存在冲突。
如果没有条件说士兵j需要添加j-i骗子，则可以为当前步骤添加当前士兵不是骗子的部分解决方案。（这里的“添加”是指“确保跟踪此状态，如果未跟踪，则根据需要更新 max/min”。）
如果没有条件说0未来会增加士兵，您可以为当前步骤添加部分解决方案，当前士兵是骗子。（在这个解决方案中，首先改变状态，说每个条件都需要少一个骗子——因为你添加了一个，然后像以前一样继续。）

你的起始条件是，i = 0有骗子的1解决方案，0绝对没有条件。

从解决方案0开始生成1, 2, ... ,的部分解决方案n。当你到达时，n你有你的答案。

（注意，通过适度的修改，您不仅可以计算出最大和最小是什么，还可以计算出究竟有多少解决方案。）

score 5 · Accepted Answer

使用以下原则，您可以获得 90% 的成功：

如果集合中的骗子数量为零，则将该集合分解为大小为 1 的集合，每个集合的骗子数量为零。所以1 3 0变成1 1 0和。2 2 0_3 3 0
如果集合中说谎者的数量等于集合的大小，则将该集合分解为大小为 1 的集合，每个集合中的说谎者数量等于 1。所以2 5 4变成2 2 1and3 3 1和4 4 1and 5 5 1。
对于我们拥有的任意两个集合 A 和 B，如果 A 是 B 的子集，则从 B 中删除 A 的所有元素，并从 B 中的骗子数中减去 A 中的骗子数。

我们将使用这些原则来解决您的两个示例问题中较长的一个。首先获取给定的输入，并将它们转换为索引集。

    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                                                   [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有三个骗子，所以将他们分解成单独的集合，然后从包含它们的任何其他集合中减去它们。

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。

这种技术并不能完全解决所有情况下的问题。例如，在您的两个样本输入中较短的一个中，此技术实际上没有任何作用。但是，对于更大的问题，它确实将您的集合分解为更模块化的形式，我希望这会使暴力破解更容易/更快。例如，在更大的样本中，我们将问题空间分解为两种可能性：

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.

我们可以很容易地评估这两种情况，以确定最小的骗子数为 13，最大为 14。这比尝试所有 2^20 的骗子和非骗子组合要快得多。

score 3 · Accepted Answer

您可以轻松地将其表述为整数线性程序。由于约束矩阵是完全单模的，它可以被任何 ILP 求解器快速求解。

score 0 · Accepted Answer

好的，如何将问题重新转换为概率/分布估计

这与“逆问题”（例如从已知平均值推断概率分布）非常相似，MAXENT（最大熵）等方法可以很好地解决（例如http://books.google.gr/books?id=Kk6SyQ0AmjsC&pg=PA35&lpg=PA35&dq =MAXENT+inference&source=bl&ots=W4kVjXRpe7&sig=IzjnOVT0FQJtIXSkeFssNxolLh4&hl=el&sa=X&ei=nxJkU-LUHMmkPciigZAH&ved=0CGcQ6AEwCDgK#v=onepage&q=MAXENT%20inference&f=false )

（另外很高兴能够将看似奇怪的场连接到底层的物理现实）

鸟类学？？:)

algorithm - 骗子之谜

4 回答 4

Related

Reference