Форум программистов, компьютерный форум CyberForum.ru

Задача на динамику с codeforce'a - C++

Восстановить пароль Регистрация
 
paladinama
0 / 0 / 0
Регистрация: 27.03.2013
Сообщений: 21
07.01.2014, 16:54     Задача на динамику с codeforce'a #1
Всем привет! Уже неделю не могу разобраться в решении задачи с codeforce'a. Собственно сама задача. А вот её разбор
Кликните здесь для просмотра всего текста
Есть несколько наблюдений, после которых задача становится очень простой. Первое наблюдение — пикать надо всегда самого сильного героя. А вот про баны ничего такого сказать нельзя, в разных ситуациях могут потребоваться самые разные баны. Самое важное наблюдение, которое поможет решить задачу — то, что рассматривать следует только m сильнейших героев. Действительно, при любой игре, где будут пикаться самые сильные герои в каждый момент времени, никакой герой, кроме первых m, не может быть пикнут вообще никогда. Значит, и банить их никогда не надо. И рассматривать тоже.

В итоге у нас остается в худшем случае 20 героев, а, значит, можно решить задачу динамикой по подмножествам: dpmask — разность между силами команд в ситуации, когда пикнуты либо забанены те и только те герои, чьи биты в маске установлены в единицу. Для переходов перебираем героя, которого команда, чья очередь хода, будет пикать или банить. Проще всего реализовать это с помощью рекурсии с сохранением. Ответ будет храниться в dp2m - 1.

К сожалению, мы неправильно оценили сложность этой задачи (несмотря на простое в реализации решение, придумать его, как выяснилось, было не так то и просто — стандартные 1500 баллов были бы лучше), и выставили неправильный TL (так что многие решения на C++ за m2·2m проходили — следовало опустить ограничение до одной секунды, а то и до 0.75 секунд). Так что если вы решили задачу за m2·2m, считайте, что вам повезло и что ваш вердикт — Time Limit Exceeded.

Почему можно писать это за m·2m? Потому что пропуск бана не имеет смысла: вместо этого можно забанить самого слабого героя из доступных — ведь его точно никто никогда не пикнет.

Здесь тоже были слабые претесты, поэтому можно было ломать тех, у кого в решении не было битмасок, чуть ли не любым большим случайным тестом.


Саму задачу я понял. Первая мысль была полным перебором, но это долго. Посмотрел решения других, но так и не смог понять, почему оно работает.
1. Почему 2m. Точнее почему 2? Если степень я еще могу понять, почему m, то почему 2.
2. Почему через биты. У всех решения через биты, но почему?
3. Да почему оно так должно работать?

Решения других можно посмотреть здесь. В фильтре справа выбрать задачу (E -Captains Mode), а вердикт - полное решение(или accept).

Может кто-нибудь объяснит, почему оно должно работать? =)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.01.2014, 16:54     Задача на динамику с codeforce'a
Посмотрите здесь:

Задача на динамику или комбинаторику C++
C++ Codeforce. Такси.
Разобраться в задаче с Codeforce C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 03:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru