| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 7 | cnnfls_csy | 3569 |
| 9 | ecnerwala | 3494 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | maomao90 | 160 |
| 3 | -is-this-fft- | 159 |
| 4 | atcoder_official | 158 |
| 4 | awoo | 158 |
| 4 | cry | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | maroonrk | 152 |
Всем привет! Осталось меньше суток до начала раунда 1B. Если вы, как и я, предпочли сон замечательному раунду 1А, то этот раунд именно для вас! 1000 участников, показавших лучший результат пройдут во второй раунд и не будут иметь возможности поучаствовать в следующем подраунде.
Напоминаю, что раунд пройдёт в субботу, 3 мая в 16:00 UTC на сайте, который и так все знают.
Напоминаю, что до начала осталось всего 4 минуты.
===============================
Just a reminder. It is less than 4 minutes before the start of contest.
как решать С?
Как решались А, В, С? :D
Как решается C?
Я 1002-ой
Ощущал себя также после первого раунда, когда был 1007.
Расскажите пожалуйста как решать А и Б) В C у меня на маленьком тесте прошло решение поддерживаем стек где мы сейчас(и куда возвращаться по обратным), проверяем в какие можем полететь (если нужно раскручивать стек, то граф должен оставаться связным), выбираем минимальную и летим туда. На большом получил runtime, либо ошибка в коде, либо в алгоритме.
А. В каждой строке заменим группу подряд идущих одинаковых символов на один такой же символ. Если теперь все строки равны, ответ есть. Для каждого символа в получившемся шаблоне посмотрим, сколько таких букв будет в данной "секции" в финальной строке. Просто переберём это количество, прибавим для каждой строки, сколько нужно будет операций, чтобы получить столько букв, а потом выберем минимум из таких сумм. Понятно, что для каждой секции ищем количество независимо от других.
из abab после замены получается abab или как?
Да, заменяются только подряд идущие символы.
А:
, где k — число, до которого перебираем. Легко заметить, что больше, чем 100 его брать незачем. В принципе, если поизвращаться, можно свести к 
Заметим, что всё, что мы можем делать — менять количество символов в отрезке, целиком состоящем из одних и тех же символов. Теперь разбиваем каждую строку на такие отрезки. Если в итоге их общий вид не совпадает, то мы проиграем. Иначе для каждого отрезка перебираем длину, к которой мы хотим привести его для всех строк. Суммарно будет работать
Даже не нужно перебирать k, известно, что оно равняется медиане множества.
Было такое предположение, не стал рисковать)
Аналогично. Да и если ограничения позволяют, то почему бы и не перебрать)
извиняюсь, 2 часа думал что мы повторяем подстроки, а не символы(
Традиционная рубрика обмена решениями.
Два вопроса:
1) А как попроще/покороче решать B-large? Я простенькую динамику по битам написал, которая за O(lg(max(a, b, c)) работает.
2) А как правильно решать C-large? У меня в итоге мнгновенно на их тестах работает O(n!) с неким набором очевидных отсечений.
С там нельзя сказать, что мы идем в минимальный лесикографический индекс, если после этого полета сможем посетить все оставшиеся? Если можно, то перебираем куда летим, можем туда лететь если есть откуда ( в стеке текущего состояния есть элемент, из которого есть рейс в планируемый) и если при этом мы стек разматываем, то в эти вершины мы не вернемся, т.е. их удаляем, проверяем что граф связный. Вроде N^3.
Ну вот у меня ровно почти такие же отсечения на тупой перебор. Тут смотри какая шляпа, есть некое множество вершин, которые ты ещё не рассмотрел. И может быть как раз из них будет ребро в некую другую.
То есть на пути в стеке ребра нет, а потом оно появится.
Ну так ты удалил плохие вершину, а по остальным dfs, т.е. ты проверяешь что остальные в одной компоненте, не важно доступны они сразу или через несколько ребер.
А, ок, я понял.
Спасибо.
У меня такое же решение
У меня B-large так: фиксируем префикс, заканчивающийся на 1 в A, в B и в K (+еше надо учесть, когда префикс равен всей строке). Это у нас будет означать числа, в которых префикс фиксирован, потом идет 0 вместо 1 и потом рандомные биты и ты пытаемся посчитать число способов для таких чисел. Ну просто в лоб для каждого бита перебираем что там может быть и перемножаем способы, потом все складываем. Получается за
.
Код: http://pastebin.com/FDB543Na
А может мне кто-нибудь пальцем тыкнуть где в условии задачи С написано, что нельзя использовать один и тот же рейс дважды?
А то от жюри получил ответ: "Please read the problem statement more carefully. Consider looking at the limits and the example cases if those might help."
Не прикольно понимать условие из тестов:(
At most 1 outbound flight going to each city, although there is no limit on the return flights (multiple return flights can go to the same city).
Там есть
At most 1 outbound flight going to each cityHow was the large input of Problem B supposed to be solved?
Dynamic dp[32][2][2][2] first parameter — bit number second: 1 if current mask for A equal to A, 0 if less. Same for B and K
Thanks!
There are many ways to do that. This code surprisingly works, but is awful: http://ideone.com/KOxA9q
Here is a very similar problem (XOR instead of AND) from topcoder SRM 595 div2 1000 problem : http://community.topcoder.com/stat?c=problem_statement&pm=12623&rd=15707&rm=319170&cr=23091955
You can take a look at the editorial : http://apps.topcoder.com/wiki/display/tc/SRM+595
Расскажите условие C по-человечески.
Построим остовное дерево и обойдём его в глубину. Для каждой вершины допишем её метку к изначально пустой строке, когда впервые зайдём в эту вершину. Получившуюся в итоге строку надо сделать лексикографически минимальной. Выбирать можно корень дерева, само дерево и порядок выбора рёбер при обходе.
You must use all flights which belong to the tickets you booked.
Последний сэмпл.
6 6 10001 10002 10003 10004 10005 10006 1 2 1 6 2 3 2 4 3 5 4 5
Explanation
In the last sample test case, the following is the sequence of what you should do to achieve the smallest number:
Start from city 1, write 10001. Outbound flight from 1 to 2, write 10002. Outbound flight from 2 to 3, write 10003. Return flight from 3 to 2. Outbound flight from 2 to 4, write 10004. Outbound flight from 4 to 5, write 10005. Return flight from 5 to 4. Return flight from 4 to 2. Return flight from 2 to 1. Outbound flight from 1 to 6, write 10006. Return flight from 6 to 1.
Полёт 3 — 5 не был использован, но был заказан. Что я неверно понимаю в условии?
Он не был заказан, его можно было заказать.
Спасибо
На входе даны не купленные билеты, а только пути, на которые можно купить билет. Решать, какие пути использовать, надо самому.
Условия только на инглише были? Или я плохо искал? А то my English is shit(
Да, условия только по-английски.
How to solve the last problem? I couldn't even solve the small input!
Greedily take the vertex with the least zip code among those which don't cause disconnecting the graph.
Got it, thank you :)
Скажите, пожалуйста, это верный вывод на A-small-attempt0.in?
http://yadi.sk/d/SOKmmTTbNyQX2
Просто отправил сейчас, то же самое решение, что и вчера, на тесты в дорешку и всё ОК. Но во время соревнования был вердикт Incorrect. Не уж то на одних тестах проходит, а на других валится..
Если не ошибаюсь, то тесты всем всегда разные выдаются. Дайте свой файл с инпутом, тогда можно будет сравнить ответы.
Спасибо за ответ. Проблема решена. Забыл перекомпилироваться перед отправкой во время соревнования.