Обсуждаем, интересует решение J.
→ Обратите внимание
До соревнования
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 144 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.10.2026 22:27:53 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
Кому втупую, а кто сначала долго не мог победить ML2, хотя по всем расчётам выходило не более 100 Мб, а потом - TL3, когда на вроде бы худшем тесте (цепочка длиной 2042040) работало 4 с.
OpenCup - хитрый турнир, тут что ни контест, то чудеса :)
UPD. Короче, с пояснениями ниже всё стало более-менее понятно. Но если такие проблемы возникали у пишущих на C (уже даже не на C++!), то я боюсь представить, как пришлось оптимизировать решения командам, пишущим на Java.
Ну, в справедливость TL ещё как-то можно поверить. Но непроход по памяти таки остаётся загадкой. Собственно, вот, например, код. Откуда там 256 Мб?
Или я неправильно понимаю, что при вызове функции на стеке выделяется память только под локальные переменные и адрес возврата?
UPD. Короче, с пояснениями ниже всё стало более-менее понятно. Но если такие проблемы возникали у пишущих на C (уже даже не на C++!), то я боюсь представить, как пришлось оптимизировать решения командам, пишущим на Java.
Интересно, кстати, а можно ли было бы отключить их создание посредством каких-нибудь директив препроцессору? И сильно ли это ухудшило бы время работы?
1) Сгенерим N чисел: a[i] = 1 + количество узлов во всех потомках i-го узла (совсем все, а не только непосредственные)
Заметим, что для каждого делителя n нас интересует количество чисел среди a[i], делящихся на этот делитель.
2) Рассмотрим b[i] = gcd(a[i], N). Как ни странно, он является делителем N. И что самое главное - для любого общего делителя N и a[i] (назовём его k) выполнено условие b[i] % k = 0
3) Посчитаем все различные b[i] (совсем по тупому - будем хранить, сколько раз встретился каждый элемент). Заметим, что различных чисел b[i] не больше, чем делителей N.
4) Научимся для фиксированного делителя N находить описанную перед п. 2 величину. Для этого просто переберём все различные значения b[i] и для тех, которые делятся на выбранный делитель возьмём посчитанное количество их вхождений в b.
Первые три шага - за O(N), последний - за O(D^2).
будем считать клетку матрицы хорошей, если она находится строго внутри некоторой прогрессии как по горизонтали, так и по вертикали. Т.е. a[i][j] == (a[i-1][j] + a[i+1][j]) / 2 == (a[i][j-1] + a[i][j+1]) / 2. Составим матрицу в которой еденичками будут помечены все хорошие клетки и ноликами плохие. Решим стандартную задачу о поиске максимальной подматрицы только из едениц перебирая все нерасширяемые подматрицы из единиц. Очевидно, что все перебраные в процессе матрицы нам подходят. Но помимо них нам возможно подходят и несколько более расширенные матрицы. А именно мы к каждой матрице из единиц возможно можем с каждой стороны дописать ещё по строке(столбцу). Но не более одной. Иначе нашу матрицу из единиц можно расширить. Проверим для каждой нерасширяемой матрицы 2^4 вариантов дописывания строк по бокам. Из всех выберем максимальный.
По крайней мере это наше решение.
Как решать задачу E, написал корневую декомпозицию, получаю WA4?
UPD В дорешке зашло.
Пусть будут события добавить плеер, удалить плеер, после каждого события нужно возвращать сколько новых нор покрыто/не покрыто.
Пусть хотим удалить плеер стоящий в x, найдем ближайщий от него плеер слева и справа, пусть их координаты x1, x2, тогда наш плеер затронет норы на отрезке
[max(x1+L+1, x-L), min(x2-L-1,x+L)]
Номер норы по X, можно искать бинпоиском. Добавление аналогично.
Красивое решение
UPD не туда.
Простой бфс у меня получил ТЛ. Тогда я придумал следующую оптимизацию.
Мне очень интересно, что за тактика была у команды Moscow SU Chapelnik: Shteiner, Panin, Blinov (div. 2), что в середине первого часа контеста они сделали три посылки по трём разным задачам в 0:41, 0:42 и 0:43.
Последняя успешная посылка была в 0:16. Затем во сколько-то одно бревно по Q, и три синхронные (но неудачные) посылки по разным задачам через 25 минут после предыдущего АС.
Может, конечно, два раза задачей ошиблись)
Думал ещё, что может инет отвалился.
Поздравляю с победой в 2 диве! :)
влоб: просто перебираем отрезок, сумму на котором будем брать и смотрим: простая ли сумма?
==============
просто я не понимаю зачем такие огромные ограничения ставить 109 итераций, неужели нельзя обойтись 108 и ограничения на время 1сек
да ничего подобного, оказывается там временные переменные или че то такое: выше написано...
Не заметил, что речь про первый. Может он не условия? Может файлы не убрал?
Можно доказать, что вторая встреча будет до того, как второй дошел до корня, или ровно в этот момент
Если они первый раз встретились строго выше земли (а из условия это всегда так), то левый на обратном пути спустится до низу строго раньше, чем правый. Потому после первой встречи - точно такая же логика, как и до неё, только рассматриваем уже правого муравья вместо левого. Более того, в формулах возникает деление только на 4 и на 5. Поэтому если домножить всё на 400, то можно все расчёты вести просто в лонгах, делить только при выводе ответа.
Если делать всё аккуратно, проблем вроде никаких не возникает. У меня была мелкая опечатка в копипасте, потому сдал только в дорешивании.
Мне одному показалось, что ряд задач див2 сегодня были ненамного проще задач див1 и намного сложнее задач общей секции?
Иначе, выкидываем первый и последний символы.
А зачем первый символ удалять? Последний понятно - потому что он полностью останется в чашке. Я лично сдал безо всякого удаления.
прямо O(n2 * logn) ? не O(n * n + n * loglogn) ли?
иначе полный бред с ограничениями, имхо
По-моему, контест был на удивление ужасен. Видимо, это отличительная черта польских контестов: на варшавских контестах неасимптотические оптимизации можно не упоминать - они чуть ли не в каждой задаче нужны. Отсюда заоблачные ограничения и неясное понимание того, а какое решение заходит.
Если решето поставить до 10^6, то проходит и в дорешку.
А вот в D пришлось писать хитрый ввод - я, например, читал fread'ом блоками по 1мб.
Я долго подбирал константу
Решение будет получать TLE, даже если избавиться от dfs'а. Там вся веселуха с кэшем во время обхода дерева.
По-моему, такие контесты не нужны. Посмотрите на задачи с NEERC, на задачи этого саратовского четвертьфинала, на последние несколько контестов на Тимусе. И потом на этот. Неужели так увлекательно загонять шаманские оптимизации под 10 миллионов ввода и 15 секунд тайм-лимита?
Дискасс.
Мне кажется, подобные высказывания я уже слышал после ГП СПб. И я выскажусь точно так же, как и там: задачи отличные. Их действительно интересно решать. В них отличные идеи, контест в целом неплохо сбалансирован. Магия с fread'ом - она была нужна, иначе теряется идея задачи - сделать ввод намного больше, чем ML. В остальном я не вижу никаких проблем - если аккуратно всё писать, косяков не возникает. С пониманием всё точно так же, как и на финале - заходит только оптимальное решение. И заоблачные ограничения - именно для того, чтобы отсекать кривую асимптотику.
Снарк в последнем Петрозаводске высказывался, что поляки очень любят действительно оптимальные решения. Поэтому сам он ограничения ставит не те, которые они предлагают, а по самому медленному из авторских решений со стандартным запасом в 2-3 раза. Если вы и под такие ограничения не можете запихать - может, стоит поучиться кодить? И под неасимптотическими оптимизациями я имел в виду именно это - нормальный код, а не такой, как на упомянутом Тимусе, где из последних контестов по редкой задаче нету 20-кратного запаса по времени и потому заходит вообще всё.