Всем привет!
Недавний тестовый раунд прошел хорошо. Ожидается, что теперь все будет работать быстрее. В подготовке задач сегодняшнего раунда принимали участие: Михаил Мирзаянов, Николай Кузнецов, Иван Фефер и Мария Белова.
Удачи!
Артем Рахов и команда Codeforces
- Задачи
- Результаты
- Победитель: JKeeJ1e30
Неправильный ответ на взлом 1
?
Ты должен пройти тест, которым тебя взломали.
Читаем правила до контеста.
А почему я не вижу «вкладку» Взломы? Раньше вроде была.
Может конечно из-за того, что я вне конкурса, но всё равно странно.
И вот в который раз.... Открываю код для взлома, вчитываюсь, закрываю и... понимаю, что не моню чей это код. :(
Реквестирую подпись автора сверху.
В задаче D на первом тесте может и быть такой ответ?
2 3
1 2
2 3
9 10
Вывод
8 10
Давайте посчитаем динамику по подмножествам: d[m][subm] - количество способов сделать связанное дерево из подграфа m с тупиковыми вершинами subm. Ответ будет суммой по d[2n-1][x], где кол-во единичных бит в x = k.
Как пересчитывать: для пустого множества и множества из двух вершин (либо 0, либо 1) - очевидно. Теперь для большего: переберём i из subm - какой-нибудь тупик. Отрежем его от дерева по некоторому ребру в b. Получаем дерево на меньшем множестве вершин и с либо уменьшенным на 1 множеством тупиков, либо с изменённым i на некоторое b. Добавляем к текущему ответу уже посчитанную динамику. В конце надо разделить на k.
В принципе, наверное, всё равно, какой тупик отрезать.
So I tried the following:
int main()
{
string str = "codeforces";
cout << str[11] << endl;
return 0;
}
It banged, crashed, exploded. Still, I agree that if current_address is char[], then the code will not crash and everything will go smoothly, exactly because of the '\0' character you spoke of.
http://ru.wikipedia.org/wiki/Сортировка_выбором
Только выбираем не минимальный элемент, а необходимый.
на тк кстати тоже подставы с этим бывали, так как присутствует субъективность оценки
разумеется оценка должна быть примерной, с которой согласно большинство
Один раз - площадь в int-ах в B, второй раз - не поставил break из цикла после обмена в D.
На самом деле, конечно, порядок задач по сложности: A,C,D,B или даже C,A,D,B...
> Чтобы не ошибаться с размером везде пишу вектора, даже для деревьев.
Извини, но по-моему это немножко быдлостиль.
Когда-нибудь по времени не успеешь с таким подходом. Владеть надо обоими.
hehe...
I will happier even to float at "yellow-red" border.. :)
Я решал перебором за O(числа деревьев). Деревьев <= n^(n-2) так что по времени проходит да и память сэкномлена по сравнению с динамикой:). Идея перебора хранить маску посещенных вершин и маску тупиковых, а при переходе пытаться увеличить дерево из первой (по номеру) тупиковой вершины после чего эта вершина перестает быть тупиковой (для алгоритма т.е. она удаляется из подмн-ва тупиковых). Ясно что при такой рекурсии ни одно дерево соответствующее пути(стэку) рекурсии не встретится дважды.
Я не решил, но в конце появилась такая идея.
Неправильное решение.Перебираем все возможные подмножества тупиковых вершин.
Для оставшихся вершин считаем количество остовных деревьев на них. (например по теореме Кирхгофа http://e-maxx.ru/algo/kirchhoff_theorem)
А также динамикой считаем количество способов выбрать из каждой тупиковой вершины по одному ребру, так чтобы в каждую нетупиковую входило хотябы одно ребро.
Перемножаем эти два числа и прибавляем к конечному ответу.
Наверняка есть способ проще ;)
Вот и хорошо, что не стал такую фигню под конец контеста кодить))
UPD
а, прошу прощения, дошло))
In problem B test 7, the input is 99 100 and the answer is 80 64. But what if the answer is 64 80? My program told me the latter answer and I think it's more reasonable--people would usually like to cut pictures as consistent with the origin ratio as possible, wouldn't they?