Сегодня через 35 минут состоится очередной SRM. Предлагаю после контеста здесь обсуждать задачи.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3390 |
| 6 | Um_nik | 3387 |
| 7 | tourist | 3384 |
| 8 | heuristica | 3322 |
| 9 | turmax | 3319 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | AmShZ | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | maroonrk | 134 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
Если читать пост, начиная с заголовка, то получается речь мастера Йоды:
Спасибо, исправил.
Зачем? :(
Как решать 550 div I?
P.S. У некоторых видел что-то очень похожее на потоки.
Я решал жадно о_О Сначала флойдом посчитал все расстояния. Потом с помощь. этих расстояний нашёл для любых вершин i,j можно ли пройти через j, идя по кратчайшему пути i. Далее, пока есть невыкинутые вершины делаем следующее: 1. Увеличить счётчик на 1. 2. Жадно найти любой путь из невыкнутых вершин: находим ближайшую к 0 невыкинутую, потом ближайшую к ней невыкинутую, в которую можно перейти, и так далее. И выкинуть все вершины этого пути.
Мне кажется, что должно работать.
Мне кажется, что нет.
вообще, эта задача эквивалентна покрытию ориентированного ациклического графа минимальным количество непересекающихся по вершинам путей, а это абсолютно точно решается паросочетанием
жадность верна или нет — пока сказать сложно, но мне кажется, что нет. Хотя в этой задаче может быть граф очень специфического вида... Например, он транзитивен, это что-нибудь дает?
А что делать с вершинами, через которое возможно прокладывать путь, но которые использовать не обязательно... там ничего особенного не возникает?
Ну на них просто забить надо
Надо было тебя ломать :(
На тесте: N=4, ребра:
0 1 3
0 2 2
1 3 2
2 3 3
2 4 9
У тебя найдется сначала путь 0 2 3, потом 0 1, потом 0 4, а можно покрыть двумя путями.
Ты прав, чёрт возьми.
Всё упало. Утренний SRM, такой утренний...
А ты сегодня ОК, поздравляю) Или для тебя это уже не ок?
Вроде контрпример:
А и С могут проводить Б (и мы жадно выберем А). А может проводить В (но А мы уже удалили).
Нет, это не то: в В мы можем попасть и из 0. Вообще, там действует транзитивность, так что удаление каких-либо вершин — это не страшно.
А можешь проверить на этом тесте... последних я уже на нём добивал. Ответ: 24.
построим граф, кто кого может "прикрывать". i прикрывает j тогда и только тогда, когда один из кратчайших путей от 0 до j лежит через i.
а теперь я раздваивал вершины и строил паросочетание
Интересно как решается 1000. Хотелось бы узнать =).
у меня 5-мерная динамика =) может, есть проще. если пройдет — расскажу
UPD: не прошла, жаль, будем искать косяк
Решаем динамикой по дереву. Считаем три значения
Сколько стоит покрасить все поддерево.
Сколько стоит покрасить все поддерево, если мы знаем, что предок жарит бомбой (не обязательно сам, главное, чтобы в нашем направлении)
Сколько стоит покрасить все поддерево, если мы знаем, что предок ждет нас что мы прожарим бомбой из поддерева в предка.
Но конечно переходы правильно вбить это то еще волшебство.
Ну ПОЧЕМУ я так и не научился челенджить?
;)
Ага, у нас тоже много 250-к с виду правильных упало. Я даже не подозревал, что там есть какие-то частные случаи.
Проблемы надо решать в порядке приоретитов. Твоя текущая проблема не научиться челенжить, а рассмотреть возможность перехода с ПО, которому уже декада стукнула.
Как ты там ПО разглядел? Я там вижу только cmd, арену и хром, остальные не узнаю.
Он про Windows XP говорит, как я понял :)
Меня ХР полностью устраивает и в ближайшее время я не собираюсь юзать какую-нибудь другую систему
Это не проблема.
О, мессадж, что-то не так с 550... да, слишком много прошло, добавьте ещё фэилдов...
В admin lobby творится нечто интересное...
В админской комнате проскочил тест на полкуска, который убивает все решения, включая авторское
Edges are 0-1, 1-3, 0-2, 2-3, 3-4, 4-5. Our solutions return 2 but correct answer is 1
N = 5, забыл добавить
кстати, при N = 5 почему-то не получается сделать ответ 1, но зато при N = 6 получилось
Почему не получается? Просто 5 пройдет без прикрытия 2 раза.
ах, вот оно что
ну тогда совсем жесть какая-то
а N = 6 некорректно по условию, так что игнорьте коммент выше :)
Конечно ошибкам авторов радоваться плохо, но у меня настроение поднялось... а то все сдали, а я даже близко к решению не подошел...
[rng_58]> if no one can solve 550 in 24 hours we will unrate the match
Круто сделали :) sarcasm
У меня такое чувство, что если матч будет рейтинговым, то в мире станет одним миллионером больше.
http://apps.topcoder.com/forums/?module=Thread&threadID=742353&start=0
По-моему тут какая-то лажа. Ответ 1 никак не получается. Да и перехода из 1 в 3 нет.Исправили.
О, то есть я не зря забыл про СРМ и отоспался? :)
Раунд уже объявили нерейтинговым или ещё ничего не понятно?
Объявили. Для 1 дива только. здесь
Да, объявили, на третьей странице: