Загадка лжецов

Я пытался решить головоломку на 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, B i и C i относятся к значениям A, B и C в i-й строке, соответственно, N и M не больше 101, и гарантируется, что данная информация удовлетворяет. Вы всегда можете найти ситуацию, удовлетворяющую заданной информации.

Выход:

На выходе выведите два целых числа 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 солдата и у нас есть два набора информации. Первая информация состоит в том, что в наборе солдат {1, 2} один лжец, а вторая часть информации состоит в том, что в наборе солдат {2,3} снова есть один лжец. Теперь есть две возможности для этого сценария: солдаты номер 1 и 3 лжецы или солдат номер 2 лжет. Таким образом, минимальное количество лжецов равно 1, а максимальное количество лжецов равно 2. Следовательно, ответ 1 2.


algorithm
person zcb    schedule 07.06.2012    source источник

Ответы (4)


arrow_upward
3
arrow_downward

Вы можете легко сформулировать это как целочисленную линейную программу. Поскольку матрица ограничений полностью унимодулярна, ее можно быстро решить с помощью любого решателя ILP.

person Falk Hüffner    schedule 08.06.2012
comment
Спасибо чувак. Ваша идея хороша, но недостаточно эффективна для решения этой проблемы. Я пытался использовать эту идею, но обнаружил, что она не удалась в 6/10 тестовых случаях. Причина в том, что в этих неудачных тестовых примерах переменных почти 100, и многие из них являются свободными переменными. Чтобы получить минимальное/максимальное количество лжецов, мне нужно перечислить все возможные значения свободных переменных. Если свободная переменная больше 30, что означает, что я должен перечислить 2 ^ 30 (около 10 ^ 9), это будет слишком медленно. Любая идея, чтобы избежать этой дилеммы? - person zcb; 09.06.2012
comment
Я не уверен, что вы реализовали. Идея заключалась в том, чтобы передать проблему готовому решателю ILP, такому как GLPK или Coin CBC. Имея всего 100 переменных, они должны решить ее за долю секунды. Если бы вы хотели реализовать это самостоятельно, вы, вероятно, использовали бы алгоритм Simplex. - person Falk Hüffner; 09.06.2012
comment
Привет, Фальк. Я предполагаю, что вы имеете в виду сформулировать эту проблему с помощью целочисленной программы и преобразовать эту целочисленную программу в линейную программу. Решатель ILP эффективен для линейной программы. Но решение является фракционным числом, а не целым. Итак, как я могу найти оптимальное целочисленное решение на основе результата, возвращаемого решателем ILP? - person zcb; 09.06.2012
comment
Поскольку матрица ограничений является полностью унимодулярной, а правая часть интегральной, ослабленное решение фактически будет интегральным. - person Falk Hüffner; 09.06.2012
comment
Вау, я не знал этого раньше. Это означает, что эта головоломка почти решена! Не могли бы вы объяснить, почему расслабленное решение является интегральным, или порекомендовать материалы, решающие эту задачу? - person zcb; 09.06.2012
comment
Матрица ограничений имеет свойство последовательных единиц, означающее, что вы можете расположить столбцы так, чтобы единицы в каждой строке были последовательными. Свойство последовательных единиц влечет полную унимодулярность. Это хорошо известный результат 1950-х годов о том, что ЛП с полностью унимодулярными матрицами ограничений и целочисленными правыми частями имеют целочисленные решения. Книга, которая должна охватывать это, например. А. Шривер: Теория линейного и целочисленного программирования. - person Falk Hüffner; 09.06.2012
comment
В качестве альтернативы также известно, что ILP со свойством последовательных единиц могут быть преобразованы в задачи сетевых потоков, которые могут дать более быстрое решение (вы можете найти это, например, в Ahuja, Magnanti и Orlin: Network Flows: Theory, Algorithms, and Приложения). - person Falk Hüffner; 09.06.2012
comment
Вы нашли решение ILP? мое решение проходит 4/10 (не проходит 6/10) с неправильными ответами. В моем решении свободные переменные устанавливаются равными нулю для минимального значения и единице для максимального значения. В любом случае, тесты терпят неудачу из-за неправильных ответов, а не из-за сложности времени/пространства. - person Ivor Prebeg; 25.11.2012

arrow_upward
7
arrow_downward

Это еще одна проблема динамического программирования. Эвристики не нужны.

В каждом i от 0 до n, в зависимости от того, как далеко вы продвинулись к удовлетворению всех текущих открытых условий, вам нужно отслеживать минимальное и максимальное количество лжецов. (Открытое условие имеет форму: «Отсюда до j мне нужно k больше лжецов».)

Если у вас есть решение для i, переход к i+1 происходит следующим образом для каждого частичного решения, которое у вас есть:

  1. Отбросьте все условия, которые вы достигли и удовлетворили.
  2. Add all new conditions for this number. If a new condition conflicts with your existing solution, throw this partial solution away. Here are the rules for conflict between a condition saying that by j you need k liars and by j' you need k' liars with j <= j':
    1. If k < k' there is a conflict. (You can't have more liars by j and then less again by j'.
    2. Если j' - j < k' - k есть конфликт. (Вы не можете добавить k' - k лжецов к j' - j солдатам.)
    3. В противном случае конфликта нет.
  3. Если ни одно из условий не говорит о том, что к солдату j нужно добавить j-i лжецов, вы можете добавить для текущего шага частичное решение, при котором текущий солдат не является лжецом. (Под «добавить» здесь я подразумеваю «убедиться, что это состояние отслеживается, и при необходимости обновить максимальное/минимальное значение, если оно не отслеживалось».)
  4. Если никакое условие не говорит о 0 дополнительных солдатах к будущей точке, вы можете добавить к текущему шагу частичное решение, в котором текущий солдат является лжецом. (В этом решении сначала измените состояние, чтобы сказать, что каждое условие требует на одного лжеца меньше, потому что вы добавили одного, а затем продолжайте, как раньше.)

Ваше начальное условие состоит в том, что с i = 0 есть 1 решение с 0 лжецами и абсолютно без условий.

Из решения для 0 начните генерировать частичные решения для 1, 2, ..., n. И когда вы достигнете n, у вас будет ответ.

(Обратите внимание, что с небольшой модификацией вы можете выяснить не только, что такое максимум и минимум, но и сколько именно существует решений.)

person btilly    schedule 07.06.2012
comment
Привет! Спасибо за ваш ответ! Я думаю, что использование DP - правильный путь. Сейчас пытаюсь реализовать. - person zcb; 08.06.2012

arrow_upward
5
arrow_downward

Вы можете пройти 90% пути, используя следующие принципы:

  1. Если количество лжецов в наборе равно нулю, разбейте этот набор на наборы размера 1, в каждом из которых количество лжецов равно нулю. Итак, 1 3 0 становится 1 1 0, 2 2 0 и 3 3 0.

  2. Если количество лжецов в наборе равно размеру набора, разложите этот набор на наборы размера 1, в каждом из которых количество лжецов равно одному. Таким образом, 2 5 4 становится 2 2 1, 3 3 1, 4 4 1 и 5 5 1.

  3. Для любых двух имеющихся у нас множеств A и B, если A является подмножеством B, тогда удалите все элементы A из B и вычтите количество лжецов в A из числа лжецов в B.

Мы будем использовать эти принципы для решения более длинной из ваших двух примеров задач. Начните с ввода данных и преобразования их в наборы индексов.

    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 комбинаций лжецов и не лжецов.

person Kevin    schedule 07.06.2012
comment
Очень красивое решение своими руками. Но где бы вы были, если бы они отказались от половины условий? Программа, попадающая в набор тестов, должна быть в состоянии справиться с этим. - person btilly; 07.06.2012

arrow_upward
0
arrow_downward

Хорошо, как насчет того, чтобы переформулировать проблему как оценку вероятности/распределения?

Это очень похоже на «обратные задачи» (например, вывод распределения вероятностей из известных средних значений), которые очень хорошо решают такие методы, как MAXENT (максимальная энтропия) (например, http://books.google.gr/books?id=Kk6SyQ0AmjsC&рд=PA35&СУГ=PA35&дк=MAXENT+умозаключение&источник=бл&отс=W4kVjXRpe7&сиг=IzjnOVT0FQJtIXSkeFssNxolLh4&гл=е&са=Х&е=nxJkU-LUHMmkPciigZAH&вед=0CGcQ6AEwCDgK#v=OnePage&д=MAXENT%20inference&F=ложь»отн=)

(плюс приятно иметь возможность связать кажущиеся странными поля с лежащей в их основе физической реальностью)

Орнитология?? :)

person Nikos M.    schedule 02.05.2014