| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
Привет, codeforces!
У меня вопрос:
Если у нас есть массив $$$a$$$ длины $$$n$$$ (не обязательно перестановка), $$$L_i$$$ — индекс ближайшего слева от $$$i$$$ элемента массива, который $$$≥$$$ чем $$$a_i$$$, а $$$R_i$$$ — индекс ближайшего $$$>$$$ (строго большего!) справа, то какая хорошая оценка сверху на: $$$\sum\limits_{i=1}^n min(i - L_i, R_i - i)$$$?
Я знаю, что если $$$R_i$$$ — больше или равный, то это $$$O(n log n)$$$.
Буду рад услышать ваши ответы!
https://csacademy.com/app/graph_editor/
It says: Internal Server Error
What would you recommend to use instead of CSAcademy's Graph Editor? Thanks in advance
Why can't authors work a little harder and write solutions that are looking good?
For example, this code could be a lot more understanable:
Задача 4. Пингвиноведение со всеросса 2015
Вам даны числа K <= N <= 2e5, а так же дана бинарная строка длины N, надо вывести другую бинарную строку N, чтобы кол-во блоков из подряд идущих элементов одного типа было максимум K, а так же чтоб кол-во мест, в которых эти строки различаются было минимальным.
Здравствуйте! Я не знаю доказательство этого алгоритма(( Если кто-то знает, можете пожалуйста написать доказательство в комментариях.
Алгоритм:
1) Первым шагом строим Транзитивное замыкание графа (если из A был путь в B, то в этом графе будет ребро из A в B).
2) "Копируем граф". Теперь у каждой вершины будет копия. Если в графе (в том, который мы получили после предыдущего шага) было ребро из A в B, то теперь есть ребро из вершины A, которая находится в левой доле в вершину B, которая находится в правой доле. (По сути теперь у вершины A есть две вершины: AL и AR)
3) В получившемся графе ищем максимальное независимое множество.
4) Теперь если и VR, и VL лежат в независимом множестве, то мы берем V в антицепь.
