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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Не работает реверс строки http://www.cyberforum.ru/cpp-beginners/thread1064994.html
Всем привет, ребятки! Я тут принялся работать с функциями обработки строк, и у меня возник вопрос. Вот вам сначала мой код: #include <iostream> #include <cstdio> #include <cstring> using...
C++ Запуск программы без создания окна. Запуск фоновой программы Вопрос, как сделать, чтобы консольное приложение при запуске не создавало окошко консоли. Т.е. запустился процесс, но визуально ничего не появилось. :) Очень криво спросил, но мне кажется понятно,... http://www.cyberforum.ru/cpp-beginners/thread1064985.html
Ошибка C++
Пдскажите пожалуйста в чём ошибка. Нужно быдо сделать задание: 27. Среди чисел 1, 1+1/2, 1+1/2+1/3, …найти первое, большее числа n. Вот код: #include <iostream.h> #include <conio.h> #include...
Двойное наследование C++
Доброго времени суток. Я делаю домашнее задание, в котором надо создать класс из него создать два производных класса, а потом из этих двух создать еще один. Только есть маленькая неувязочка....
C++ Чтение из файла и запись числа в массив http://www.cyberforum.ru/cpp-beginners/thread1064961.html
Добрый день, уважаемые. Помогите. Есть файл func.txt, в котором через пробел записаны координаты X и Y точки на плоскости. Также есть функция, область определения которой задана прямоугольным...
C++ Найти количество элементов, встречающихся в обоих массивах Помогите решить хотя бы какую-нибудь задачу пожалуйста можно без инклюдов и прочей фигни просто функцию и массив подробнее

Показать сообщение отдельно
paladinama
0 / 0 / 0
Регистрация: 27.03.2013
Сообщений: 21

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

07.01.2014, 16:54. Просмотров 821. Ответов 0
Метки (Все метки)

Всем привет! Уже неделю не могу разобраться в решении задачи с 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).

Может кто-нибудь объяснит, почему оно должно работать? =)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru