Codeforces Global Round 16 Editorial Мы надеемся, что вам понравился контест. Сразу к разбору: <spoiler summary="A: Максимизация медианы"> [problem:1566A] <spoiler summary="Первое решение"> <spoiler summary="Подсказка 1"> Какие числа меньше медианы нужно брать? </spoiler> <spoiler summary="Подсказка 2"> Какие числа больше медианы нужно брать? </spoiler> <spoiler summary="Подсказка 3"> Жадный алгоритм. </spoiler> <spoiler summary="Разбор"> Будем рассматривать искомый массив из $n$ чисел в порядке неубывания. Заметим, что числа до медианы можно сделать равными нулю, после чего останется $m = \lfloor {\frac{n}{2}} \rfloor + 1$ чисел, сумма которых должна быть равна $s$, причём минимальное из них (то есть медиана) должно быть максимально. Чтобы этого добиться, достаточно сначала сделать эти числа равными $\lfloor {\frac{s}{m}} \rfloor$, а потом добавить к последнему числу то, что осталось от $s$, то есть $s \bmod m$. Нетрудно убедиться, что такой массив удовлетворяет всем условиям, причём сделать ...

Full text and comments »

Codeforces Round #703 (Div. 2) Разбор [problem:1486A] <spoiler summary="Подсказка1"> Какое наименьшее количество блоков необходимо, чтобы ответ был $\texttt{YES}$? </spoiler> <spoiler summary="Подсказка2"> Проверьте предикат на каждом префиксе. </spoiler> <spoiler summary="Решение"> Давайте рассмотрим минимальное количество блоков, которое необходимо, чтобы первые $i$ высот были возрастающими. Так как высоты неотрицательные и возрастающие они должны выглядеть как $0, 1, 2, 3, ..., i - 1$, так что минимальная сумма будет $\frac{(i - 1) \cdot i}{2}$. Оказывается, что это условие достаточное. Если это не так для какого-то префикса $i$, то мы не можем сделать этот префикс возрастающим (так как суммарное число блоков на префиксе никогда не увеличивается) соответственно ответ $\texttt{NO}$, иначе ответ $\texttt{YES}$, так как мы можем двигать блоки с $i$-й позиции, пока в ней хотя бы $i$ блоков и получим возрастающие высоты. </spoiler> Решение на C++: [submission:107892022]<br> Решение на Python: [submission...

Full text and comments »

Целочисленный бинпоиск – правильная реализация Казалось бы, по бинпоиску написано столько материалов, что все должны знать, как писать его, однако в каждом материале похоже рассказывается свой подход, и я вижу, что люди теряются и допускают ошибки в такой простой штуке. Поэтому я хочу рассказать о подходе, который нахожу наиболее элегантным. Из всего многообразия статей, я увидел свой подход только в этом [комментарии](https://mirror.codeforces.com/blog/entry/9901?#comment-153756) (но менее обобщённый). UPD: Также у [user:nor,2022-05-29] в [блоге](https://mirror.codeforces.com/blog/entry/96699). ### Проблема Предположим, вы хотите найти последний элемент в отсортированном массиве, меньший `x`, и просто храните отрезок кандидатов на ответ `[l, r]`. Если вы напишете: ~~~~~ int l = 0, r = n - 1; // отрезок кандидатов while (l < r) { // больше одного кандидата int mid = (l + r) / 2; if (a[mid] < x) { l = mid; } else { r = mid - 1; } } cout << l; ~~~~~ ...вы наткнётесь на проблему: предполож...

Full text and comments »

Codeforces Round #113 (Div. 2) Разбор задач Изначально мы хотели расположить задачи по сложности так: A-C-E-D-B. Насчет порядка последних двух мнения разделились. Посмотрим, что покажут результаты. [problem:166A] В этой задаче нужно сделать то, что написано в условии --- отсортировать команды по заданному компаратору: ($p_1 > p_2$) или ($p_1 = p_2$ и $t_1 < t_2$). После этого надо разбить команды на группы одинаковых, и найти размер группы, команды из которой делят $k$-ое место. Многие почему-то при равенстве числа задач сортировали команды по убыванию времени, а не по возрастанию. Такие решения случайно проходят претесты и получают WA #13. [problem:166B] Так как многоугольник A --- выпуклый, достаточно проверить, что все вершины многоугольника B лежат строго внутри многоугольника A. Идейно самое простое решение – построить выпуклую оболочку из точек обоих многоугольников, и проверить, что в нее входят точки только из первого многоугольника. Но в таком решении придется писать выпуклую оболочку, которая обязательно б...

Full text and comments »

Codeforces Round #107. Разбор задач. ### [problem:150E] Идея: 1. Сделаем бинарный поиск по ответу. Пусть мы хотим проверить существование пути с медианой $Mid$. 2. Если ребро $\ge Mid$ положим его вес равным $+1$, иначе $-1$. Теперь надо проверить существование пути не отрицательного веса, у которго длина $\ge l$ и $\le r$. Назовем такой путь хорошим. 3. Подвесим дерево за какую-то вершину $V$. 4. Сначала предположим, что путь проходит через $V$. Затем удалим эту вершину и сведем задачу к нескольким меньшим. 5. Если в качестве вершины $V$ выбирать центр дерева (такую вершину, что после подвешивания за нее, размер всех поддеревьев не превохсодит половины размера всего дерева), то таких шагов будет не более $Log(N)$. 6. Т.е если мы сейчас научимся за $O(F(N))$ проверять наличие хорошего пути, то мырешим задачу за сложность $O(F(N) * log^{2}(N))$. 7. Для начала научимся ее решать за $O(N Log (N))$. Для каждой вершины посчитаем ее глубину, стоимость пути от нее до корня, и первое ребро на пути от ко...

Full text and comments »

Разбор задач Codeforces Round #301 (Div. 2) [problem:540A] Для каждого символа посчитаем, в какую сторону выгоднее вращать диск. Это можно сделать либо формулой: $min(abs(a[i] - b[i]), 10 - abs(a[i] - b[i]))$, либо даже двумя циклами for: в прямом или обратном направлении. [problem:540B] Посчитаем количество оценок, меньших $y$. Если таких больше $\frac{n-1}{2}$ штук, то мы не сможем удовлетворить второму условию (про медиану), и ответ -1. Иначе получим ровно столько оценок $y$, чтобы количество оценок, больших или равных $y$, было как минимум $\frac{n+1}{2}$ штук (возможно, это уже выполняется). Это минимальное необходимое действие для удовлетворения второго условия. Теперь, чтобы не нарушить первое условие, сделаем оставшиеся неизвестные оценки как можно меньше &mdash; единицами, и проверим сумму. Если она больше $x$, то ответ снова -1, иначе требуемые оценки найдены. [problem:540C] Я выделил здесь три случая, хотя некоторые из них можно объединить. 1. Если начальная и конечная клетка совпадают, посмотрим ...

Full text and comments »

Ещё один блог о задачах с запросами Доброго времени суток, Codeforces! ---------------------------------- Недавно я решал задачи на структуры данных из архива, и мне пришли в голову идеи нескольких задач. Я хотел бы поделиться ими с вами и узнать ваше мнение о них. Косвенно этот блог вдохновлён [похожим блогом](https://mirror.codeforces.com/blog/entry/99300) от [user:BERNARB.01,2022-07-13]. Также я буду очень рад, если в комментариях предложат решения задач (быстрее, чем за $O(nq)$) или их модификации. Любой фидбек очень важен! В любом случае, перейдём к задачам. **Задача 1.** Имеется множество из $n$ отрезков на прямой, заданных границами $l_i$ и $r_i$ ($0$ <= $l_i$ <= $r_i$ <= $10^9$). Также имеется $q$ запросов, каждый задан отрезком с границами $x_i$ и $y_i$ ($0$ <= $x_i$ <= $y_i$ <= $10^9$). Для каждого запроса необходимо найти количество отрезков, вложенных в отрезок запроса. **Задача 2.** Аналогично задаче 1, но имеются запросы добавления отрезков в множество. **Задача 3.** Аналогично задаче 2, но им...

Full text and comments »

Codeforces Round #177, разбор задач Здравствуйте! #####[problem:289A] **Краткое описание.** Есть $10^5$ числовых отрезков, которые не пересекаются. За один шаг можно увеличить любой отрезок на $1$ влево или вправо. Нужно найти минимальное количество шагов, после которых число целых чисел, принадлежащих отрезкам, будем делится на $k$. **Решение.** Для начала нужно посчитать, сколько чисел изначально принадлежат заданным отрезкам. Поскольку они не пересекаются и даже не касаются (это следует из неравенства $min(r_i, r_j) < max(l_i, l_j)$ для всех $i, j$), никакая точка не может принадлежать двум отрезкам одновременно. Поэтому изначально величиной множества есть число $p \buildrel \text{d{}ef}\over = (r_1-l_1+1) + (r_2-l_2+1) + ... + (r_n-l_n+1) $. Если $p$ делится на $k$, то ответом будет число $0$ &mdash; не надо делать никаких шагов, все уже готово. Но если это не так, нужно подумать, за какое минимальное количество шагов из $p$ можно сделать число, которое делится $k$. Можно увидеть, что за один шаг величин...

Full text and comments »

Как додуматься до... задачи "F. Изучение бинарного поиска" из Codeforces Round 1088, Div. 1 + Div. 2 Всем привет! Сегодняшний пост посвящён [задаче F](https://mirror.codeforces.com/contest/2211/problem/F) с недавнего [Div 1 + Div 2 раунда](https://mirror.codeforces.com/contest/2211). Она стала локальной знаменитостью, потому что является более решаемой задачей, чем [задача Е](https://mirror.codeforces.com/contest/2211/problem/E) того же раунда. А сегодня мы разберёмся, почему же эта задача такая простая Итак, переходим к задаче. В ней для каждого отсортированного массива $a$ с элементами от $1$ до $m$ нужно посчитать суммарное количество итераций, за которое стандартный бинпоиск находит в массиве каждый элемент от $1$ до $m$. В задаче эта сумма описана как $f(a,1,1,n)+f(a,2,1,n)+\ldots+f(a,m,1,n)$. Ограничение: $n, m \leq 10^6$ Давайте попробуем что-то понять про количество итераций бинпоиска в зависимости от искомого числа $k$. Интуиция подсказывает, что на всех массивах бинпоиск будет вести себя регулярным образом, нужно это лишь формализовать. Для того, чтобы быстрее нащупать идею, давайте нем...

Full text and comments »

Разбор Codeforces Round #330 (Div.1 + Div. 2) [595A &mdash; Виталий и ночь](http://mirror.codeforces.com/problemset/problem/595/A) Простая задача на реализацию. Проитерируемся по $i$ от 1 до n, а внутри проитерируемся по $j$ от 1 до $2 \cdot m$, причем на каждой итерации будем увеличивать $j$ на два. Если на текущей итерации $a[i][j] = '1'$ или $a[i][j + 1] = '1'$ увеличим ответ на один. Асимптотика решения &mdash; $O(n m)$. [595B &mdash; Паша и телефон](http://mirror.codeforces.com/problemset/problem/595/B) Будем считать ответ для каждого блока отдельно и умножать ответ для предыдущих блоков на ответ для текущего блока, при этом не забывая брать результат перемножения по модулю. Для блока длины $k$ ответ считается следующим образом. Пусть для этого блока число должно делиться на $x$ и не должно начинаться с цифры $y$. Тогда ответ для этого блока &mdash; количество чисел из $k$ цифр, делящихся на $x$, минус количество чисел, начинающихся с цифры $y$ и состоящих из $k$ цифр, плюс количество чисел, начинающихся с...

Full text and comments »

Бинарный поиск в вещественных числах Как выглядит типичный бинарный поиск в вещественных числах? Так: ~~~~~ float l = 0.0f, r = 1e14f; for (int i = 0; i < iteration_count && l + eps < r; ++i) { float mid = 0.5f * (l + r); if (check(mid)) r = mid; else l = mid; } ~~~~~ Здесь `l` и `r` &mdash; границы, выставляемые исходя из условия, `check(x)` &mdash; функция, которая начиная с какого-то x возвращает true, до него &mdash; false, и нужно найти этот x. Как правило, `l` или `0.5 * (l + r)` &mdash; ответ. Но есть несколько минусов: 1. Количество итераций еще нужно подобрать, балансируя между точностью ответа и временем работы. 2. Ответ с погрешностью. #### Что можно с этим сделать? Для начала разберемся, как представляются вещественные числа. Детально можно почитать, к примеру, [тут](https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%BE_%D0%BE%D0%B4%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B9_%D1%82%D0%BE%D1%87%D0%BD%D0%BE%D1%81%D1%82%D0%B8) и [тут](http://www.volke...

Full text and comments »

Медиана массива. Всем Привет!<br><br>Попалась недавно задачка, к которой не могу подобрать алгоритм. ((<br>Когда уже мысли кончились, решил погуглить, но решения так и не обнаружил... хотя в некоторых статьях пишут, что оно существует ))<br><br>Задача такова, что необходимо найти медиану массива (неотсортированного конечно же). <br>Т.е. такое значение, которое после сортировки массива A[1...n]&nbsp; будет равно:<br>элементу A[n / 2 + 1], при нечетном n и (A[n / 2] + A[n / 2 + 1]) / 2.0, при четном n.<br><br>НО.... самое интересное, что алгоритм должен быть линейным... 8)

Full text and comments »

Russian Code Cup 2016 — Warmup Round — Разбор задач <h2>A. Секретный код</h2> <p>Задача относится к типу &laquo;сделайте что просят&raquo;. Очевидно, как посчитать количество совпадающих символов у двух строк. Для проверки встречался ли данный символ в исходной строке достаточно предподсчитать массив логических значений used[c], где хранится true если символ c встречался в секретном коде и false иначе.<h2>B. Хаос</h2> <p>Рассмотрим наибольшее среднее арифметическое двух чисел, которое можно получить используя два числа из входных данных. Легко заметить, что это среднее арифметическое двух наибольших чисел массива. </p><p>Ответ больше этого числа никак не получить, так как при замене двух чисел на две копии их среднего арифметического среднее арифметическое двух максимумов не увеличивается. </p><p>Теперь рассмотрим стратегию, как можно добится этого результата: На каждом ходу берем эти два максимума и любое число, стираем, затем дважды пишем среднее арифметическое максимумов. Начиная со второго хода два максимума перестанут меняться и ...

Full text and comments »

Помогите с задачей. <P>Задача из второго тура SNWS-10. Про медиану. Дано N (1&lt;=N&lt;=10^6) чисел. Числа добавляются в изначально пустой набор в заданном порядке. Требуется определять медиану после каждого добавления числа. <BR></P><P>Я реализовал бинарное дерево поиска по Кормену. Однако получил TL на 11 тесте. Вот код:</P><P>[cut]</P><P>struct binary_elem {<BR> long key,size,left,right; <BR>};<BR><BR>vector&lt;binary_elem&gt; BT;<BR><BR>binary_elem BT_init(long key) {<BR> binary_elem res;<BR> res.key=key;<BR> res.size=1;<BR> res.left=-1;<BR> res.right=-1;<BR> return res;<BR>}<BR><BR>void BT_insert (binary_elem z) {<BR> long y=-1,x=0;<BR> BT.push_back(z);<BR> long cur=BT.size()-1;<BR> if (cur==0) return;<BR> while (x!=-1) {<BR> y=x;<BR> BT[x].size++;<BR> if (z.key&lt;BT[x].key) x=BT[x].left; else x=BT[x].right;<BR> }<BR> if (y!=-1)<BR> if (z.key&lt;BT[y].key) BT[y].left=cur; else BT[y].right=cur;<BR>}<BR><BR>long BT_select (long x, long i) {<BR> long r;<BR> while (true) {<BR> if (BT[x].left==-1) r...

Full text and comments »

Codeforces Round Statistics FAQ #### Пример статистики раунда [Здесь](/blog/entry/10167) #### Значения чисел <br/> **Sent** &mdash; количество **участников**, сделавших хотя бы одну попытку по задаче<br/> **Pretest fail** &mdash; количество **участников**, решение которых "остановилось" на **претестах**<br/> **Hacked** &mdash; количество **участников**, решение которых было взломано и не ушло дальше **взлома**<br/> **Systest fail** &mdash; количество **участников**, решение которых "остановилось" на **системных тестах**<br/> **Accepted** &mdash; количество **участников**, решивших задачу<br/> **Attempts** &mdash; общее количество **попыток** по задаче<br/> **Success %** &mdash; отношение количества успешных попыток к общему количеству попыток по задаче<br/> **Severity** &mdash; среднее количество попыток среди участников, решивших задачу<br/> **Median Score** &mdash; медиана полученных за *...

Full text and comments »

Доступ к элeментам в контейнерах Недавно столкнулся с задачей, частью которой был доступ к медиане за О(logN) максимум, при этом элементы добавляются/удаляются по-одному и медиана нам нужна будет только тогда когда кол-во элементов в нашем списке равно какому-то М. Мне когда-то говорили что это можно делать при помощи нескольких деревьев Фенвика, но хотелось бы узнать какой-то более оптимальный способ. Я пробовал это делать при помощи сета с итератором на середину, но по-ходу я понял что этот итератор я не умею двигать. **UPD.** хотелось бы также узнать можно ли решать более обобщенные задачи, например узнать медиану на отрезке от L до R.

Full text and comments »