Сегодня в 1900 по Москве.
Время в других часовых поясах.
Сегодня в 1900 по Москве.
Время в других часовых поясах.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Как решать 550? Немного похожа на независимое множество в транзитивном замыкании.
так оно и есть. 1533 с тимуса — боян [||||||||||||||||||||]
убиваем всех девок что принадлежат какому-нибудь циклу, а затем 1533.
тогда вопрос, как решать 1533?)
Failed System Tests :( видимо я матрицу не проинвертировал, спроси у кого другого :(
google dilworth theorem
Просто максимальное независимое множество NP полная задача сама по себе, или тут другое?
максимальное независимое множество в DAG (Direct Acyclic Graph) после удаления циклов у нас останется DAG
google dilworth theorem
кто-нибудь сдал тернарник в 250?
да ты упоротый.
согласен
как тернарником ее решать?
Никак. задача на два if.
зашло в дорешке. так что выкусите
1000: представим числа в двоичном виде. Пройдемся гауссом прямо и обратно, пусть результат это A. Возьмём XOR строк, пусть это S. Ответ — сумма по i : S xor (i==0?0:A[i])
550: макс. антицепь = мин. покрытие путями = N минус макс. паросочетание в раздвоенном графе. Циклы? Пофиг на них. Если девушка сама себя может защитить, то в графе являющимся замыканием есть такое макс. паросочетание где все такие девушки идут в самих себя, а значит не влияют.
Эх, если бы не было бы тупой ошибки в паросочетании (khun(i) -> khun(M[i])) , было бы седьмое.
А как именно в 550 граф раздваивать?
Так
А как в 550 после этого восстанавливать ответ, если я хочу узнать, какие именно вершины брать?
Не знаю, может вот здесь написано: http://en.wikipedia.org/wiki/Dilworth's_theorem
Тоже очень интересует этот вопрос.
Придумал craus.
Сразу дополним граф до транзитивно замкнутого. Покроем путями. Теперь нужно на каждом пути выбрать ровно одну вершину антицепи (если на одном пути две вершины — они конфликтуют, если ноль — их мало).
Сначала выберем все вершины, являющиеся нижними концами путей. Теперь, пока в множестве выбранных есть конфликт — пара вершин (A,B) такая, что существует ребро из A в B — заменяем вершину B на ее непосредственного предка в пути.
Почему это корретно? В частности, почему мы уверены, что вершина B никогда не оказывается верхней в пути при попытке обращения к ее предку? Заметим, что любая операция замены была обязательной. Это значит, что если на каком-то шаге вершину B пришлось заменить на предка, то B не может принадлежать никакой наибольшей антицепи (можно доказать по индукции). Получается, что если на каком-то шаге мы не можем совершить операцию замены, то на пути этой вершины вообще нельзя выбрать элемент антицепи, что противоречит Dilworth's theorem.
Что неправильного в моём решении 550: в топологическом порядке запускаем от ещё не рассмотренной вершины dfs и добавляем эту вершину в ответ, если на неё никто не сослался в процессе обхода?
Ромб.
А можно поточнее?
Одна девушка защищает двух, которые защищают ещё одну. Вот этим валили всякие левые решения.
NYYN NNNY NNNY NNNN Ответ 2
Круто, спасибо!
Тест:
NYYY
NNNN
NNNN
NNNN
NNY NNY NNN
или
NYY NNN NNN
В 550 заходит перебор. Только у меня была лишняя оптимизация, из-за которой TL. И даже очевидно почему. Вот отстой.
А как перебирал?
Просто ищем антиклику. Надо запоминать + перебирать по порядку. Дает
.(
— это логарифм от map). Это видимо где-то на границе прохода Поэтому я зачем-то дописал выбор вершины после котрой останется самая маленькая маска. Но я тормаз, и при этом к чертям ломается оценка. А так проходит.
У меня тоже перебор с запоминанием, но хитрый — если из вершины достижима только одна, то ее всегда берем (вершину, а не та, которая достижима). Перебор ведем в порядке топсорта. Проходит очень быстро
Без какого-нибудь перемешивания вершин такое все равно опасно сдавать.
Вот, например, нехороший тест
Этот тест был в челленджах? Просто у меня 37 мс на макс время, мне Ваня сказал
Видимо не было, если решение зашло.
Просто обычный перебор падает на тесте с одной такой диагональю из Y, вторая такая же по идее должна убивать эту эвристику.
А не такое, ли решение должно зайти? И как увидеть почему задача слетела?
Ага, я взял код из условия одной задачи Burunduk1 с его тура в Харькове в 2011 году, добавил туда мап, случайно перемешал вершины и оно прошло c макс временем работы 78мс.
Зачелленджил решение в практис руме, неужели оно проходило систем тесты? Сам сначала написал довольно медленный перебор, потом сделал ресабмит, чтобы его ускорить, но в итоге добавил тупой баг.
Это да, прошло. А с random_shuffle валить умеешь?
P.S. yeputons говорит, что у него прошло без запоминания но с отсечением по ответу.
С random_shuffle или жадным упорядочиванием можно доказать, что не валится.
Так казалось бы тоже есть оценка, которую я выше писал. Или ты ровно в нее и свалил?
И как же доказать, что не валится мой рандом? :) http://community.topcoder.com/stat?c=problem_solution&rm=314422&rd=15179&pm=12080&cr=22740438
Можно свалить с вероятностью 0.35 тестом из 10 таких кусков
Матожидание за челлендж 1.25
Ага, спасибо.
Мой слив