Сегодня, 12 января, в 21:00 по Московскому времени состоится TopCoder Single Round Match 566
Посмотреть время в вашем регионе
Всем удачи и успешных взломов! ^__^
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
29:55:24
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
29:55:24
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 11:39:36 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
У меня одного арена не грузится?
У меня все отлично работает.
У меня нормально. Возможно тебе надо ее перекачать, если ты давно не писал (они ее обновляли).
Я прямо с сайта запускал... Уже залогинился, вопрос снят.
Похоже RAD стал первым таргетом из Саратова. Congratulations!!!
Спасибо!
Пришло письмо об очередном SRMе... Остались двойственные впечатления от прикрепленного видео:)
Random факт: предыдущий SRM, где никем не была решена 3я задача в обоих дивизионах сразу был SRM 406, прошедший 17 июня 2008 года.
А ведь хард то совсем несложный. По модулю тупейшей ошибки (+= вместо |= в проверке цветов) у меня все было готово через 3 минуты после окончания кодинг фазы, а я сегодня очень сильно тупил
Ну да, без ссылки на решение коммент безсмысленный
Как 500 решать-то?
Там вроде симметричные матрицы получаются поэтому их можно за O(n^2) перемножать. Правда я не понимаю почему ограничения 350. Upd: симметричные в смысле каждая строка получается циклическим сдвигом предыдущей.
Заметим, что от чисел нам важны лишь их остатки по модулю N. Поэтому, считаем сначала простую динамику D[i][j] — сколько способов добраться в состояние j (т.е. сдвинуться на j шагов из какой-либо позиции), используя числа 1, ..., i. С ее помощью мы знаем значения для полного периода из N шагов; теперь по целым периодам делаем возведение в степень (склеиваем две динамики за квадрат: C[i] — сумма по всем j A[j] * B[i - j]), а остаток набираем с помощью склеивания и той же простой динамики.
По сути перемножаются не матрицы, а многочлены.
С такими ограничениями люди могли пытаться оптимизировать O(N3) * log(d). А если поставить 1000, то там уже без шансов и никто бы не сабмитил ТЛ-ящие решения.
Надо сказать что и при 350 (N^2)*log(d) работает довольно долго, у меня 0,7s, конечно, можно было писать намного аккуратнее и работало бы раз в 10 быстрее, но это все же не стиль TC.
А как перемножать симметричные матрицы за O(N^2)?
Там важно не то, что они симметричные, а то то что циклические (следующая строка — сдвиг на 1 вправо предыдущей тут ) и произведение двух таких матриц — снова циклическая матрица
А, понятно. Я раунд-то не писал, а как перемножать именно симметричные, без всяких дополнительных свойств, матрицы, я не знаю (и мне кажется, что это нельзя сделать быстро)
Дело не в симметричности, а в том, что на всех диагоналях там стояло одно значение. Типа a[i][j] = a[i + t][j + t]. Такие матрицы правда можно перемножать за квадрат. Достаточно вычислить первую строку результата и записать ее в другие строки результата, циклически проворачивая.
Я это имел ввиду.
У меня O(N^3) чистый на Java не заходил. Чтобы он зашел, нужно было похачить константу, например в перемножении матриц, модуль брать не каждый раз, а накапливать long до предела и только тогда брать модуль. Дело было уже в самом конце, и я до этого не дошел.
Это мне скрасило впечатление от всего SRMa.
А как тут O(N^3) сделать?
Можно остаток считать не за квадрат, а за куб, перемножив O(N) матриц, при этом делая каждое умножение за квадрат.
Можно поподробней? Если у нас уже есть матрица для блока длины n, как учесть, что этот блок входит
раз?
У меня было следующее. Одномерный массив показывал сколько есть способов добраться из 0 города в x-ый. И была одна функция (N^2), которая к одному массиву, применяла другой, по сути складывая длину маршрута. С помощью этой функции я и делал с помощью них период, но поскольку мне было лень писать новые функции, я и начальный массив для длины n считал прибавляя по очереди n массивов вида (a[i] = 1, a[N-i] = 1, a[всё остальное] = 0). Отсюда и N^3, но почти ничего не писать дополнительно и до кучи, после одной из таких итераций мы автоматом получим и массив остатка.
т. е. вы эту задачу умеете решать для d = 10100 ?
Нет, извиняюсь, конечно имеется ввиду разница между O(N^2 + log D * N^2) и O(N^3 + log D * N^2). То есть логарифм никуда не девается, но доминирующей частью если пренебречь эффективностью в первой части становится N^3 (при данных ограничениях).
Довольно удобно в самом внутреннем цикле брать по модулю 1 000 000 0072 ифом и вычитанием, а в конце цикла один раз брать по настоящему модулю.
Div1-500 is pretty much the same as problem C from NEERC 2006/2007:http://neerc.ifmo.ru/past/2006/problems/problems.pdf
Скринкаст: http://youtu.be/1lRsTXK2wbM?hd=1
Особенно удались последние 10 минут кодинга — тупое всматривание в код харда в поисках баги, потому что не проходит последний сэмпл, а баги в итоге не было. В итоге оказалось, что я не заметил в условии, что в каждом загоне должен быть хотя бы один пингвин.