Через полчаса (в 19:00 по Москве) состоится SRM #577.
Предлагаю обсудить задачи здесь по окончанию.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Название |
---|
Хммм, интересно, что тогда здесь?
Подтверждение моей невнимательности. Скрыть пост?
Ох как яростно меня заминусовали :) Ладно, больше не буду
указывать красным на их ошибкикидать ссылки на заминусованные (и кривые) посты.судя по заголовку, поздний анонс 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 на самом деле заполняются нулями.
Ммм, а я о чем?
Понял, сначала неправильно интерпретировал слово "обязаны".
Тогда ещё бывают статические члены классов и статические переменные в функциях, которые тоже, вроде как, инициализируются нулями.