Через полчаса (в 19:00 по Москве) состоится SRM #577.
Предлагаю обсудить задачи здесь по окончанию.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 8 | SecondThread | 147 |
| 9 | pajenegod | 145 |
| 9 | orz | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 18.04.2024 08:59:42 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Хммм, интересно, что тогда здесь?
Подтверждение моей невнимательности. Скрыть пост?
Ох как яростно меня заминусовали :) Ладно, больше не буду
указывать красным на их ошибкикидать ссылки на заминусованные (и кривые) посты.судя по заголовку, поздний анонс 557го раунда
Кто умеет доказывать, что в 1000 див2 мы всегда можем разделить двумя числами?
А то послал какую-то хрень, а она зашла о_О
Формально, что для любых двух l,r(l<r) работает один из трёх случаев:
- gcd(l,r) = 1;
- существует l<x<r, т.ч. gcd(l,x) = gcd(x,r) = 1;
- существуют x и y, т.ч. l<x<y<r и gcd(l,x) = gcd(x,y) = gcd(y,r) = 1.
Как решать 500 и 1000 див1?
500 в дорешке так досдал: повернем все на 45^, тогда расстояния это максимумы из разностей координат. будем делать 4х мерную динамику: (x1, y1, x2, y2) — суммарная стоимость операций, переход такой: перебираем новый камень, который не входит в этот прямоугольник, расширяем до него: (nx1, ny1, nx2, ny2) и суммируем стоимости для всех камешков которые попадают в первый прямоугольник и не попадают во второй.
1000 — mincut.
Захотим, чтобы вершина принадлежит множеству S, если через неё проходит вертикальная полоса, T — если горизонтальная.
Добавим рёбра пропускной способности 1 от вершины до всех соседних. Если с некоторой стороны соседа нет (клетка, которую не надо красить), то добавляем ребро в сток или исток в зависимости от того, соединён ли сосед по вертикали или по горизонтали.
В полученном графе mincut равен удвоенному ответу на задачу.
1000 можно было свести к минимальному разрезу в графе. Проведем ребра пропускной способности 1 из истока к закрашенным клеткам у которых соседняя сверху клетка не закрашена (или ее нет). Аналогично, проведем ребра проп. спос 1 из всех закрашенных клеток, слева от которых нет закрашенной клетки в сток. Теперь проведем ребра проп. спос 1 из каждой закрашенной клетки в соседнюю с ней клетку слева и снизу (если они закрашены). Утверждается, что мин. разрез в этом графе и будет искомым ответом.
Теперь о том, почему это работает. Каждая клетка, которая попадет в одну долю с истоком будет покрашена горизонтальным мазком, а все остальные клетки — вертикальным. Если слева от клетки край таблицы или не закрашенная клетка, то при горизонтальной покраске эта клетка будет началом отрезка и прибавит +1 к ответу. Аналогично, прибавляют +1 к ответу все клетки, которые мы красим вертикальным образом, у которых сверху нет закрашенного соседа. Дополнительно, +1 к ответу прибавляют соседние клетки, которые покрашены разным образом (здесь нужно их учитывать аккуратно, чтобы ничего не посчитать 2 раза).
Вроде бы понятно, очень круто, спасибо.
По 500 зашло такое: будем не добавлять камни, а удалять, тогда (возможно) на каждом шаге нам нужно удалить один из двух камней, расстояние между которыми максимально. Рекурсивно перебираем какой камень из двух будем удалять.
Жесть, и как в такое поверить на контесте?
Почему все так плохо порешали первую? Я минут 20 потерял на миспрочтении и исправлении баги в 1 символ, а получилось не самое маленькое 185 место.
Можете объяснить решение?
Сначала узнаем чему равно r. Теперь посмотрим все группы по r элементов в отсортированом по убыванию массиве. Будем считать не ожидание среднего значения, а ожидание значения суммы. Понятно, что каждая группа по r элементов добавит к сумме среднее арифметическое своих элементов, если там нету Элли (если есть — просто добавляем ее рейтинг).
Теперь посмотрим на остаток. Если его нет — возвращаем сумму деленную на количество человек в каждой комнате. Иначе, если он есть, и мы не выбирали еще Элли, добавляем к сумме рейтинг Элли, и делим на количество участников в комнате с учетом Элли. Иначе же есть два варианта: человек из остатка не попадет в комнату к Элли (с вероятностью (left-r)/r, где left — размер остатка) или попадет(каждый — с вероятностью 1/r). Аккуратно учитываем оба случая.
Все те, кто решил первую еще хуже, или же вообще ее не решил — в ярости жмут на минус)))
Относительно решения — я матч не писал, но вроде бы можно даже проще, чем описано чуть ниже, без разбора случаев, если раздвоить матожидание (в стиле быстрого подсчета шансов в покере), сейчас в практисе попробую и отпишусь.
Upd. Нет, нельзя. События все же зависимые( Все же надо разбирать 2 случая.
Столкнулся со странной фишкой.
250 я кодил не на том шаблоне, и по ошибке объявил переменные внутри класса, а не глобально, как я делаю обычно. Т.е. у меня было вот так:
В rsum у меня хранились суммы рейтингов пользователей, которых рассматриваем на определенной итерации. Вроде бы логично, что rsum используется с индексами 0..19. У меня 20000 — с запасом) Но решение упорно падает на 39 тесте.
Вместо того, чтобы искать баг в коде, я начал решать проблему народными методами. Помогло увеличение размера массива путем приписывания нолика)
Оказывается, если этот массив размера 20000 — он по дефолту заполнен какой-то ненулевой ерундой в 39 тесте, но вполне себе нулевой (по крайней мере, в тех местах, которые использую я) в предыдущих 38. А в 39 каждый раз одна и та же ненулевая ерунда, если его не занулить — получается лажа и WA39.
Если массив размера 200000 — все тесты проходит.
И теперь вопрос — должны ли эти переменные вообще быть обнулены, если я объявил их таким образом? Я подозреваю, что нет... Если да, то какого хрена оно не так в 39 тесте?:) Если нет, то каким чудом оно доходит до 39 теста, и почему увеличение размерности позволяет ему проходить вообще до конца?
Только глобальные обязаны буть занулены.
Почему whatever? Потому что UB
Как раз не глобальные. Глобальные в gcc на самом деле заполняются нулями.
Ммм, а я о чем?
Понял, сначала неправильно интерпретировал слово "обязаны".
Тогда ещё бывают статические члены классов и статические переменные в функциях, которые тоже, вроде как, инициализируются нулями.