Соревнование начнётся в 21 июля в 20:10 по саратовскому
Да пребудет с нами Сила!
[Ads mode on] Нечего делать перед матчем? Не забываем про бомбер [Ads mode off]
UPD. Поздравляю Петю и Гену! :)
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Соревнование начнётся в 21 июля в 20:10 по саратовскому
Да пребудет с нами Сила!
[Ads mode on] Нечего делать перед матчем? Не забываем про бомбер [Ads mode off]
UPD. Поздравляю Петю и Гену! :)
Название |
---|
После поста про коллизии хешей начали возникать коллизии среди анонсов про SRM >_< пусть остается этот пост, тут есть котэ)
Кот педро, ага :)
По такому поводу будет три 550-ых задачи?
только у меня время в арене неверное?
Они же уже разослали, что знают и фиксят.
UPD. Отлично пофиксили!
Спасибо.
Ничего не приходило.
UPD: Вижу теперь
А что-таки произошло? На сайте ничего нет.
Время топкодера стало на 5 часов меньше реального.
Для фикса вместо того, чтобы поправить время, сделали старт контеста на 5 часов раньше.
Э, то есть он уже прошел? o_O
Нет. реально он будет в тоже время. Просто время на TC не совпадает с реальным.
Ну из-за того, что время в арене всё ещё на 5 часов отстаёт -- всё будет как запланировано (в 20:10 Саратова)
Привет всем. Это будет мой первый контест на топкодере. И я, честно говоря, не совсем разобрался что там да как. Если кому не сложно, пожалуйста, опишите вкратце то, как проходят там контесты.
Почитайте вот это.
Большое спасибо)))
Я понял)
Как решать 850?
Вычисляем мин. стоимость, проверяем что maxCost на неё хватает, смотрим сколько раз можно ещё сделать цикл a->b->c->a , пусть минимальное число ходов это moves, и можно сделать cycles циклов.
От текущего слова нам нужно три параметра: сколько букв совпало, скольким нужна одна замена, скольким две. Итого состояний порядка N2т.к. их сумма это N.
Когда мы делаем замену, состояние меняется линейно. Берём соответствующую матрицу, добавляем туда строчку куда будем писать сумму для состояния (N, 0, 0), возводим в степень moves+cycles+1 и смотрим в клеточку соотв переходу из начального состояния в сумму, там будет ответ.
Осторожнее, сумма costi и минимальная стоимость может вылезти за int.
Жадность фраера сгубила.
Расскажите, как третью делать? Свёл к умножению многочленов длины 10^9 / 3, узнал, у какой функции ряд Тейлора , но так задачу и не решил. В решении чувака из моей комнаты, которое я не смог завалить, было какое-то двоичное масштабирование.
Смотри выше.
УГ раунд.
А мне норм.
Ну как, первая — ничем не примечательная реализация, вторая — "или ты увидишь C(n, k) и знаешь как его быстро считать по модулю два, или нет", а вот третья вызывает интерес.
Эм, расскажи про цешку? Решал как-то кажется совсем по-другому
Упс, допер идею, ок.
У тебя получился красивенький фрактал. После некоторого афинного преобразования (кажется, прямую y=x надо перевести в прямую x = 0) получится треугольник серпинского, или, что то же самое, в точке (x, y). А дальше магия: C(n, k) чётно тогда и только тогда, когда (k | n) == n.
Ага, спасибо. не заметил сходу Cшки, проверял шаманской рекурсией)
Когда я решал вторую то я не заметил связь с Cnk). Просто понял что это фрактальчик. Хотя да, по формуле она сразу видна.
Автор математик. 300 — реализация как реализация. Туповатая слегка, но вполне жизнеспособная. А дальше надо думать. Тут это почему-то не любят. Хотя давать 500-ку на "либо ты умеешь проверять Сшку на четность магическим выражением
(n&k) == k
либо убиваешься любым доступным тебе способом это действительно не очень хорошо.Вау, а я всегда делал это рекурсивно по треугольнику Серпинского за логарифм.
Офигеть, эта штука еще как-то называется! Я когда вывел правильные формулы, время уже кончилось...
Кстати, треугольник Серпинского за логарифм хорош тем, что обобщается на произвольный модуль вместо двойки. Вот даже задача об этом http://projecteuler.net/problem=148 .
Я хоть и подозревал, что простая формула за О(1) должна следовать из теоремы Люка, но на контесте кодил за логарифм методом, который всегда использовал. Возможно, это и есть решение по треугольнику Серпинского.
Идея состоит в том, чтобы найти степень вхождения в числитель и знаменатель формулы подсчета C(N, K). Если степени равны, то оно не делится на 2, иначе — делится. А проверить степень вхождения числа p в N! можно одним циклом:
А можно, в таком случае, объяснить решение 500?
UPD: Спасибо
Можно.
0. Клетки с нечетным (x+y) и x < y пустые. Это очевидно из формул.
1. Оставвшиеся клетки представляют собой треугольник. У клетки есть две предыдущих — как раз описанные в условии.
2. Клетка либо пустая, либо ее цвет зависит от чего-то вроде .
3. Из формул в клетке записан ксор предков. Что тоже самое .
4. По простому модулю цешка равна произведению цешек по разрядам в p-ичной системе счисления. Это проверяется явным вычислением. По модулю 2, это значит, что она 1, только когда все биты в k не больше чем соответствующие в n. Что тоже самое
(n&k) == k
.Спасибо!
Не совсем понятен пункт 3. Почему ксор понятно, но откуда берётся переход к C((x+y)/2, y). Можете обьяснить?
Получающаяся конструкция соответствует треугольнику Паскаля по модулю 2 (т.к. каждый слой на 1 длиннее предыдущего, и значение определяется как сумма двух предков в предыдущем слое по модулю 2).
Вот! То что надо. Теперь понятно, спасибо.
Из комментариев, в общем, видно, что это далеко не единственное решение 500-й. Можно уметь узнавать и считать , можно просто по картинке рекурсию делать, можно, наверное, погуглить треугольник...
Я это и назвал убиться любым доступным тебе способом. Это все представляет собой в той или иной форме проверку остатка цешки.
Ну не знаю... я гораздо больше очков слил на ресабмит int -> int64 в одном месте, чем на придумывание этой рекурсии. А красивую формулу за O(1) только в этом обсуждении узнал.
Я хотел на зимние сборы это дать. Мне сказали что баян :)
Не понравилось, что третья задача была 850 (первый раз вы жизни вижу на ТС, чтобы третья задача стоила меньше 900) — то есть, очень простая для третьей. А реально она по сложности была не проще обычных.
Разминусуйте меня!
Сейчас это сообщение заминусуют. Я снова челленджил, перепечатывая код. Действительно очень удобно. Сегодня успел просмотреть 2 решения по первой задаче. Одно зачелленджил тестом
{1,1,2,2,3}
, второе упало на сэмплах, поэтому я начал еще раз проверять код, и время кончилось. В общем, это и вправду выгодная тактика.Забавно, вчера было -12, сегодня уже +10...
И очередной слив: http://www.youtube.com/watch?v=6OagOnDW7F0&hd=1