| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
Остался последний шанс пройти во второй раунд TopCoder Open 2012
Рануд начинается в 20:00 MSK.
Регистрация уже открыта
Не забудьте, что разрешено только 2000 регистраций(Из которых больше 500 занято уже сейчас, через полчаса после открытия регистрации)
Что это за троллинг? Ведь long long же действительно не нужен в 250, а 500 можно решить, вообще не доказывая?
Я 500 доказал. Я сначала неправильно прочитал задачу и подумал, что от нас требуют восстановления таблички. Если рассматривать ребра в порядке топологической сортировки от старта к финишу и для всех ребер, для которых не выполняется неравенство max(u) + w(u, v) ≠ max(w), где max(u) — длина максимального пути до вершины, а w(u, v) — вес ребра, увеличивать их вес до нужной величины, то получится как раз нужный граф. Почему? Потому что этот граф будет графом "кратчайших наоборот" путей (для него это условие необходимо и достаточно, если я не ошибаюсь), а значит, любой путь будет кратчайшим, то есть равным максимальному. А ребра с каких-то из исходных максимальных путей мы не трогаем, потому что для них это неравенство всегда изначально верно.
Не совсем понял, что именно тут нужно доказывать. Ясно, что до каждого узла все пути должны иметь одинаковый вес, если мы знаем наименьший суммарный вес до узлов (i — 1, j) и (i, j — 1), то сразу знаем и для (i, j).
Мне было не сразу очевидно, почему мы можем увеличить веса на некоторых ребрах и сделать все пути одной длины так, чтобы при этом максимальный путь не увеличился.
Киньте, пожалуйста, какой-нибудь гадкий тест на 1000.
abb
Это не гадкий тест :).
После этого СРМа я начал ненавидеть кроликов, может кто-нибудь рассказать решение последней задачи?
Подождите до окончания систестов :). Решения-то рассказать можно, но нет гарантии, что они правильные.
Я решил так: подсчитал количество вхождений каждой буквы. Если у нас больше одной непарной буквы, выводим -1, иначе — ставим непарную букву в центр (если она имеется), потом двигаемся слева направо до середины, если у текущей буквы пара стоит не на месте — ставим ее на место. Разумеется, количество обменов считаем.
Такое же решение, жаль не успеть додебажить. Кстати, может быть выводить надо -1, если количество непарных букв больше n mod 2(где n — длина пароля)?
В строке четной длины не может быть нечетного кол-ва букв, которые встречаются нечетное кол-во раз. Поэтому это эквивалентно.
Спасибо, теперь ясно. Все равно на решение не повлияло было.
По-моему, первая была самая сложная =)
вообще говоря очень странно. 1000 была для меня очень лёгкой. Я её буквально за 5-10 минут придумал и написал, а вот 500 как раз сложноватая...Систесты не прошла
Я чего-то не подумал, что квалификация будет проще обычного СРМа, и потратил и в 500, и в 1000 кучу времени на доказательство решения. На мой взгляд, 1000 сложнее — его я там так и не доказал, послал на авось. А сначала вообще написал какое-то более сложное решение с поиском количества циклов в перестановке, которое к тому же оказалось неверным.
Да, это ведь нерейтинговый раунд?
rated
TCO раунды всегда были рейтинговыми
А что там доказывать? Нельзя разложить цикл длины n меньше, чем в n-1 транспозицию.
Меньше-то понятно, что нельзя, но непонятно, почему алгоритм не сделает больше шагов, чем нужно. Ведь, казалось бы, в процессе жадника мы можем сделать какие-то неоптимальные транспозиции.
а, так у меня не жадник. Я дфсом нашел все циклы
Я пытался так сделать, но, наверное, не ту перестановку находил. Я говорил, что если буква встречается первый раз, то она должна здесь остаться, а если второй, то она должна пойти симметрично первому вхождению. Но это ломается тестом aabcbc. По такому алгоритму в середине должны оказаться и буква b, и буква c.
соединяем буквы ребром, если они стоят на симметричных позициях
китайцы начитирили