| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | Petr | 145 |
| 9 | pajenegod | 145 |
Привет, 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 в антицепь.
