Копись вкладик.
Соревнование начнётся в 9 февраля в 20:00 по саратовскому.
Да пребудет с нами Сила!
UPD. Артём крут!
Копись вкладик.
Соревнование начнётся в 9 февраля в 20:00 по саратовскому.
Да пребудет с нами Сила!
UPD. Артём крут!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 164 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
По Питерскому! =)
По Рыбинскому! =)
А в D1 450 правильна ли такая динамика: dp[prefix][edgesleft][mask], где mask маска четности последних K?
Да. Нужно только учитывать кратные ребра.
Спасибо, просто я не успел закодить :) А кратные ребра надо учитывать с помощью сочетаний, да?
Да, причем это лучше делать в самом конце, а не в переходах динамики.
эх, походу из-за этого я и не успел докодить, как-то и не дошло, что лучше это делать в конце
А я учитывал при переходах в динамике, вот только она не прошла из-за маленьких массивов:(
Как тогда тут правильно делать переходы, чтобы не было проблемы, которую я описал ниже? Я в итоге запихал четырехмерную динамику.
у меня были долгие переходы (за m * 2k), поэтому не зашло.
UPD а как быстрее делать переходы?
Я не смог довести ее до ума. Проблема вот в чем (уточню сразу — я делал динамику вперед, хотя это не должно быть важно). Мы можем прийти в одно состояние несколькими способами. К примеру, в d[3][0][011] можно прийти из d[2][1][101] и из d[2][1][110]. Переход посчитается дважды, хотя картинка одна.
Надо просто упорядочить переходы, добавив состояние, в какую мы сейчас хотим добавить ребро.
Что это значит? Разве в динамике мы не добавляем варианты через прикрепления к последней вершине нового ребра?
Все равно не понимаю. Я добавил еще одно состояние — минимальный левый конец ребра, которое мы можем поставить. Таким образом, по модулю кратных ребер получается всего два перехода — мы либо ставим ребро, либо не ставим. Заработало секунд за 20 до конца, успел даже засабмитить. Но это четырехмерная динамика, а все вроде бы трехмерную писали.
Да, я имел ввиду ровно то что сказал ты, только я себе это представлял с другого конца. У меня 4-ех мерная.
forest, RAD, признавайтесь, на чем поломали?
в моей комнате многие ломались на тестах из одной строчки — <<.9.>>, <<9.9>> и <<999>>
Ага, я на тесте "5.." ломаюсь.
А 450 на том что массив больше 64Mb, сразу c SIGKILL валится в арене
Ага. Не знал, что так мало памяти, думал 256 не пожалеют. Потестить не успел, сабмитил за 40 секунд до конца. И все равно там еще и WA было.
У меня человек как-то странно не симетрично обрабатывал концы и свалился на {".45","123"}
333 ..3 я вот так ломал
А у меня один человек делал так. Если строка имеет вид x.y, то он добавлял тот конец, который больше.
жадина detected :D
Во второй задаче див2 троих сломал на тесте 8.9, у самого тоже не проходит этот тест, но потому что скопипастил строчку из соседнего цикла и не сменил индекс, обидно, но будет наука впредь:(
Блин я сейчас заплачу. Быстро сдал 300 и 450. Был 30м придумал 1000ю не дописал. Сделал первый в жизни челендж, а за ним и второй. Был видимо в топ25 и упала medium из-за одного символа (8->9)
Такая-же лажа с 450, только 9 -> 10 :) забыл условие
if (p != N)а далее былоd[..][p + 1][...]Какой верный ответ на 111,1.1 ? Почему не 5? Или там эта ерунда получается не круглая?
во-первых она не должна быть круглой, во-вторых нужно найти максимально качественную непрерывную последовательность => 4
Я понял, что раз цепочка, то будет круглая, и специально сделал 5... Блин, третье место ушло и я дальше в div-2 =/
UPD Просто интересно, кто-нибудь еще понял ее так же?
5 челенджей, хорош! =)
Да там еще было 3 неудачных, именно из-за этого неправильного понимания. Если бы правильно понял этот момент, вышел бы на 2 место.
Цепочка — круглая, а цепь — не круглая? :)
Google translate в одном месте сказал, что он делает украшение, а не просто цепь =) Первая же ассоциация, что цепь-украшение круглая.
Ты не один такой. У меня тоже на этом 300ка упала (узнал что она не круглая уже во время челленджа, когда вывод на успешный челлендж не совпал с тем, что я ожидал увидеть).
Можно либо 1111.1, либо 1.1111, обе непрерывные последовательности будут равны 4.
UPD. Не круглая, да.
Засабмитил 1000 в последнюю минуту, на макстесте работала 1990мс :)
рубаха парень ^^
А как решать? У меня динамика за O(n3m2k) работает три секунды. Идея: выразим ответ через ответы для меньших таких же задач, перебрав количество уток первого типа.
Я умею решать за n^2 на количество упорядоченных разбиений m. Это не очень много, только там какие-то веселые коэффициенты из факториалов и цешек лезут. не дописал.
А, то есть это немного? Блин.
Ключевое слово упорядоченных. Их 250000 примерно. Но из-за этой упорядоченности начинаются проблемы с подсчетом скольки неупорядоченным состояниям соответствует это.
У меня O(n2 * m2 * k) Состояние динамики — n,m,k, и сколько утят типа k обязано присутствовать в каждой строке — пусть это A. Переход — перебираем минимальное кол-во утят в каждой строке и количество строк, в которых их именно столько. Ещё хитрость в том что сначала в d[n,m,k,A] хранится кол-во вариантов если A-это то самое минимальное количество, а потом суммированием точный параметр превращается в ограничение снизу.
И еще по параметру k я сжимал динамику по памяти, так как значения для k пересчитываются из k - 1
Если не ошибаюсь, то можно решить за
O(n * m^2 * k + n^2)за 2 функии динамики.Первая функция
f(n)— ответ. Определим количество вариантов первой строки при условии следующий различных между собой, вычтем возможность идентичности первой строки с какой-либо другой, используем формулу включений-исключенийf(n) = f(n — 1) * a(1) — 1! * f(n — 2) * C(n — 1, 1) * a(2) + 2! * f(n — 3) * C(n — 2, 2) * a(3) — ...где
a(i) = g(i, m, 0)Вторая функция
g(n, m, k)— количество способов сделать n идентичных строк длины m, начиная с k-го номераg(n, m, k) = C(m, 0)^n * g(n, m, k + 1) + C(m, 1)^n * g(n, m — 1, k + 1) + ...Сам не проверял, но вроде все правильно. Только под конец раунда придумал
Да, простое решение :)
Что-то изи как-то активно попадала.
Если пытаться решать за квадрат или линию, что делало очень много народу, то код увеличивается в 4 раза и в нем появляется много багов.
Я писал с сортом, в итоге у меня довольно сложный код, ладно, в какой-то момент упростил, и то УГ)
А перебрать все пары i=/=j за квадрат по-моему как раз-таки легко и где там набажить не понятно)
Ага, вот только если в массиве одна строка, это может не сработать. Например, {"11."}. Поломал два таких решения.
о, точно
а, дак вот на чём у меня упало((
SysTest... Up... Up... Up =)
Поздравляю RAD с победой в СРМе!
Артём, сколько ты уже SRM-ов выиграл? Мы сравнялись? :)
Это второй.
Сравнялись :)
Спасибо!
а есть ли возможность посмотреть результаты только по одной стране?
otinn.com тебе в помощь
В последние три минуты отошел кабель, а у меня был готов тест, которым мог всю комнату завалить. Пойду повешаюсь.
Кто-нибудь может помочь с идеей в div 2 950? Знаю, что в div 1 такой задачи не было, но в дивизионе решило только 2 человека, и хотелось бы услышать разные идеи :)
Динамика по профилю.
Аналогично задаче симпатичных узорах.
А на ТС зайдет 2^17*100*8 в 2 секунды? Если да, тогда решение ДП по изломаному профилю, dp[i][j][mask] — где і,j = номер строчки и столбца, а mask — битмаска где хранится чётность клеточёк.
А можно подробнее, почему 2^17 и что вообще в этом случае представляет из себя маска?
у меня было 2^16 * 100 * 8, смотри дп d[rowsCnt][col][mask][cntmask]. rowscnt до 100, от этого параметра можно избавиться просто заменяя массивы, ибо нам нужно только две последовательные "строки" этого массива (d_old[col][mask][cntmask], d_new[col][mask][cntmask]). Каждый слой представляет собой ломаную штуковину типа
000XXXX
XXX0000
в данном случае излом в col = 3, (если от 0 считать). в случае col = 0, у нас первая строка из крестиков, а вторая из ноликов. Крестики представляют собой то, чему соответсвуют биты масок. Первая маска говорит о том, что в данной позиции что-то есть (если соответсвующий бит равен 1) или пусто. Вторая маска говорит для каждого крестика чётность стоящих рядом непустых клеток, из тех, для которых мы уже определили значение. Давай рассмотрим что происходит на примере приведённого выше профиля. Я переобозначу клетки так
000AXXX
XXBC000
сейчас, мы должны назначить значение клетке C, для этого переберём возможные варианты (пусто, занято). Заметим, что если в клетке A не пусто, то мы можем поставить значение единственным образом, т.к. клетка С это последний сосед клетки A. После того как мы поставили сюда что-то (или не поставили) мы переходим к профилю
0000XXX
XXXX000
и нужно обновить или совсем заменить значения некоторых битов в обоих масках. т.к. он соответсвует уже другой клетке. например сейчас это произошло с битом номер 3(если с нуля считать) соответсвовало клетке A, а теперь стал соответствовать клетке B. полное решение смотри в практис румах юзера Alias_Prudaev
У меня зашло N × M × K × 22K = 1000 × 8 × 216. За 1.7 секунды, правда, но зашло:). Так что это и вовсе должно заходить.
So, I hope you enjoyed the problems :)
Вот что я реально не понимаю, так это в чём у меня ботва в 1000... http://community.topcoder.com/stat?c=problem_solution&rm=311450&rd=14725&pm=11766&cr=22452815
может
поменять на
и зайдёт?
Логично предположить, что это число прибавляется в первой итерации последующего цикла
Тогда меняй константу 51 на 52, а то по при minFirst=51 будет выход за границы ДО того как ты проверишь что minFirst>m .
Да, действительно будет. Спасибо.
а по Topcoder'y есть какой нибудь поиск по тегам? Порешать задачи на такие-то и такие-то темы?
Зашёл на топкодер, удивился: почему-то 532-й раунд исчез из рейтингов. На арене так же. Не локальный глюк, вроде. Кто-нибудь наблюдает то же самое?
То же самое. На сайте написано, что следующий SRM — 533ий и будет 18ого. Скорее всего скоро пофиксят.
Там написано 533-й, это верно.