Сегодня в 20.00 по МСК состоится очередной SRM. Будем надеяться, что он пройдет без каких-либо заминок. Желаю всем удачи.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 09.11.2026 15:36:19 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
а все ли клавиатуры в казахстане имеют русскую раскладку?
Существуют виртуальные клавиатуры.
Блин, теперь я капитан...
Я один не могу зайти в комнату?
UPD: Отлично, зашел, зато теперь не могу открыть задачи.
Перенесли на 15 минут
а вообще даже не с ареной, а с java 1.6.0_29)
Хм. Ты меня смутил своим линком. С другой стороны, я там же нашёл, что MSK теперь вообще deprecated - http://www.timeanddate.com/library/abbreviations/timezones/eu/msk.html
Так что не у одного меня неправильное)
Сдвинули на 8:17 по Москве.
Надеюсь, room assignment останется прежним.
Ну вот почему нельзя заранее с запасом выделить время для распихивания по комнатам?! Уже ведь много раз распределение с трудом укладывалось в отведенное время, и рано или поздно оно должно было не успеть.
Вот бы ещё ничего не упало.
Я присоединяюсь, фонд перестает быть анонимным.
Первый раз в жизни написал вторую, зато прогнал, как и многие, в первой, и еще -25 словил.
А вторая может запросто упасть, локально 1.3 сек работаетне упала, фейл не эпичныйВот это мясо. Я по B в своём духе написал самое сложное, что только может прийти в голову. Динамика за 2(n / 2) * n3 с пятью оптимайзами тащит :-)
В результате угрохал время контеста куда-то в задни^W чёрную дыру.
40 * 20 * 20 * 2^20 * (лонг лонги повелевае!1) = полтора миллиарда операций с лонг лонгами. Я это очень долго и со скрипом впихивал.
У меня критичный макстест - когда нулей и единиц по 20 и они разбросаны по строке.
У меня есть отсечение, которое проверяет, что очередная маска по количеству нулей и единиц подходит исходной строке. А на таком тесте единственная подходящая маска - это в которой все нули.
Возьмем первые n/2 символов, далее для каждой маски:
Найдем начала строчек a и b, которые войдут в x и y.
Пусть для определенности a длиннее b. Тогда если a[1..blen] == b[1..blen], обновим в мапе, сколько раз встречается строчка a[blen+1..alen].
Потом проделаем почти такую же операцию для вторых n/2 символов и второй мапы. Только там надо кое-что реверсить.
Далее пройдемся по всем строкам из первой мапы и попробуем найти их во второй. Если получилось, прибавим к ответу m1[s]*m2[s].
Еще, конечно, строки можно делать числами, а мапы - массивами (последнее я не успел). Получается за O(n * 2^(n/2))
Я так примерно делал.
И там не просто посчитать сколько раз такая строка была, а надо еще вроде сохранять какая именно строка была длинее и потом sum( m1[<num, s>] * m2[<1 - num, s>]. И отдельно учесть пустые строки.
Да, это я учел. У меня локально работает 1.3 сек, и почему-то кажется, что мой Core 2 Duo E6600 четырехлетней давности побыстрее их компов
UPD: Зашло. Жаль, с 250 протупил
Есть некоторое решение, не уверен что правильное.
не понял пункт b, честно говоря
Но я прочитал его только в последнюю минуту и послал какую-то жесть, которая меня удивит, если пройдёт систесты.
Идея решения у меня такая: смотрим на цвета по очереди и для каждого решаем, сколько раз отнять от него P1 и сколько раз отнять P2. Считаем динамикой ответ для состояний (количество просмотренных цветов, сколько у нас свободных P1-ок, сколько у нас свободных P2-ек).
Я делал динамику f(i, mx, opened) -- максимальное количество раз, которое мы можем отнять P2, если мы отняли P1 ровно opened раз, максимальная сумма количества отниманий P1 и P2 для одной коробки равна mx, и всего мы обработали i коробок.
У меня такое без отсечений немного не укладывалось по времени. Прошло только с проверкой на корректное кол-во единиц в маске, совпадение первого символа и первого бита маски, совпадение последнего символа и последнего бита маски.
я делала даже C(18, 9) — первый и последний фиксированы, отсечение по нулям в слое динамики и по кол-ву, как у Вас. На макстесте как-то быстро работало, надеюсь по wa не свалится — не особо проверяла свой код
upd: ня, прошло
Можно всунуть пересчитывание динамики в перебор маски так чтобы было 2n· n а не на n2. Работает 1,2 стабильно на 40.
один я решал meet-in-the-middle?
Я делал тоже meet-in-the-middle. Достаточно заметить, что если в левой половине у нас маски (A, B) для синих и красных, а во второй (X, Y), то должно выполняться:
У меня был N/2+1 массив масок, в, к примеру, left[i] хранятся разности, у которых ровно i элементов принадлежат красной поcледовательности. Сливаю массивы left[i] и right[n/2 - i] для всех i. Вроде должно работать.
UPD: Разобрался. Глупая ошибка в реализации - сравнивал Long между собой оператором ==, а не .equals(), как следует.
UPD2: При том, что интересно, сэмплы проходили прекрасно, ибо для маленьких значений Long все объекты закэшированы, и прекрасно сравниваются через ==. Обидно.
Я просто шагал с шагом 0.01 и считал максимальное количество для текущего времени.
Я решал так:
> Тут требуется определённая эпсилон-кунг-фу, я не придумал как её избежать.
Так как все скорости разные, считались такие точки очень просто.
Добавляем момент времени 0, и для каждого момента считаем сколько максимально москитов находятся на отрезке длиной 2R.
Test Arguments
a <= b -> a < b+eps
a == b -> abs(a-b) < eps
a >= b -> a+eps > b
a > b -> a-eps > b
Главное - считаем, что числа равны, если abs(a-b)<eps. Если есть сомнения, надо на бумажке нарисовать, станет все ясно.
вопрос в том, когда они начнутся...
UPD: опередили...
Когда систесты начнутся?
upd: Ого, видишь, этот вопрос всех куда больше интересует!
Ура! После 99-го своего SRMa я стал наконец-то красным!!!