This is a gentle reminder to all coders that SRM 537 is going to happen on the coming Saturday i.e. 17th March.This round is sponsered by CITI ,so there is a total purse of 5000 USD.So gear up and get ready for the challenge.You can find the round details and timings here. You can get the exact prize divisions and a bit of discussion on the SRM on vexorian blog here.
A couple of SRM's back ,the registeration limit of 2500 members was reached some 5 minutes before the closing time.So dont be late or else you may miss a chance to grab some money. Good Luck and Best wishes to all :-)
Please notice, that DST is already in force in USA, hence for most of the world SRM would be one hour earlier then it is common for Saturday SRMs
And one hour overlaps with COCI :( http://www.hsin.hr/coci/
There are no more spots available =( 2500 registrants.
And new MLP episode after challenge phase! YAY!
UPD. mistaken, it was at the same time as SRM :(
Пойду что ли новый вчерашний South Park посмотрю...
Я смотрю любителей антропоморфных пони среди программистов больше чем круглоформатных американских школьников :-)
Nope. Your post was written in russian.
I like SP too :)
У меня одного весь раунд тупила арена: сначала я не мог посубмитить, потом раз 5 арена просто отрубалась?
У меня вроде ОК.
у меня такого не было)
У меня тестинг работал секунд по тридцать.
У меня челенж-фаза была испорчена ей :(
Как делать middle?
Побитово.
я считала вероятность 1 для каждого бита каждого из чисел надеюсь пройдет по точности
Решаем задачу для каждого разряда в отдельности, т.к. матожидание линейно.
Считаем динамику — D[k][i] — матожидание значения выбранного разряда i-ой комнаты к k-ому ходу. Оно, очевидно, равно (D[k — 1][prev[i]] + inv(D[k — 1][i])) / 2, где inv(x) это либо 1 — x, если соответствующий разряд в i-ой маске для первого заклинания — единица, либо просто x.
Спасибо. Ацтой, я не знаю очевидных основ теорвера.
Мог бы и походить к Райгородскому на пары, он же первое, чему учит наизусть — матожидание линейно, матожидание линейно :-)
Я бы с радостью, но, увы, у нас теорвер только на втором курсе.
Я писал динпрог по четирем параметрам: f(room, day, bit, value) — какая вероятность того, что количество после day дней bit-ый бит в комнате room будет иметь значение value
Как нормально решать первую в div1? Ато вторую написал, а на первую только чушь какая-то в голову приходила.
Перебираем Y. Достаточно, чтобы можно было собрать числа A и B. Проверяем все возможные коэффициенты в линейной комбинации pX + qY до 200 с небольшим.
мда, все так просто...
Чувствую себя идиотом %)
Я запихнул в массив все возможные A*p+B*q до p, q ≤ 200 и проверял Y до 200 =) Почему собрать A и B достаточно?
Потому что, если мы можем собрать А и B, то логично, что мы можем собрать все остальное, что собирается при помощи А и B ;)
Пусть вы собрали A и B, тогда pA+qB вы собрали, взяв в p раз больше "ингредиентов" для А и q — для B
"Чувствую себя идиотом %)"
Моя очередь...
тогда, подставляя представление для А и В в виде линейных комбинаций X и Y и раскрывая скобки, получаем представление любой линейной комбинации A и B в виде линейной комбинации X и Y
Соображение: достаточно проверить, что не пропала возможность набора у всех чисел до A*B <= 40000. Насчитали вектор достижимости (можно ли взять число или нет) относительно {A, B}. Это делается за A*B. После этого перебираем Y от 1 до 200 и смотрим, что список достижимости не сузился.
такое ведь тл-ится?
40000·200 = 8 * 106? Не думаю. Нам надо 200 раз посчитать достижимость, что делается за A·B
200^3 — восемь миллионов. С чего бы ему ТЛиться.
Почему же? 200 * 40000 — вполне нормально (200 — перебираем Y, 40000 — насчитываем достижимость).
Оно даже прошло систесты.
тесты — ужасны! у меня прошло решение за ~200^4, для которого я знаю очевидный тест, на котором оно TL-ится :(
А сильно TL'ится? Сервера на TC хорошие.
dolphinigle and I collaboratively wrote the problemset together. We hope the problems were interesting for you all :)
Cool problemset, thx! Very mathematical problems :-)
Ух ты, я впервые в жизни сдал все три задачи!
А как решалась 1000?
Как обычно, рассмотрим граф, где вершины соответствуют числам от 1 до M. Доминошки — ориентированные ребра. Нам нужно найти там самый длинный цикл, проходящий по каждой группе кратных ребер хоть раз. Иными словами, нам нужно выкинуть из графа как можно меньше ребер, чтобы он стал эйлеровым и чтобы в каждой группе кратных ребер осталось хоть одно. Посчитаем для каждой вершины разность между исходящей и входящей степенью. Выкинем по одному ребру из каждой группы. Добавим две вершины — исток и сток. В вершины с положиетельной разностью степеней пустим ребра из истока такой пропускной способности, какова разность; с отрицательной — в сток. Всем ребрам присвоим стоимость 1. Найдем min cost max flow, его стоимость — сколько ребер надо удалить.
каким образом достигается связность полученного эйлерового графа? почему ответ у тебя не получится состоящим из нескольких компонент?
Например за счет условия что всех ребер надо взять по одному.
Я отдельно проверяю связность неориентированного графа, состоящего из всех неизолированных вершин и всех прямых и обратных ребер. Еще, если поток не смог насытить все ребра из истока, ответа тоже нет.
А я под чертой. Призы первому, я второй. Самая обидная позиция. Приятней было бы третьим в комнате быть, что уж тут... Хотя приятно, что впервые в жизни 2ой в комнате div1 (до этого был только третьим несколько раз), но все же...
Какая разница? Чтобы их получить надо заплатить налогов и за пересылку большую сумму :) Впрочем, за мое первое место видимо вообще на благотворительность пойдет. Тем лучше.
Приятно само ощущение формального приза. Я понимаю, что я могу те же деньги заработать без проблем фрилансом или еще каким-то другим способом, но это "не интересно" :)
Когда я получал, то платил только комисию в банке (вроде как ~ $5)
Может быть. Мне говорили про как минимум подоходный налог США, и N долларов за пересылку. Мне что-то подсказывает, что должны быть какие-то еще местные налоги, хотя не факт.
местные налоги 1 процент скорее всего