Всем привет!
В данный момент идет SNSS R1, и будет идти до 10 августа.
Как и всегда, предлагаю обсудить задачи после контеста)
Всем удачи!
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Название |
---|
Разрешён ли prewritten код?
В правилах не нашёл ничего по этому поводу.
Посылки вслепую протестируются после раунда? Раньше вроде сразу показывали вердикты.
Так можно же в дорешивание послать, и узнать, что проходит, а что нет.
Спасибо. Узнал. Все печально(
Жюри не отвечает на клары уже несколько часов, что делать?
UPD. Уже ответили.
Как решать C?
А как А решается?
http://e-maxx.ru/algo/nearest_points
В D какой-то перебор?
в Д. в искомой подматрице 1 клетка одного цвета, 2 клетки другого, К клеток еще какого-то. поэтому мы знаем площать подматрицы — к * (к + 1) / 2. поэтому перебираем левый верхний угол, перебираем длину, если площадь делится на длину то получили высоту. проверяем подматрицу на хорошесть частичными суммами.
Так как нам известно количество клеток в основном элементе (k * (k+1) / 2), то мы сможем легко найти все возможные размеры сторон основного элемента (их будет не много). Теперь для каждой клетки переберем все возможные длины сторон и попытаемся построить основной элемент с одной из вершин в перебираемой клетке. Для того, чтобы быстро посчитать количество букв в основном элементе и количество каждой буквы можно воспользоваться динамикой dp[26][251][251], где dp[i][j][k] — количество букв i в прямоугольнике начинающемся в (0,0) с длиной сторон (j,k). Можно воспользоваться битовой маской для нахождения возможных количеств букв и сравнивать с таргетом. Общая сложность O(N * M * 26).
Как решать E?
Надо динамикой из A обработать ребра с d > 0 и дейкстрой из B ребра с d = 0
Можно идти с одной и той же стороны, не различая рёбра: пустить Дейкстру k раз для каждого возможного остатка бензина, то есть почти то же самое, что Дейкстру один раз на большом графе. Суммарно в графе 200·2000 вершин и 200·10 000 рёбер. Если сделать не одну очередь с приоритетами на все вершины, а 200 очередей с 2000 вершинами каждая, сдаётся с почти двухкратным запасом (на D 1.65 секунды из 3).
На самом деле можно просто запустить дейкстру на графе, в котором есть вершина для каждого города и для каждого значения остатка топлива.
Код
В коде не дейкстра. И даже не SPFA: не проверяется, что вершина уже в очереди. По-моему, лучше так не писать, особенно, если сдавать в слепую.
Такое же решение с обычной дейкстрой с set работает за 0.595с без риска свалиться на анти-SPFA тесте.
Да. Всё именно так. Никак не отучусь, потому что в 90% случаев заходит.
Можно просто дейкстрой. Состояние — вершина+сколько бензина.
Прошу прощения, если пишу не туда, но решил не создавать новую тему.
У меня одного произошла такая штука? Написал пару дней назад 2 раунд, а теперь меня нет в таблице и по всем задачам написано "нет посылок", хотя написано, что "Ваше участие в соревновании завершено"
Не у вас одного. Всех, кто писал до 8 августа (а может быть, ещё кого-то) нет в текущей таблице. Лично у меня тоже пропали посылки. Видимо, сервер падал или что-то в таком духе. На мой вопрос по этому поводу ответили, что все результаты добавят после конца раунда, так как сейчас импорт данных в текущую таблицу ещё не работает.
Спасибо!
А 3 раунд тоже не только у меня не открывается?
Тоже не только у вас.
Как решать B?
Мое решение понятно ловит TL
Замена
на
ускоряет решение в 4 раза.
как-то печально все ето...
может сможете подсказать, почему решение на D падает?
А так же подсказать идею на А и С? Спасибо.
Видимо надо заменить на
заменил на
все равно не работает.
код
Your text to link here...
Код
Я чуть-чуть подправил места, которые вызывали подозрение, и зашло
Спасибо большое! Есть идеи по А и С?
Про А выше писали, там на e-maxx есть алгоритм
Про второй раунд.
А давайте сделаем раунд, в котором шесть задач, и в каждой нужно вывести ответ по модулю, но для каждой задачи – разный модуль! Может, хоть тогда до меня что-нибудь дойдет.
А если серьезно, то на самом деле спасибо за такие проверки на внимательность. Получить пару неверных посылок по одной задаче из-за модуля, и сразу после этого на этом же контесте не сдать другую задачу только из-за того, что не смотришь на модуль – отрезвляет.
Читайте условия внимательнее, господа.