Раз никто не написал такой пост, сделал я. Давайте здесь пообсуждаем раунд.
№ | Пользователь | Рейтинг |
---|---|---|
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 |
10 | nor | 152 |
Название |
---|
Collaborating in any way with anyone else (member or not) during a rated event is considered cheating. This includes discussing problem statements or solutions between the time that the coding phase begins and the time that the challenge phase ends.
В 500ку пол часа въезжал.
Когда на СФ дают условие с кучей воды, то, во-первых, почти всегда понятно, где в нем вода, и что можно не читать вообще, если прога пройдет претесты (обычно различные количество разных строго положительных и т.д. - выделены).
Во-вторых, там как раз нету длинных формальных определений) Как я уже сказал выше:)
Ну и последнее, тоже довольно важный факт. Русский для меня не родной, но чтение условия на русском все же значительно меньше нагружает, чем на английском. Многие, как и я, читают вроде бы и без проблем, но "лучше бы не на англ..." :) Те, кто знает свой родной русский, но трудно читает на англ, явно сегодня возненавидели 500.
Горю желанием просветиться в нецензурной лексике, такому меня родня с Украины не учила))
На челленжах от безысходности ломал всех, чье решение было подозрительно. В итоге +4 -3 = +125 очков, итого 200 в сумме. Но все равно обидно, могло бы быть гораздо больше.
Объясните, как нормально делать 500?
Я считал для каждого столбца его "плохоту" - сколько минимум штрафа можно насобирать на этом столбце, а дальше сортировал по этой "плохоте" (т.к. чем раньше мы поставим столбец, тем большим будет множитель, равный числу возможных суффиксов).
Но примерно за 10 минут до конца, когда я наконец-то доделал свое решение, возникли проблемы с дубликатами. Обломным был тест "а а в в", на который мое решение упорно давало ответ 5.
Отдебажить не успел:( В процессе решения я не строил в явном виде перестановки для ответа, а обходного пути для удаления дубликатов не нашел.
Можно было как-то просто?
Слив засчитан...
250ка упала (ещё не понял почему). В 500ке почему-то забыл что можно для каждого столбца свою перестановку чисел (из-за чего очень удивлялся как это её столько человек сдает). Итого 50 поинтов. Мдя.
C 250ой понятно... Перепутал i и j в 1 месте...
У меня круче слив, -50.
В 250 сабмит... Дальше еще раз прочел условие... И почему-то вместо possible прочел positive :)
Сначала думал ресабмитить, потом как-то не удавалось тест придумать на 0... Нервы блин...
Перед началом систестов меня успокоили, что там positive:) Но я уверенно заявил, что все равно на чем-то упадет.
Угадал.
А в 500 обломали повторы строк в инпуте.
P.S. Я, по ходу, ступил так же, как rng58. long вместо long long, спешил блин:( :( Зато теперь поднимать рейтинг будет намного проще:) :)
В каждом матче найдутся люди, которым он понравился, потому что они подняли рейтинг - благодаря результатам тех людей, которым он не понравился:)
Мои поздравления!
А у меня почти -200 (еще бы нет, последнее место в дивизионе), и теперь самый низкий рейтинг за последние 2.5 месяцев.
И на CF не идет что-то, и на ТопКодере...
1) граф связный;
2) степень каждой вершины чётна;
3) для каждой вершины кроме стартовой #рёбер любого цвета не более половины;
4) для стартовой вершины #рёбер любого цвета - 2 не более половины.
Доказывается просто, при этих условиях есть полное паросочетание по рёбрам для каждой вершины, соединим рёбра по этому паросочетанию, получим набор маршрутов, которые надо склеить. Склеить всегда можно, т.к. граф ориентированный и цикл всегда можно развернуть, добившись выполнения условия на цвета рёбер. Необходимость вообще очевидна.
Далее, построим лексикографически наименьший маршрут. У нас будет функция check(from, to, previous_color), которая проверяет, есть ли в текущем графе маршрут из from в to при условии, что сейчас запрещён цвет previous_color. Она проверяет какие-то условия, похожие на 1-4, только более запутанные. Будем строить граф по одному ребру, пробуя на каждом шаге добавить все возможные рёбра и проверить, корректно ли это добавление. Шагов будет O(n2), на каждом шаге O(n) вызовов функции check, итого время работы O(n5). Большая часть ресабмитов была видимо из-за багов в разборе случаев в функции check (по крайней мере, у меня именно из-за этого).