Кажется, снова никому не пришло письмо.
Так что напомню, что сабж будет сегодня в 20:00 Москвы.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
10:01:42
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
10:01:42
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 07:33:20 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
у кого-нибудь получается приконнектиться к арене?
Мне одному показалось, что сегодня задачи были заметно сложнее чем обычно?
250-ка да. 550-ка нет. а 1000 как обычно.
По поводу 1000. На контесте научился сводить к матожиданию диаметра. Надо как-то научиться его считать или что-то совсем другое?
Да. Фиксируем центр — это либо вершина, либо центр ребра. А дальше расширяемся с этого места в 4/2 стороны. У нас должно быть по вершине на 2х краях — там уже формула включения/исключения
Что-то я туплю. Почему в тесте №5 выигрывает Боб?Не правильно распарсил условие
Рассмотрим ходы Алисы. Если она ходит в большой круг, в котором 4 вложенных — Боб оставляет ее с этими кругами и выигрывает. Если она ходит в один из 4-х маленьких — тогда Боб оставит ей еще один круг и выигрывает.Остальные случаи симметричны.
Как решать медиум? Я пробовал так — искал вложенности, потом считал функцию Гранди для каждого круга(переход — или ставим точку в большой круг и разбиваем на сумму игр для прямых детей, или ставим точку в одного из детей и разбиваем на сумму игр для остальных). Но такое решение не проходит 1 сеймпл, потому-что там возможен ход в круг, у которого функция Гранди равна нулю. Как с таки бороться?
Переход: точку можно ставить куда угодно, а не только в корень и в его непостредственных детей.
А вот моя интуиция сегодня тупанула, подсказав мне что функция Шпрага-Гранди от графа — высота дерева, что довольно хорошо выполнялось на маленьких графах...
Да, понял ошибку, спасибо.
Правда странно, что оно падает на тесте где максимальная глубина вложенности равна 1
Функция Гранди одного круга 1.
Ход = отрезать путь от корня до какой-то вершины. При этом понятно что отпадает. Для каждой вершины посчитали ответ для всего поддерева, потом dfs'ом посчитали ее функцию гранди. Как посчитать что отвалится вроде понятно. Если нет, то проще посмотреть код чем объяснять наверное.
PS. Ни чем от отличается от того, что у вас, ни в чем у вас проблема я так и не понял.
Я понял, спасибо.
Так решать нельзя, потому что в этом решении мы форсируем порядок ходов.
Я решал так. Будем считать функцию Гранди от поддеревьев. Пусть у нас есть дерево с корнем в какой-то вершине V. Тогда пусть S(V) — это множество всех вершин из ее поддерева (включая ее саму). Мы можем походить в любую из вершин множества S(V) — переберем ее (пусть это X). Тогда на какие игры разобьется наша исходная игра? Легко видеть, что это игры для всех компонент связности, которые останутся после удаления пути из X в V. Следовательно, нам надо просто проксорить функции Гранди для соответствующих поддеревьев. Ну а дальше взять mex, чтобы найти функцию Гранди для поддерева с корнем в вершине V.
Понятно, спасибо.
I cant participate because no e-mail notification.