Блог пользователя tamir

Автор tamir, 11 лет назад, По-русски

Здравствуйте! Недавно я наткнулся на метод под названием "Meet-in-the-middle", почитал о нём на вики и захотел использовать его на этой задаче(Куча камней), но безуспешно. Объясните мне решение.

UPD: Помогите ещё с этой задачей(клик).Решается ли эта задача при помощи формулы включений-исключений‎ ?

Спасибо за внимание!

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Не вижу, как можно применить Meet in the middle в этой задаче.

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, но так получится O(2^N * N). А можно за O(2^(N/2) * log(2^(N/2)) вроде.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    Если ограничения будут немного больше (на TopCoder давали 34, если не ошибаюсь), то "обычное" решение с масками не пройдет по понятным причинам. Тогда можно использовать идею meet in the middle. Перейдем к следующей задаче — набрать кучку, вес которой не меньше половины, но как можно меньше. Тогда понятно, что разность между весом этой кучки и весом остатка — и будет ответом на задачу.

    Разобьем начальное множество камней на 2 части равного размера. Для каждой сгенерируем все возможные подмножества и отсортируем их по весу. Предположим, что мы зафиксировали подмножество из первой группы. Тогда нам известно, какое ограничение снизу на вес подмножества из второй группы, и среди всех таких подмножеств нужно выбрать самое легкое. Объединение этих двух подмножеств и будет кандидатом на лучший ответ.

    Отсюда получаем решение — использовать два указателя и meet in the middle. Один указатель на самое тяжелое подмножество из первой части, второй — на самое легкое подходящее подмножество второй. Когда двигаем первый указатель вниз — надо проверить, что суммарный вес не стал меньше половины, если стал — двигаем второй указатель вверх до тех пор, пока не кончится массив или пока суммарный вес не станет опять не меньше половины.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Всё понятно, разобрался. Спасибо за объяснение!

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Первую ещё можно рюкзаком решать, например. Ассимптотика выйдет O(N * MAXSUM) времени и O(MAXSUM) памяти. Но в данном случае перебор битмасками работает быстрее.

Во второй ответом будет MAX(0, SUMa - N * (K - 1)). Одно из возможных доказательств:
Рассмотрим два отдельных диалекта. Пусть на первом говорит A человек, а на втором — B. Тогда понятно, что если всего есть N человек, то на обоих диалектах будет говорить не меньше A + B - N. Теперь мы можем свести два любых диалекта в один. Будем делать это, пока у нас не останется лишь один диалект. Несложно заметить, что сделать это нам прийдётся ровно K - 1 раз. При этом если N из формулы для двух диалектов будет во всех слагаемых (что в конце выльется в N * (K - 1)), несложно заметить, что остальная часть формулы сойдётся в сумму кол-ва носителей каждого из диалектов.