Всем привет!
Недавний тестовый раунд прошел хорошо. Ожидается, что теперь все будет работать быстрее. В подготовке задач сегодняшнего раунда принимали участие: Михаил Мирзаянов, Николай Кузнецов, Иван Фефер и Мария Белова.
Удачи!
Артем Рахов и команда Codeforces
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
Неправильный ответ на взлом 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?