| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Здравствуйте! Недавно я наткнулся на метод под названием "Meet-in-the-middle", почитал о нём на вики и захотел использовать его на этой задаче(Куча камней), но безуспешно. Объясните мне решение.
UPD: Помогите ещё с этой задачей(клик).Решается ли эта задача при помощи формулы включений-исключений ?
Спасибо за внимание!
Не вижу, как можно применить Meet in the middle в этой задаче.
Эта задача скорей на битовые маски. Надо просто перебрать битовые маски одного из множеств и считать сумму для одного множества и для другого
Да, но так получится O(2^N * N). А можно за O(2^(N/2) * log(2^(N/2)) вроде.
Если ограничения будут немного больше (на TopCoder давали 34, если не ошибаюсь), то "обычное" решение с масками не пройдет по понятным причинам. Тогда можно использовать идею meet in the middle. Перейдем к следующей задаче — набрать кучку, вес которой не меньше половины, но как можно меньше. Тогда понятно, что разность между весом этой кучки и весом остатка — и будет ответом на задачу.
Разобьем начальное множество камней на 2 части равного размера. Для каждой сгенерируем все возможные подмножества и отсортируем их по весу. Предположим, что мы зафиксировали подмножество из первой группы. Тогда нам известно, какое ограничение снизу на вес подмножества из второй группы, и среди всех таких подмножеств нужно выбрать самое легкое. Объединение этих двух подмножеств и будет кандидатом на лучший ответ.
Отсюда получаем решение — использовать два указателя и meet in the middle. Один указатель на самое тяжелое подмножество из первой части, второй — на самое легкое подходящее подмножество второй. Когда двигаем первый указатель вниз — надо проверить, что суммарный вес не стал меньше половины, если стал — двигаем второй указатель вверх до тех пор, пока не кончится массив или пока суммарный вес не станет опять не меньше половины.
Всё понятно, разобрался. Спасибо за объяснение!
Первую ещё можно рюкзаком решать, например. Ассимптотика выйдет O(N * MAXSUM) времени и O(MAXSUM) памяти. Но в данном случае перебор битмасками работает быстрее.
Во второй ответом будет MAX(0, SUMa - N * (K - 1)). Одно из возможных доказательств:
Рассмотрим два отдельных диалекта. Пусть на первом говорит A человек, а на втором — B. Тогда понятно, что если всего есть N человек, то на обоих диалектах будет говорить не меньше A + B - N. Теперь мы можем свести два любых диалекта в один. Будем делать это, пока у нас не останется лишь один диалект. Несложно заметить, что сделать это нам прийдётся ровно K - 1 раз. При этом если N из формулы для двух диалектов будет во всех слагаемых (что в конце выльется в N * (K - 1)), несложно заметить, что остальная часть формулы сойдётся в сумму кол-ва носителей каждого из диалектов.
Дошло. Спасибо!