Примерно через 25 минут начинается очередной SRM. До закрытия регистрации еще 10 минут.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Название |
---|
OK :(
как решается div1 500?
Возьмём множество из всех атомов. Найдём отсутствующее ребро, у которого оба атома в множестве. Понятно, один из них надо исключить, переберём какой, уходим в рекурсию. Если всё ок — берём сумму атомов во множестве и улучшаем ответ.
Так как мы можем исключить всего 16 атомов (50/3) , то и ветвлений всего 2^16.
Должен работать такой перебор: Берем все вершины и находим наименьшую пару (i, j) что между i и j нет ребра. Рекурсивно перебираем, выкинув либо i либо j. Т.к. глубина не больше n/3, получаем O(2^(n/3))
Еще можно
или даже ![](https://espresso.codeforces.com/a6789789ff550e4c27de18a2b19f543ddea89a55.png)
Будем решать задачу на дополнении. Тогда это найти вершинное покрытие размера не более чем. Тогда вершину степени <= 1 мы точно не возьмем. А иначе можно либо взять, либо не взять. Тогда удаляется либо вершина либо два соседа. Получаем рекурентность на Фибоначчи.
А можно отдельно разобрать случай всех циклов. Тогда будет выкидываться хотя бы три вершины в одном из случаев.
Да, точно. Я примерно так решал http://acm.timus.ru/problem.aspx?space=1&num=1695
А там то оно что даст? 1.61n?
. Просто добавить запоминание к перебору.
Есть же халявный
1.61^n с мемоизацией работает намного быстрее чем 2^(n/2), и видимо это единственный способ сдать эту задачу на Java :)
Посоны, посоны, алгоритм с Википедии заходит? Говорят, работает за O(3^(n/3)), у меня два дефенда и единственная выжившая 500-ка в комнате.
UPD. Не заходит :(
где n — количество максклик(которые нельзя увеличить)
автор ниже прав, я не умею читать :(
где n — количество вершин в графе
У меня алгоритм Брона-Кербоша зашел в практике после отсечения (если кандидатов не хватит на достаточно большую клику), максимум 684 мс. Подскажите, это дырка в тестах или правда этого отсечения достаточно? http://pastebin.com/icARB4fb
Из моего кода в 250-ке внезапно пропала строчка, которая добавляла .mp3 в конец всех названий. То есть, сначала я действительно ее не добавил, но потом добавил и отослал. У кого-нибудь что-нибудь подобное было? Пользуюсь kawigi.
compile нажимал, или только run tests?
черт, это возможно. обидно. очень странно, что оно не напоминает о том, что я отсылаю неактуальный код. спасибо.
Буду благодарен если напишете Div2-1000 :)
я так понимаю она идентична div1 500? Она обсуждаеться выше
Для начала создадим порядок в обходе всех ребер. Теперь пустим рекурсию по состоянию. В начале у нас пустое множество. Пусть на каком-то шаге у нас образовалось мн-во А, |A| = t. Найдем все ребра вершины которых не лежат в A. Если таких ребер не нашлось, то из вершин не лежащих в А возьмем k-t вершин с максимальным весом добавим и обновим ответ. Иначе возьмем первое ребро и закинем сперва первую вершину, а затем вторую. В итоге у нас получается О(n * n * 2^k).
Быстро однако ответил :)
Кто-нибудь умеет доказывать такое решение 500ки: 20К раз пошафлим вершины и жадно наберем клику?
Казалось бы, падает на полном графе, в котором удалено штук десять ребер.