Rating changes for last rounds are temporarily rolled back. They will be returned soon.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | jiangly | 3640 |
| 2 | Benq | 3593 |
| 3 | tourist | 3572 |
| 4 | orzdevinwang | 3561 |
| 5 | cnnfls_csy | 3539 |
| 6 | ecnerwala | 3534 |
| 7 | Radewoosh | 3532 |
| 8 | gyh20 | 3447 |
| 9 | Rebelz | 3409 |
| 10 | Geothermal | 3408 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Find user
→ Recent actions
You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:
305— search for 305, most probably it will find blogs about the Round 305andrew stankevich contests— search for words "andrew", "stankevich" and "contests" at the same timeuser:mikemirzayanov title:testlib— search containing "testlib" in title by MikeMirzayanov"vk cup"— use quotes to find phrase as istitle:educational— search in title
Results
1.
[Tutorial] Пересечение матроидов простыми словами **[This article is also available in [English](https://codeforces.com/blog/entry/69287?locale=en)]**
Привет, CodeForces.
Я думаю, что матроиды — это прекрасные и очень мощные структуры, однако, не настолько хорошо известные в спортивном программировании.
Я познакомился с матроидами на Зимних Петрозаводских Сборах 2019. Там была задача, которая очевидно не решалась обычными способами, известными мне тогда. Разбор этой задачи состоял буквально из трех слов “just matroid intersection”. Тогда мне потребовалось больше двух дней дорешивания чтоб найти всю необходимую информацию и детали и написать решение, которое получает Accepted. И намного больше времени мне потребовалось чтобы понять почему это действительно работает и как именно это работает. (Я до сих пор сомневаюсь в некоторых деталях.)
Конечно, совершенно не трудно нагуглить все необходимые определения и статьи, связанные с этой темой, но мне кажется, что все они больше сконцентрированы на математической теории, с...
2.
Обновления Polygon (июнь-октябрь 2019) Hello, Codeforces!
Я и [user:cannor147,2019-11-07], будучи студентами Университета ИТМО, в июне присоединились к разработке Codeforces. С июня по октябрь мы преимущественно занимались развитием платформы Polygon. В этом посте нам бы хотелось представить вам список того, что мы сделали за это время. В этот список не включены мелкие баг-фиксы или какие-то незаметные пользователям улучшения.
#### Пин-коды для контестов и задач
Иногда в Polygon разрабатываются особо важные контесты и задачи. В таком случае председатель жюри может быть обеспокоен возможностью утечки, например из-за слабого пароля другого члена жюри. Пин-код — дополнительный фактор подтверждения доступа к задаче или контесту, его может установить или изменить только владелец задачи или контеста. Предполагается, что пин-код будет передан каким-то отдельным надежным каналом связи.
Теперь в интерфейсе контеста для владельцев появилась ссылка Create Pin:
 Привет, Codeforces!
Мы, [user:AlperenT,2024-03-26], [user:flamestorm,2024-03-26], [user:toxicpie9,2024-03-26] и [user:willy108,2024-03-26], приглашаем всех на Codeforces на [contest:1952]! 12-й Конкурс первоапрельских розыгрышей пройдет [contest_time:1952]. Это шутливое соревнование, в котором решение задачи часто проще, чем понять, что за задача вообще.
В этом раунде вам будет дано $n$ крутых багабу, где $-1 \le n \le \textbf{[REDACTED]}$, и **2** часа для их решения. В конкурсе будут использоваться расширенные правила ICPC (нет хаков, позиции определяются количеством решенных задач и штрафным временем, полученным за них). Вы можете отправлять решения на любом языке, разрешенном на Codeforces, если задача не указывает обратного.
Обратите внимание, что раунд **не рейтинговый**, и штраф за **неправильное решение** составляет **10** минут.
Чтобы представить, как будет выглядеть контест, вы можете посмотреть на контесты предыдущих лет: [2012](https://codeforces.com/contest/171...
Announcement of April Fools Day Contest 2024
4.
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...
Tutorial of Codeforces Round 703 (Div. 2)
5.
Яндекс.Алгоритм 2017, третий отборочный раунд: разбор (с челленджами и свистелками) На этот раз я решил попробовать писать разбор в спойлерах, как уже делал кое-кто из авторов. Буду рад вашим комментариям о том, стало ли лучше.
#### Задача A. Сдвиги
Темы: динамическое программирование.
Общий комментарий: это первая среди "сложных" задач контеста. В ней можно помочь хорошее знакомство со стандартными задачами на ДП, но довести решение до финального правильного вида все равно непросто.
Решение: пускай мы можем сдвигать не только вправо, но и влево.
<spoiler summary="Как решать такую задачу?">
Прежде всего заметим, что сделать сдвиг -- это то же самое, что переместить какой-то символ в другое место. Ясно, что никакой символ не надо двигать больше одного раза, поскольку вместо этого можно сразу поставить его на финальное место и не тратить действия. Кроме того, очевидно, что сдвиги не меняют количество вхождений каждого символа в строку, поэтому в обеих строках посимвольные вхождения должны совпадать.
Посмотрим теперь на символы исходной строки, котор...
, что и разность $c_i / d_i - c_j / d_j$. Теперь для сравнения надо сделать
всего одинзапрос (если
6.
Codeforces: итоги 2014 <img src="http://assets.codeforces.com/images/statistics-2014/snowman-ru.png" style="float:right; margin:0 1em 1em 1em;"/>
Здравствуй, 2015! Добрый день, Codeforces!
На календаре 2-е января, а значит оливье почти съедено. Итоги 2014-го года я как обычно подведу тезисно, без этого "коротенько, минут на сорок".
Честно говоря я почти опасался начинать подводить статистику 2014-го года, ведь <a href="/blog/entry/10148">в 2013-м году Codeforces показал настолько стремительный рост</a>, что было бы неудивительно выглядеть бледненько на его фоне. Как бы не так! Я был приятно удивлен цифрам и отчетам!
Чуть ниже будет список основных событий и достижений Codeforces за прошедший год. Для вас это просто список, но обратите внимание — за каждым пунктом кроется напряженная многодневная работа команды Codeforces, авторов задач, организаторов контестов и турниров, помощь тестов и волонтеров. Ура! Мы вместе сделали всё это (а список неполный, много что просто опущено):
* разработа...
7.
Grakn Forces 2020 [Div1 and Div2] Привет, Codeforces!
<center>
<img alt="grakn" src="https://grakn.ai/assets/svg/logo.svg" style="float:right; height: 50px; margin: 10px; max-width:10%;"/>
</center>
Я рад пригласить вас поучаствовать в [contest:1408], который состоится [contest_time:1408]. Он будет **рейнтинговым и открытым для обоих дивизионов**.
Этот раунд проводится по инициативе и поддержке компании Grakn Labs. Больше информации можно найти [здесь](https://codeforces.com/blog/entry/82787).
Все задачи были придуманы и подготовлены [user:300iq,2020-09-29] и [user:isaf27,2020-09-29]. Большое спасибо [user:growup974,2020-09-29], [user:postscript,2020-09-29], [user:QAQAutoMaton,2020-09-29], [user:PM11,2020-09-29], [user:morzer,2020-09-29], [user:qlf9,2020-09-29], [user:RedDreamer,2020-09-29], [user:gdb_18,2020-09-29], [user:talibmohd,2020-09-29], [user:Dragnoid99,2020-09-29], [user:KAN,2020-09-29] и [user:VladGanzha,2020-09-29] за тестирование раунда и отличные советы, а так же [user:MikeMirzayanov,2020-...
Announcement of Grakn Forces 2020
8.
Codeforces Round #265: разбор Я скоро засабмичу свои решения и положу здесь ссылки.
В некоторых разборах приведены дополнительные челленджи, над которыми можно поломать голову. Делитесь идеями в комментариях. =)
[problem:465A]
Если прибавить к числу 1, его двоичная запись поведет себя понятным образом: все младшие единицы превратятся в нули, а следующий за ними ноль станет единицей. Найдем длину максимального суффикса из единиц, пусть она равна $l$. Тогда ответ равен $l+1$, кроме случая, когда вся строка состоит из единиц, тогда ответ $l$.
Забавно, что в задаче div1E тоже приходится думать о том, что будет, если прибавить к числу 1. =)
[problem:465B]
Наилучшая стратегия такова: для каждого непрерывного отрезка из непрочитанных писем откроем первое письмо, пролистаем до последнего в том же отрезке, если есть еще непрочитанные письма, вернемся к списку.
Легко показать, что лучше мы сделать не сможем: для выбранного отрезка посмотрим на момент, когда мы прочитаем последнее письмо из него. Если мы ...
к последовательности новый запрос $d_i \to t_i$. Как поменяются чиселки $m_d$
и $s_d$? Очевидно, (\log n)$ времени, но каждый запрос может потребовать создания $O(\log n)$
дополнительных вершин., , поэтому ответить на запрос о сравнении можно уже сейчас., Теперь добавим спереди к последовательности новый запрос $d_i \to t_i$. Как
поменяются чиселки $m_d
Tutorial of Codeforces Round 265 (Div. 1)
Tutorial of Codeforces Round 265 (Div. 2)
9.
Общие идеи Всем привет!
Любители ли вы задачи, которые расчитаны на Ad Hoc решение? Я — терпеть не могу! Поэтому я решил сделать подборку идей, которые могут быть применены к достаточно большому классу задач. Добавляйте ещё, если о чём-то забыл. :)
[cut]<br>
**1. Слияние множеств за $O(n\log{n})$ амортизированно.** Если у нас есть некоторые множества, которые нам потом нужно будет соединять, поддерживая промежуточные результаты, то можно делать это в лоб, всегда добавляя меньшее множество к большему. Таким образом, каждый элемент будет перенесён в какое-то другое множество не более, чем $O(\log{n})$ раз, так как новое множество для него каждый раз будет увеличиваться хотя бы в два раза. На этом, в частности, основана одна из версий общеизвестного _DSU_. Из применений — можно сливать множества внутри обхода дерева в глубину и таким образом можно для каждой вершины в какой-то момент времени подержать в руках множество всех элементов её поддерева.
**2. Подвохи в задачах. Час...
, отрезка длины $1$, мы сможем выполнить запрос так, будто перед нами готовое
статичное множество. Об этой
10.
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$. Нетрудно убедиться, что такой массив удовлетворяет всем условиям, причём сделать ...
вместе. Пусть $ans(x)$ — ответ на запрос с числом $x$, а $g(x)$ — $xor$ всех
чисел, не
Tutorial of Codeforces Global Round 16
11.
C++17, competitive programming edition C++17 уже [доступен](http://codeforces.com/blog/entry/57646) на codeforces, сообщество [хочет](http://codeforces.com/blog/entry/15643?#comment-413401) новую версию [C++ tricks](http://codeforces.com/blog/entry/15643), которую написал [user:Swift,2018-02-13], так что, начнем!
Disclaimer: Я сделал всего лишь немного примеров новых фич, которые по моему мнению относятся к спортивному программированию. Если у Вас есть примеры лучше или Вам что-то непонятно, или нужно больше объяснений каких-то фич $---$ пишите в комментах)
### Fold expressions (Свертки)
* Я думаю все знают, что такое reduce и свертка, но все-таки приведу пример из c++11:
```
vector<int> v = {1, 3, 5, 7};
int res = accumulate(v.begin(), v.end(), 0, [](int a, int b) { return a + b; });
cout << res; // 16
```
* Начиная с C++17 есть поддержка свертки для шаблонного списка со следующим синтаксисом:
```
(pack op ...)
(... op pack)
(pack op ... op init)
(init op ... op pack)
```
* Для примера напишем...
; cin >> l >> r; //Обработаем запрос первого типа break
12.
Интерактивные задачи: руководство для участника Иногда на соревнованиях по программированию (в том числе и на Codeforces) вы можете встретить _интерактивные задачи_.
При тестировании вашего решения по интерактивной задаче тот ввод, что будет подаваться в ваше решение (то есть те данные, что ваше решение читает) не являются заранее заготовленными, а строятся непосредственно в процессе тестирования вашей программы. Для этого жюри пишет специальную программу _интерактор_, вывод которой отправляется в ваше решение, а вывод вашего решения отправляется в интерактор. Иными словами, ваше решение и интерактор работают в паре и как ваше решение, так и интерактор могут принимать решение о том, что в данный момент вывести на основании "истории общения".
При написании решения для интерактивной задачи важно помнить, что если вы что-то вывели, то без специального указания в программе эти данные могут на самом деле попасть во внутренний буфер и не быть выведенными немедленно. Это может привести к ситуации, что интерактор "не увидел" ваш вывод...
строк является ответом системы на $i$-й запрос. После того, как ваша программа
угадала число, выведите, $ включительно. Вы можете делать запросы к тестирующей системе, каждый запрос —
это вывод одного, Вы можете делать запросы к тестирующей системе, каждый запрос — это вывод
одного целого числа, Каждое из значений $x_i$ обозначает очередной запрос к системе. Ответ на запрос
программа сможет, Тестирующая система даст вашей программе прочитать ответ на запрос из входных
данных только после
13.
Разделяй и властвуй. Dynamic connectivity offline и ускорение ДП. Разделяй и властвуй по запросам. Всем привет, Codeforces! Я давно хотел написать какой-нибудь образовательный блог, но никак не мог найти для этого тему. И недавно я вспомнил, что на Codeforces нет толкового блога по одной из моих любимых тем: технике "разделяй и властвуй". Поэтому я хочу рассказать о ней. План будет примерно такой:
1) Разделяй и властвуй. Что это за техника такая и для чего она нужна. Пример.
2) Dynamic connectivity offline при помощи разделяй и властвуй. Разделяй и властвуй dp оптимизация.
3) Расскажу о методе, который я придумал самостоятельно: разделяй и властвуй по запросам. В этом случае мы делим не только массив, но и запросы на группы.
Итак, поехали.
Сначала о том, что это за техника такая. Суть состоит примерно в следующем: пусть у нас есть, скажем, массив. Тогда, если мы умеем вычислять ответ для двух его частей, и умеем из ответов по двум частям получать ответ для целого массива, то можно применить технику разделяй и властвуй. Давайте разберем ее на самом простом примере: сор...
умели по списку ребер быстро отвечать на запрос, то мы бы получили готовое
решение. К сожалению, в, )$ операций, а весь dfs займет $O(q \cdot t_1 + S \cdot t_2)$, где $t_1$ --
время на ответ назапрос, $S, Итак, если бы мы умели по списку ребер быстро отвечать на запрос, то мы бы
получили готовое решение
14.
Dynamic connectivity problem Всем привет!
Недавно на тренировочных сборах MIPT: The Fall на контесте от Александра [user:Milanin,2014-11-22] была задача с Petr Mitrichev Contest 7. Суть её заключалась в том, что нам был дан граф и множество запросов вида "допустим, мы удалили из графа $k \leq 4$ рёбер. Остался ли он связным?" Я не знаю, какое решение предполагалось автором (буду благодарен, если кто-то расскажет или скажет, где его можно найти, говорят, там что-то красивое :), но далее я хочу рассказать о решении более общей задачи, когда рёбра произвольно добавляются и удаляются, за $O(k \log k)$ в оффлайне. Первый алгоритм с такой оценкой был получен Дэвидом Эппштейном в 1992 году сведением к fully dynamic minimum spanning tree problem, однако здесь речь пойдёт о более простом алгоритме, предложенном в 2012 году Сергеем [user:Burunduk1,2014-11-22] Копелиовичем.
[cut]<br>
Будем считать, что запросы бывают трёх типов — добавить ребро (`+`), удалить ребро (`-`) и узнать некоторую информацию о граф...
реализация СНМ, дающая оценку $O(\frac {\log n} {\log \log n})$ на запрос, что
позволяет опустить, $ вершин). Переделаем запросы таким образом, что если в начальном графе запрос
был обращён к паре, запрос был обращён к паре вершин $(a, b)$, то теперь он будет обращён к паре
вершин-компонент
Discussion of Dynamic connectivity contest
15.
Будьте осторожны с random_shuffle Всем привет! Может быть, эта тема уже обсуждалась, но по запросу "random" ничего похожего на Codeforces не нашел.
Предыстория. Хотели с Сашей ([user:adrozdova,2015-03-26]) изучить декартово дерево. Для инициализации приоритетов рекомендуется использовать случайные числа, чтобы высота дерева не была очень большой. Соответственно, надо эти числа как-то получить. Я совсем не разбираюсь в структурах данных, поэтому не задумывался, насколько плохо будет дереву (и будет ли), если приоритеты нескольких вершин будут одинаковыми. Поэтому на всякий случай хотелось сделать их попарно различными (чего не гарантирует простое использование rand() при создании очередной вершины). Предложил следующий, "надежный" и "проверенный" метод — создать массив из N чисел, инициализировать его числами от 0 до (N-1) соответственно, применить к нему random_shuffle — и мы получим N различных ключей в случайном порядке.
История. Саша стала сдавать задачи и на практике оказалось, что в нескольких за...
16.
CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) Разбор Извините за технические шоколадки в задаче B. Надеемся, что в остальном вам всё понравилось. Подсказки добавим скоро.
[problem:1870A]
<spoiler summary="Разбор">
Заметим, что если $min(n, x+1) < k$, то ответ $-1$.
Иначе существует два случая:
- Если $k=x$, то подходящий массив выглядит как $[0, 1, 2, \dots, k-1, \dots, k-1]$.
- Если $k \ne x$, то подходящий массив выглядит как $[0, 1, 2, \dots, k-1, x, \dots, x]$.
В обоих случаях мы можем построить массив и посчитать его сумму за линейное время. Итоговая асимптотика $O(n \cdot t)$.
</spoiler>
[problem:1870B]
<spoiler summary="Разбор">
Заметим, что после операции с $b_j$, у которого есть какой-то единичный бит, этот бит станет единичным у всех чисел из $a$ (и останется им, так как бит не может стать нулём из единицы в результате операции ИЛИ). Если $n$ чётное, то в итоговом XORе этот бит станет нулевым, так как он будет равен XORу чётного числа единиц. Если $n$ нечётное, то этот бит будет единицей в итого...
17.
Codeforces Round #846 (Div. 2) — Разбор [problem:1780A]
Идея: [user:AndreyPavlov,2023-01-24] <br> Подготовка: [user:AndreyPavlov,2023-01-24] <br> Разбор: [user:AndreyPavlov,2023-01-24]
<spoiler summary="Разбор">
Заметим, что существует два варианта какие числа брать, чтобы их сумма была нечётной: $3$ нечетных числа; $2$ четных и $1$ нечетное. Сохраним все индексы четных и нечетных чисел в два массива, и проверим оба случая.
</spoiler>
<spoiler summary="Решение (Python)">
~~~~~
def solve():
n = int(input())
a = list(map(int, input().split()))
odd, even = [], []
for i in range(n):
if a[i] % 2 == 0:
even.append(i + 1)
else:
odd.append(i + 1)
if len(odd) >= 1 and len(even) >= 2:
print("YES")
print(odd[0], even[0], even[1])
elif len(odd) >= 3:
print("YES")
print(odd[0], odd[1], odd[2])
else:
print("NO")
t = int(input())
for test in range(t):
solve()
~~~~~
</spoiler>
<...
единицы с начала, следовательно делать ещё один запрос для этого бесполезно.
Тогда вместе с тем, как
Tutorial of Codeforces Round 846 (Div. 2)
18.
Разбор Codeforces Round #770 (Div. 2) Спасибо за участие, надеемся, что вам понравились задачи! Также мы просим вас оценить каждую из задач раунда в соответствующем спойлере, чтобы улучшить качество будущих соревнований.
Все задачи были подготовлены [user:Alexdat2000,2022-02-02] при помощи соавторов.
[Почему AI не участвовал](https://codeforces.com/blog/entry/99579?#comment-884764)
[problem:1634A]<br>
Идея: [user:sevlll777,2022-02-02]
<div class="spoiler"> <b class="spoiler-title">Подсказка 1</b> <div class="spoiler-content" style="display: none;">
Каким свойством будет обладать строка после первой операции (независимо от типа операции)?
</div></div>
<div class="spoiler"> <b class="spoiler-title">Подсказка 2</b> <div class="spoiler-content" style="display: none;">
Что произойдет, если применить операцию к палиндрому?
</div></div>
<div class="spoiler"> <b class="spoiler-title">Разбор</b> <div class="spoiler-content" style="display: none;">
[tutorial:1634A]</div></div>
<spoiler summary="Решение">
...
="display: none;"> Обозначим за $\bar{i}$ ответ на запрос для трех индексов,
отличных от $i$. Зная
Tutorial of Codeforces Round 770 (Div. 2)
19.
Разбор VK Cup 2015 — Finals Всем спасибо за участие! Задачи следуют в порядке, в котором они шли на оригинальном соревновании.
[problem:562A]
--------------
(в трансляции: [problem:566C])
Формализуем задачу. Нам дано необычное определение расстояния по дереву: $\rho(a, b) = dist(a, b)^{1.5}$. У каждой вершины есть её вес $w_i$. Нужно как-то так выбрать место $x$ для проведения соревнования, чтобы минимизировать сумму взвешенных расстояний от всех вершин до неё: $f(x) = w_1 \rho(1, x) + w_2 \rho(x, 2) + \ldots + w_n \rho(x, n)$.
Давайте изучим свойства функции $f(x)$. Мысленно разрешим себе ставить точку $x$ не только в вершины дерева, но и в любую точку на ребре, доопределив естественным образом расстояние от точки внутри ребра до всех остальных вершин (например, середина ребра длины $4$ находится на обычном расстоянии $2$ от концов ребра).
**Утверждение 1**. На любом пути $x \in [a, b]$ в дереве функция $\rho(i, x)$ является выпуклой вниз. Действительно, функция $dist(i, x)$ на любом пути выгляд...
]$ и сливаем их. Для ответа на запрос третьего типа проверяем, лежат ли
работники $x$ и $y$ в одном
Tutorial of VK Cup 2015 - Finals
Tutorial of VK Cup 2015 - Finals, online mirror
20.
Разбор VK Cup Round 1 Набор задач в онлайн-трансляции незначительно отличается от набора задач на основном раунде, задачи следуют в порядке, в котором они фигурируют в основном раунде.
[problem:524A]
==============
В задаче требовалось реализовать ровно то, что описано в условии. Фиксируем человека $x$, проходимся по всем остальным людям $y$, не дружащим с $x$, и считаем количество общих друзей $x$ и $y$.
Тонкий момент №1: несмотря на то, пар друзей во вводе не более 100, самих людей может быть до 200, и можно ошибиться в выставлении размеров массивов.
Тонкий момент №2: нужно аккуратно сравнивать вещественные числа. Если написать нечто вроде `common / degree >= k / 100.0`, то в силу специфики вычислений с вещественными числами, результат такой проверки может быть недетерминирован (если в какую-то из частей внесётся незначительная погрешность). Поэтому, надо либо сравнивать с точностью до некоторого `eps`, либо выполнять проверку в целых числах: `common * 100 >= degree * k`.
[problem:524B]
=...
чтобы ответить на один запрос, переберём первое слагаемое в сумме, а второе
либо найдём бинарным, Можно показать, что выгоднее всего сопоставить этот запрос самому недавнему из
активных людей, запрос пытаемся сопоставить новому человеку. Разумеется, это не всегда возможно
сделать &mdash
Tutorial of VK Cup 2015 - Round 1
21.
Codeforces API <img style="float: right; height: 350px" src="http://assets.codeforces.com/images/posts/api.png"/>
Добрый день, Codeforces!
Сегодня мы представляем вам [Codeforces API](/apiHelp). Благодаря этому разделу, вы сможете получать часть данных Codeforces в машинно-читаемом JSON-формате.
У API есть подробная инструкция по адресу [/apiHelp](/apiHelp), которая поддерживается актуальной. У каждого метода есть пример URL, которым можно воспользоваться для просмотра примера результата метода и экспериментов с параметрами.
По умолчанию, любой запрос к API будет анонимным, и ему будут доступны только публичные данные. Чтобы сделать запрос не анонимным, надо создать API-ключ на странице [/settings/api](/settings/api) и воспользоваться нижней частью инструкции по адресу [/apiHelp](/apiHelp).
На данный момент все методы API лишь читают данные. Добавление write-методов вида "послать решение" планируется.
Мы открыты для предложений и запросов о новых API-методах. Особенно, от автор...
экспериментов с параметрами. По умолчанию, любой запрос к API будет анонимным,
и ему будут, По умолчанию, любой запрос к API будет анонимным, и ему будут доступны только
публичные данные
22.
Ещё один блог о задачах с запросами Доброго времени суток, Codeforces!
----------------------------------
Недавно я решал задачи на структуры данных из архива, и мне пришли в голову идеи нескольких задач. Я хотел бы поделиться ими с вами и узнать ваше мнение о них. Косвенно этот блог вдохновлён [похожим блогом](https://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, но им...
23.
Jngen: универсальный генератор тестов Два года назад я [вкидывал](http://codeforces.com/blog/entry/20108) в сообщество идею о библиотеке, которая умеет генерировать разные клёвые тесты. Я долго крутил идею в голове и наконец попытался что-то написать. Реализовано пока далеко не всё из того, что хочется, но то, что уже есть, я активно использую в своих задачах.
Итак, встречайте: https://github.com/ifsmirnov/jngen. Саму библиотеку (точнее, единственный хедер jngen.h) можно скачать [тут](https://raw.githubusercontent.com/ifsmirnov/jngen/master/jngen.h).
Jngen умеет работать с массивами, деревьями и графами, а также генерировать немного строк и геометрии. Есть парсер опций командной строки и клёвая SVG-рисовалка. Можно делать, например, так.
~~~~~
cout << Array::id(10).shuffled().add1() << endl; // permutation of elements from 1 to 10
cout << Tree::random(100000, 20) << endl; // "long" tree with elongation 20
pair<string, string> test = rnds.antiHash({{mod1, base1}, {mod2, base2}}, "a-z", 10000); // should be s...
24.
Codeforces Round #870 (Div. 2) Editorial Все задачи названы в честь песен моей любимой группы Hippie Sabotage. Рекомендую их послушать!
[problem:1826A]
<spoiler summary="Подсказка1">
Проверьте число лжецов независимо.
</spoiler>
<spoiler summary="Подсказка2">
Как проверить, что лжецов ровно $x$?
</spoiler>
<spoiler summary="Решение">
[tutorial:1826A]
</spoiler>
C++ реализация: [submission:204718333]
[problem:1826B]
<spoiler summary="Подсказка1">
Как решать задачу для $n = 2$?
</spoiler>
<spoiler summary="Подсказка2">
Как решать задачу для $n = 4$?
</spoiler>
<spoiler summary="Решение">
[tutorial:1826B]
</spoiler>
C++ реализация: [submission:204718497]
[problem:1826C]
<spoiler summary="Подсказка1">
Каким свойством обладает число опций, присутствующее в бесконечном числе раундов?
</spoiler>
<spoiler summary="Подсказка2">
Выберете самое маленькое такое число.
</spoiler>
<spoiler summary="Подсказка3">
Как это число и число $m$ относятся к ответу?
</spoiler>
<spoiler s...
Как выбрать третий запрос, чтобы два кандидата не были слишком
Tutorial of Codeforces Round 870 (Div. 2)
25.
IOI 2017, второй тур <center><a style="font-size:20pt;" href="http://scoreboard.ioi2017.org/Ranking.html">Таблица результатов</a></center>
**SPOILER ALERT**: в комментариях и теле этого поста, скорее всего, будут обсуждаться задачи соревнования, поэтому если вы участвуете в каком-либо онлайн-зеркале, либо хотите порешать задачи самостоятельно, будьте к этому готовы. <br />
<spoiler summary="Краткий обзор задач">
Авторы соревнования, кажется, решили сделать самый оригинальный проблемсет со времён IOI 2010, и предложили во втором туре две интерактивки и одну обычную задачи.
[Prize](http://ioi2017.org/tasks/day2/prize/prize-RUS.pdf). Это интерактивная задача. В ряд расположены $n \leq 200\,000$ неизвестных целых положительных чисел, причём единичка ровно одна, и если есть $x$ чисел, равных $t$, то чисел, равных $t+1$, хотя бы $x^2 + 1$. Мы можем спрашивать про позицию ряда, в ответ нам возвращается количества чисел слева и справа, меньших стоящего на выбранной позиции. Требуется за определённое кол...
26.
Editorial of Codeforces Round 741 (Div. 2) <p align="right"><small>Will we, will you...<br>Can we, can you, can we change?
<p align="left">
[problem:1562A]
<spoiler summary="Подсказка 1">
Попробуйте рассмотреть такие отрезки, где $l \le \lfloor \frac{r}{2} \rfloor + 1$.
</spoiler>
<spoiler summary="Подсказка 2">
Теперь подумайте, что делать, если это условие не выполняется.
</spoiler>
<spoiler summary="Решение">
[tutorial:1562A]
</spoiler>
<spoiler summary="Код C++ (Wind_Eagle)">
~~~~
#include <iostream>
using namespace std;
int l, r;
void solve() {
if (r < l * 2) {
cout << r - l << endl;
}
else {
cout << (r - 1) / 2 << endl;
}
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> l >> r;
solve();
}
}
~~~~
</spoiler>
[problem:1562B]
<spoiler summary="Подсказка 1">
Попробуйте рассмотреть небольшие числа, например, состоящие из трех цифр.
</spoiler>
<spoiler summary="Подсказка 2">
Теперь подумайте, какое...
Tutorial of Codeforces Round 741 (Div. 2)
27.
Codeforces Round #816 (Div. 2) editorial Привет, Сodeforces!
Мы очень благодарны Вам за участие в нашем раунде.
Спасибо [user:Qwerty1232,2022-08-12] за помощь при написании разбора.
[problem:1715A]
<spoiler summary="Совет #0">
_Не сомневайся в себе, не сомневайся в своем решении. Не доказывай. Тестирующая система существует чтобы тестировать. Засылай._
</spoiler>
<spoiler summary="Подсказка #1">
Несколько наблюдений, если $(n; m) \neq (1; 1)$:
- Сергей будет телепортироваться только 1 раз
- Марго может не использовать порталы ни разу
</spoiler>
<spoiler summary="Подсказка #2">
Сергей и Марго будут двигаться только по направлению к целям (Сергей по увеличению $x$ и $y$, Марго по уменьшению $x$ и увеличению $y$.
</spoiler>
<spoiler summary="Подсказка #3">
Марго может двигаться по одному маршруту независимо от размеров доски.
</spoiler>
<spoiler summary="Решение">
### [problem:1715A]
_Для удобства скажем, что вверх — по уменьшению x координаты, вниз — по увеличению x коорди...
Tutorial of Codeforces Round 816 (Div. 2)
28.
Разбор Educational Codeforces Round 38 <spoiler summary="A. Исправление слов">
Подсказка: Когда гласная остается в строке?
<spoiler summary="Решение">
Пройдем по строке и выведем только согласные и те гласные, перед которыми не стоит гласной.
[Исходный код решения](https://pastebin.com/J0py2Gef)
</spoiler>
</spoiler>
<spoiler summary="B. В погоне за призом">
Подсказка $1$: Никогда не выгодно возвращаться. Там, где вы прошли, не осталось призов.
<spoiler summary="Подсказка 2">
Выгодно собирать призы в следующем порядке: некоторый префикс отходит вам, остальные — вашему другу (некоторый суффикс).
<spoiler summary="Решение">
Можно найти итоговое время по информации о длине префикса. Формула получается $\min(a_n - 1, 10^6 - a_1, \min \limits_{i = 1}^{n - 1} (\max(a_i - 1, 10^6 - a_{i + 1})))$.
[Исходный код решения](https://pastebin.com/mKhxYUxK)
</spoiler>
</spoiler>
</spoiler>
<spoiler summary="C. Подбираем тесты">
Подсказка: Для начала решим задачу, обозначенную в условии. Формула ...
графе на соответствующем отрезке запросов. Если некоторое ребро присутствует с
запроса $l$ позапрос
29.
Heavy-Light decomposition, logN на get-запрос **Коротко:**
Речь пойдет в основном про Heavy-Light decomposition (далее HLD).
Мне интересно, существует ли реализации HLD, допускающие change-запросы и работающие в среднем за $O(\log N)$ на get-запрос. Если да, пожалуйста, ссылку в студию. Если нет, докажите (опровергните), пожалуйста, идею кэширования (ниже подробно описана).
**Подробно**
[cut]
**:**
1) Введение
HLD или, иначе говоря, покрытие дерева вертикальными путями, позволяет отвечать на различные запросы на дереве... Как дерево отрезков на массиве, только на путях дерева. Почитать про HLD можно на [е-maxx.ru](http://e-maxx.ru/algo/heavy_light).
2) Условие задачи
Я не буду стремиться обобщить свои мысли, а приведу их на примере конкретной задачи: у каждой вершины дерева $v$ есть значение $a[v]$, нужно уметь делать операции $a[v] = x$, и $getMax(a, b)$ -- найти максимум на пути от $a$ до $b$. Задачу можно посылать на тимус [1553. Caves and Tunnels](http://acm.timus.ru/problem.aspx?space=1&num=1553) (н...
Heavy-Light decomposition, logN на get-запрос, $O(\log N)$ на get-запрос. Если да, пожалуйста, ссылку в студию. Если нет,
докажите (опровергните, get-запрос. Если да, пожалуйста, ссылку в студию. Если нет, докажите
(опровергните), пожалуйста, идею, , всегда (кроме случая в самом верху) считает максимум на префиксе, т.е. запрос
зависит только от вершины, Вопрос #4: может быть, я туплю, и задача на самом деле решается за $O(\log N)$
назапрос, но проще, запрос. Link-Cut за $O(\log N)$, если использовать Splay дерево (почитать можно
[здесь](http
30.
Codeforces Round #932 (Div. 2) Разбор [problem:1935A]
Идея: [user:i_love_penguins,2024-02-24] <br> Разработка: [user:i_love_penguins,2024-02-24] <br> Разбор: [user:i_love_penguins,2024-02-24]
<spoiler summary="Подсказки">
<spoiler summary="Подсказка 1">
Ответ всегда будет иметь префикс либо $s$, либо перевернутую строку $s$.
</spoiler>
<spoiler summary="Подсказка 2">
Добавлять строку в конец требуется не более одного раза.
</spoiler>
</spoiler>
<spoiler summary="Разбор">
Пусть $t$ — перевернутая строка $s$. Заметим, что нам выгодно использовать операцию 1 (добавление перевернутой строки в конец) не более одного раза. Действительно, получив какую-то строку, оставшиеся операции потратим просто на переворот строки. Тем самым получим исходную строку, либо перевернутую в зависимости от четности количества оставшихся операций.
Несложно увидеть, что ответ всегда будет иметь префикс либо $s$, либо $t$. Тогда найдем две лексикографически минимальные строки с префиксом $s$ и $t$. Это будут строки:
...
Tutorial of Codeforces Round 932 (Div. 2)
31.
Codeforces Round #612 Всем привет!
Сейчас проходит зимняя смена ЛКШ (Летней Компьютерной Школы), и мы в составе параллели А*+ с ее преподавателями подготовили полноценный <a href="/contests/1286,1287" style="color:#03A89E !important; font-weight:bold">Codeforces Round</a>.
Раунд состоится в [contest_time:1286] и продлится 2 часа. В каждом дивизионе будет предложено по 6 задач.
Задачи раунда были придуманы и подготовлены [user:ismagilov.code,2020-01-04], [user:devid,2020-01-04], [user:Volkov_Ivan,2017-05-29], [user:Jatana,2020-01-04], [user:karasek,2020-01-04], [user:polinarria,2020-01-04], [user:cookiedoth,2020-01-04], [user:AlesyaIvanova,2020-01-04], [user:doktorkrab,2020-01-04], [user:AliceG,2020-01-04], [user:D.Pavlenko,2018-01-04], [user:VFeafanov,2020-01-04], [user:LordVoidebug,2020-01-04], [user:forestryks,2020-01-04], [user:Ilistratov,2020-01-04], [user:seiko.iwasawa,2020-01-04], [user:DeadInsideOnTest993,2020-01-04], [user:Drozd_off,2020-01-04] под руководством преподавателей [user:PavelKun...
Announcement of Codeforces Round 612 (Div. 1)
Announcement of Codeforces Round 612 (Div. 2)
32.
Чемпионат КРОК 2012 — Раунд 1 — разбор задач **A.** Решение в лоб за $O(n)$ (моделирование всех n раундов) получает TL. Ускорим наивное решение --- рассмотрим раунды на отрезках [1..mk], [mk+1..2mk], [2mk+1..3mk] и так далее. Нетрудно заметить, что результаты раундов на этих отрезках будут повторяться. Поэтому промоделируем только один из этих отрезков, а затем учтем его [n/(mk)] раз ([x] --- деление нацело). Остаточек из n%(mk) последних раундов промоделируем отдельно. Итого получаем решение за $O(mk)$, которое легко проходит по времени.
Авторы --- ~Ripatti,2012-04-06 и ~Gerald,2012-04-06
[cut]
.
**B.** Построим двудольный граф на n+m вершин. Вершины из первой доли соответствуют строчкам, вершины из второй --- столбцам. Ребро соединяет две вершины тогда и только тогда, когда на пересечении соответствующих строки и столбца находится колонна.
Изначально луч смерти полностью покрывает только последнюю строчку таблицы --- то есть, только одну вершину в нашем графе. Когда мы делаем колонну магической, то мы даем "пройти" л...
Найдем как-нибудь, для каждого человека такое количество. Теперь пусть у нас
естьзапрос, какая, Опишем, как быстро отвечать за запрос количества точке в области, которая имеет
специальный вид, запрос, какая максимальная группа содержит точку ($x_i, y_i$) и ($x_j, y_j$).
Раз в этой группе
Tutorial of Croc Champ 2012 - Round 1
33.
Группы на Codeforces <img src="http://assets.codeforces.com/images/groups/group.jpg" style="float:right; margin: 0 1em 1em 1em;"/>
Привет, Codeforces!
Сегодня я хочу рассказать о новой функциональности Codeforces — о _группах_. Теперь вы можете создавать группы,
приглашать в них пользователей, добавлять в группы соревнования и участвовать в них все вместе.
#### Как создать группу
Чтобы создать группу необходимо иметь рейтинг участника Div. 1. Если у вас есть возможность создать группу, то на странице [Группы](/groups)
у вас будет соответствующая ссылка.
При создании группы кроме названия можно указать:
* описание — может содержать простой HTML,
* логотип — будет сиять на каждый странице вашей группы,
* ссылку на внешний веб-сайт группы.
[cut]
<center><img src="http://assets.codeforces.com/images/groups/new-group-ru-65.png" style="border:1px solid gray;margin-top:1em;"/></center>
#### Видимость группы
Бывают открытые и закрытые группы. Открыт...
34.
Разбор Codeforces Round #572 Коды были добавлены!
К некоторым задачи были добавлены челленджи(по большей части простые), которые возникли у нас при создании задач. Не стесняйтесь делиться решениями к ним и задавать любые вопросы в комментариях!
Киану Ривз
----------
Если строка хорошая, то ответом является сама. Иначе, ответ равен 2, тогда можно вывести всю строку без последнего символа и последний символ отдельно. Сложность решения $O(n)$.
[код](https://pastebin.com/Dc0gtG9n)
Числа на окружности
----------
Будем считать, что массив отсортирован. Для начала заметим, что если $a_n \ge a_{n - 1} + a_{n - 2}$, то ответ — NO (т.к. $a_{n}$ будет не меньше суммы своих соседей). Мы утверждаем, что во всех остальных случаях ответ — YES. Одной из возможных конструкций (для уже отсортированного массива) является:
$a_{n - 2}, a_{n}, a_{n - 1}, a_{n - 4}, a_{n - 5}, \ldots ,a_1$
Легко заметить, что все числа кроме $a_n$ будут иметь хотя бы одного соседа не меньше их. Сложность решения...
Tutorial of Codeforces Round 572 (Div. 1)
Tutorial of Codeforces Round 572 (Div. 2)
35.
CF-Predictor — Знай свой рейтинг! <spoiler summary="UPD 02.09.2018">
Сегодня выпустил небольшое обновление в связи с увеличившим количеством пользователей, если вдруг заметите проблемы в работе, пишите, пожалуйста, сюда в комментарии или мне в личку, или в телеграм.
</spoiler>
Всем привет! Я на прошлом контесте предлагал всем желающий потестировать мой сервис предсказания изменений рейтинга. Сейчас я рад представить его!
Огромное количество Ваших нервных клеток погибает, так и не дождавшись обновления рейтинга. Хватит это терпеть! Теперь Вы можете использовать данный сервис для приблизительно вычисления изменения рейтинга.
Наиболее интересная составляющая — расширение для хрома. Оно изменять страницу положения, добавляя предсказываемые дельты. Расширения доступны для 3х браузеров:
[](https://chrome.google.com/webstor...
**Chrome extension** отсылает запрос к web role, получает JSON ответ и
модифицирует страницу с
36.
Разбор задач Codeforces Round #285 [problem:501A]
В этой задаче требовалось сделать то, что написано в условии. Считать числа и определить у кого из ребят больше баллов.
Асимптотика: $O(1)$.
[problem:501B]
Для начала немного переформулируем задачу. Был дан ориентированный граф, вершинами которого являются хэндлы пользователей, а ребрами запросы изменения хэндлов. Он состоит из некоторого количества цепочек, нужно было найти их количество, начальные и конечные вершины каждой цепочки. То есть у каждой вершины входящая и исходящая степень не превосходит $1$. Ввиду последнего ограничения, ребра этого графа можно хранить в словаре(в C++ — **std::map\unoredered_map**, Java — **TreeMap\HashMap**), где ключом является вершина из которой исходит ребро, а значением — вершина, в которую оно входит.
Каждому уникальному пользователю соответствует вершина с нулевой входящей степенью. Из всех таких вершин нужно переходить по ребру, до тех пор, пока существует переход. Чтобы найти вершины с нулевой степ...
]$, где $j$-индекс запроса. Итак, обрабатывая очередной запрос $v$, мы
пробегаем по его битам от, Итак, обрабатывая очередной запрос $v$, мы пробегаем по его битам от младшего к
старшему. В случае, Обрабатывая очередной запрос разобьем пути $(a, b)$ и $(c, d)$ на части,
целиком принадлежащие, Теперь для ответа на запрос нам необходимо находить наибольший общий префикс
двух подстрок в строке
Tutorial of Codeforces Round 285 (Div. 2)
Tutorial of Codeforces Round 285 (Div. 1)
37.
Codeforces Round #897 (Div. 2) Editorial Всем привет! Просим прощения за задержку >_<
Надеемся, что вам понравились наши задачи! Извините за то, что лимиты по времени и памяти в некоторых задачах были слишком жесткими и решения на Java не проходили С (кстати, у одного из авторов бывшый ник — "java." :D). Постараемся не допустить таких ошибок вновь.
Оставляйте впечатления и пожелания в комментариях! Спасибо за участие!
[1867A — green_gold_dog, массив и перестановка](https://codeforces.com/contest/1867/problem/A)
Автор: [user:green_gold_dog,2023-09-12]
<spoiler summary="Разбор">
Из минимального числа вычтем $n$, из следующего $n - 1$, из следующего $n - 2$, $\ldots$, из максимального $1$. Тогда количество различных элементов будет $n$. Очевидно лучшего результа достичь невозможно.
Докажем, что количество различных элементов будет равно $n$. Допустим $c_i = c_j$, тогда без ограничения общности скажем, что $b_i > b_j$, тогда $a_i \leq a_j$, значит $c_i = a_i - b_i$ < $a_j - b_j = c_j$. Противоречие....
Пусть $i$ "--- позиция в которой начинается первый вторичный запрос. Заметим,
что после этого, Теперь будем сдвигать последний подотрезок запроса на единицу вправо и делать
новыйзапрос, пока
Tutorial of Codeforces Round 897 (Div. 2)
38.
Количество префиксных максимумов на отрезке с изменениями и с линейной памятью Дана следующая задача: дан массив целых чисел $a_1, \ldots, a_n$, а также $q$ запросов одного из двух видов:
1. $a_i += x$, где $l \leq i \leq r$.
2. узнать количество индексов $i$, где $l \leq i \leq r$ и $a_j < a_i$, для всех $j:$ $l \leq j < i$. (Или по-человчески — количество префиксных максимумов на отрезке)
Очень хочется это решать быстрее, чем за $O(sqrt(n))$ на запрос.
Рассмотрим более легкий вариант, когда у нас нет запросов изменения. Тогда можно просто сделать Дерево отрезков, где в вершине хранится отсортированный список префиксных максимумов, если наш отрезок — это отрезок, соответствующий вершине дерева отрезков. Тогда мы должны просто сделать алгоритм, анологичный Merge Sort Tree, только мы должны в запросе вершины, на которые мы разбиваем разбиваем запрос, рассматривать слева направо и хранить максимум среди предыдущих элементов на подходящем отрезке, и к ответу прибавлять количество элементов в вершине, больших максимума до этого, а затем обнов...
разбиваем запрос, рассматривать слева направо и хранить максимум среди
предыдущих элементов на подходящем, Очень хочется это решать быстрее, чем за $O(sqrt(n))$ на запрос., Теперь нормальное решение за $O(n)$ памяти и $O(log(n)^2)$ на запрос., Это работает за $O(log(n)^2)$ на запрос, а также $O(nlog(n))$ памяти и времени
на построение., Это уже работает за $O(log(n)^2)$ на запрос, но в этом случае будет построение
за $O(nlog(n)^2)$, а
39.
Heavy-Light Decompositon за O(log n) Задача
------------------
Дано дерево на $n$ вершинах, в вершине $v$ записано число $a_v$. Поступают запросы двух видов:
1. Найти максимальное число на кратчайшем пути из вершины $u$ в вершину $v$.
2. Сделать $a_v = x$.
Варианты решений
------------------
Эта задача очень известна, поэтому скорее всего вам в голову пришло решение, использующее Heavy-Light Decompositon (или Link-Cut Tree, если вы большой любитель splay-деревьев). Первый вариант в стандартной реализации работает за $O(log^2~ n)$, второй работает за $O(log~ n)$, однако для его использования нужны более специфичные знания. Хочется добиться более хорошей асимптотики HLD, используя какие-то несложные идеи. Оказывается, что это возможно.
$O(log^2~ n)$ на запрос
------------------
Постараемся разбить дерево на вершинно непересекающиеся пути так, чтобы при запросе нам потребовалось разбить путь между вершинами из запроса на небольшое количество отрезков так, чтобы каждый из них лежал в каком-то одном пути.
На...
если следить за такой величиной, можно понять, что мы добились $O(log~ n)$ на
запрос, так как если мы, $O(log^2~ n)$ на запрос ------------------ Постараемся разбить дерево на
вершинно, $O(log~ n)$ на запрос ------------------ Для доказательства асимптотики в
предыдущем пункте мы, Для начала подумаем, как в таком дереве отвечать на запрос максимума на
отрезке. Для этого, Для смены $a_v$ достаточно сделать один запрос в дерево отрезков., Основная проблема кроется в дереве отрезков. Оно отвечает на запрос за $O(log~
n)$ (или $O(log(r, Теперь, что бы ответить на запрос, достаточно узнать максимум на путях $(lca(u,
v), u)$ и $(lca(u
40.
Разбор Codeforces Round #169 [**A. Проблемные обеды**](http://codeforces.com/contest/276/problem/A)
Для нахожения ответа переберем все возможные рестораны, в которых могли пообедать три Кролика. Посчитаем ответ для каждого ресторана. Из всех ответов выберем максимальный. Ответ для ресторана $i$ считается по формуле, описанной в условии. Сложность решения $O(N)$.
[Код на С++](http://pastebin.com/cJK5K017)
[Код на Java](http://pastebin.com/D800mDax)
[**B. Девочка и игра**](http://codeforces.com/contest/276/problem/B)
Посчитаем количество букв, которые встречаются в строке $s$ нечетное количество раз. Пусть это количество равно $k$.
Заметим, что если $k=0$, то первый игрок сразу же побеждает — он легко может составить палиндром, поставив одинаковые буквы в разные концы строки (так как общее количество всех букв четное, он сможет это сделать).
В случае $k=1$ первый игрок опять-таки сразу же побеждает — сначала он строит палиндром из букв, которые встречаются четное количество раз, а...
Предположим что поступил запрос на добавление на отрезке $l$ до $r$ значения
$val$., При обработке запроса типа $0$ посмотрим, затронет ли он корень. Если запрос
затрагивает корень, Пусть поступил запрос на нахождения значения элемента с индексом $v$.
Tutorial of Codeforces Round 169 (Div. 2)
41.
Грустная история про перенос раунда 383 Добрый день.
К сожалению, сегодня (в пятницу) провести раунд не получится :-(
Если коротко, то это по техническим причинам. Для интересующихся изложу более подробный вариант.
В ночь на четверг я получил смс-ку, что на сервере для бэкапов баз данных место израсходовано на 90%. На этом сервере хранятся три копии базы данных за последние трое суток. Места там примерно 2 терабайта, а база данных подросла более чем до 600 гигабайт, поэтому и стало в упор.
Так как последующие сутки я планировал провести в поезде по дороге на NEERC, то стереть из базы данных неважные данные (по моим оценкам это освободило бы несколько десятков гигабайт). Я запустил запрос на присвоение пустой строке одного поля в таблице и понял, что сделал это зря. В этой таблице несколько десятков миллионов записей и, видимо, отработать быстрее чем за несколько часов шансов у него не было. В результате я убил этот запрос, сделав KILL QUERY. Но база продолжала лагать, я решил её перезапустить. Этот процесс тоже з...
оценкам это освободило бы несколько десятков гигабайт). Я запустил запрос на
присвоение пустой строке, запрос на присвоение пустой строке одного поля в таблице и понял, что сделал
это зря. В этой таблице
42.
Обновления Codeforces (апрель-май 2015) Привет!
Работа на Codeforces никогда не стоит на месте, и вот пришло время рассказать вам о последних изменениях, ранее не упоминавшихся.
### Testlib
- testlib переехал на [GitHub](https://github.com/mikemirzayanov/testlib), выпущена новая версия 0.9.9 с поддержкой C++11. Добавлены генераторы двудольных графов, корневых и простых деревьев.
### Polygon
- Добавлена базовая поддержка групп тестов. Теперь вы можете для каждого теста указать его группу, запускать invocations по группам, добавлены строки с summary по группам на странице просмотра invocation'а. Если для теста указана группа, она появится в дескрипторе задачи (например `<test cmd="gen 1 2" group="testGroup" method="generated"/>`). Эта функциональность может оказаться полезной при подготовке задач для школьных олимпиад.
- Добавлена возможность просмотра условий и валидатора задачи/контеста на одной странице. Это значительно упрощает нахождение ошибок в переводах и валидаторе (раньше для этого нужно было открывать их...
статуса. Такое иногда возникало когда запрос уходил на другой сервер
Codeforces. - Исправлен баг с
43.
Еще о запросах на прямоугольниках… В детстве мне очень нравилась задача 1147 с тимуса [statements](http://acm.timus.ru/problem.aspx?space=1&num=1147). Нравилась в первую очередь тем, что я знал кучу решений, но никак не мог придумать ни одного быстрее, чем за $N^2$. Сейчас у меня наконец появились мысли, как решать эту задачу за NlogN.
Обобщим сперва задачу, чтобы асимптотику оценивать только через N: пусть $A, B < 10^9, color < 10^6$
Я знаю следующие решения, все они используют сжатие координат:
1. Квадродерево за O($N^2$)
2. Решение одномерной задачи деревом отрезков за O(NlogN) => O($N^2$ logN)
3. Решение одномерной задачи проходом слева направо с кучей за O(NlogN) => O($N^2$ logN)
4. Решение одномерной задачи с помощью СНМ за O(N) => O($N^2$) [здесь в оценке я опускаю обратную функцию Аккермана]
5. **Новое:** Решение за O(NlogN) [использует разделяй и властвуй по X и сжатие координат при переходе к подзадаче].
Если кто-то знает что-то еще, расскажите, пожалуйста, в комментариях, мне это буде...
44.
Разбор задач Educational Codeforces Round 13 ### [problem:678A]
Задачу предложил Әбдірахман Исмаил [user:Ismail_A,2016-06-14].
Нам нужно найти минимальное $x$, что $x*k>n$. Легко видеть, что $x=\lfloor\frac nk\rfloor+1$.
Для подробного знакомства с математическими функциями пола и потолка я рекомендую книгу
авторов Грэхем, Кнут, Паташник "Конкретная математика". В этой книге есть отдельная глава, посвящённая
этим функциям и их свойствам.
<spoiler summary="Решение на С++">
~~~~~
li n, k;
bool read() {
return !!(cin >> n >> k);
}
void solve() {
cout << (n / k + 1) * k << endl;
}
~~~~~
</spoiler>
Сложность: $O(1)$.
### [problem:678B]
Задачу предложил Артур Яворски [user:KingArthur,2016-06-14].
Два календаря совпадают если и только, если в них одинаковое количество дней и они начинаются
с одного дня недели. Таким образом, достаточно было просто перебрать следующий год, поддерживая
первый день недели в году. На самом деле день недели каждый год увеличивается на единицу. Исключением...
, чтобы ответить на один запрос третьего типа нужно взять максимум по прямым
нижнего огибающего множества
Tutorial of Educational Codeforces Round 13
45.
Codeforces Round #922 (Div. 2) Разбор Всем привет!
Надеемся, что вам понравились наши задачи!
Спасибо за участие!
[1918A — Кирпичная стена](https://codeforces.com/contest/1918/problem/A)
Автор: [user:ooaa,2024-01-30]
<spoiler summary="Разбор">
Устойчивость стены — это число горизонтальных кирпичей минус число вертикальных.
Так как горизонтальный кирпич длины хотя бы $2$,
в одном ряду можно разместить не более $\lfloor\frac{m}{2}\rfloor$ горизонтальных кирпичей.
Поэтому ответ не превосходит $n \cdot \lfloor\frac{m}{2}\rfloor$. С другой стороны,
если размещать в ряду горизонтальные кирпичи длины $2$, и, когда $m$ нечётно,
последний кирпич длины $3$,
то в каждом ряду будет ровно $\lfloor\frac{m}{2}\rfloor$ горизонтальных кирпичей, и вертикальных кирпичей в стене вообще не будет.
Так достигается максимальная устойчивость $n \cdot \lfloor\frac{m}{2}\rfloor$.
Решение — это одна формула, асимптотика $O(1)$.
</spoiler>
<spoiler summary="Решение">
~~~~~
#include <bits/stdc++.h>
...
Tutorial of Codeforces Round 922 (Div. 2)
46.
Разбор Codeforces Round #144 Задачи, которые не успели написать, разберу кратко. Задавайте вопросы.
[problem:233A]
Идея: [user:Gerald,2012-10-14] Реализация: [user:tunyash,2012-10-14] Разбор: [user:Moskupols,2012-10-14]
Эту задачу можно было решать разными способами, например, таким: рассмотрим перестановку $p$, в которой $p_i = i$, то есть просто последовательность чисел от $1$ до $n$. Очевидно, для неё условие $p_{p_i} = i$ выполняется всегда. Осталось только преобразовать её таким образом, чтобы выполнялось и второе условие: $p_i \neq i$. Для этого поменяем местами каждые два соседних элемента, т.е. для каждого $k: k*2 \le n$ поменяем местами значения $p_{2k-1}$ и $p_{2k}$. Нетрудно убедиться, что для полученной перестановки оба условия выполняются всегда.
[problem:233B]
Идея: [user:tunyash,2012-10-14] Реализация: [user:tunyash,2012-10-14], [user:Gerald,2012-10-14] Разбор: [user:Moskupols,2012-10-14]
Для начала найдем диапазон значений, которые может принимать $s(x)$. Так как из уравнения ...
выбранного столбца за n/32 на запрос (просто сделаем and битсетов). На
картинке кружочками обведены, , обращающихся к lcp на отрезке. - запрос на число суффиксов, которые лежат в
суффиксном массиве на этом, Если массив строить за $O(n \log_2 n)$, запрос $lcp$ выполнять за $O(1)$ с
предподсчетом за $O(n, Отсюда возникает следующая идея: для ответа на запрос нам достаточно узнать,
сколько подотрезков, Получим асимптотику $\log max(a_i,b_i)$ на запрос (логарифм возникает из
соображения о том, что
Tutorial of Codeforces Round 144 (Div. 1)
Tutorial of Codeforces Round 144 (Div. 2)
47.
VK Cup 2012 Round 3 — Разбор [problem:164A]
**Кратко о решении --- dfs, O(E).**
Пустим поиск в глубину из всех вершин, где переменная присваивается. Пометим все посещенные.
Пустим поиск в глубину по обратным ребрам из всех вершин, где переменная используется.
Запретим ему проходить по вершинам, где переменная присваивается.
Пометим все посещенные.
Вершины помеченные оба раза --- это и есть те вершины, где состояние Васи кого-то волнует
[problem:164B]
**Кратко о решении --- метод двух указателей, O(N).**
Давайте для удобства предположим, что каждый символ в каждой строке встречается ровно один раз.
Тогда у нас есть перестановка $p_i$ (позиция во второй строке $i$-го символа первой строки)
Решение за квадрат теперь такое: фиксируем начало подстроки и идем по ней вперед, при этом параллельно идем
по подпоследовательности и следим, что и там, и там мы не прошли больше круга.
Решение за линию.
Будем теперь идти двумя указателями "начало подстроки" и "конец подстроки".
Параллельно бу...
48.
Разбор задач Codeforces Round #294 (Div. 2) [problem:519A]
------------------
**Автор:** [user:Bekzhan.Kassenov,2015-02-28]
В этой задаче необходимо было найти чья шахматная позиция сильнее.
**Решение:** Пробегаемся по всей доске, складывая веса фигур игроков, и в конце выводим ответ.
**Асимптотика:** $O(n^2)$, где n — длина стороны доски (в этой задаче — 8)
**Код:** [submission:10083191]
[problem:519B]
------------------
**Автор:** [user:ADJA,2015-02-28]
В этой задаче вам было дано 3 массива. Второй содержал все элементы первого, за исключением одного, третий массив содержал все элементы второго, за исключением одного. Необходимо было вывести удаленные элементы.
**Решение:** Я опишу простейшее решение этой задачи:
Обозначим сумму элементов в первом, втором и третьем массиве как $a$, $b$ и $c$ соответственно.
Ответом будут числа $a - b$ и $b - c$
Также существуют множество других решений, использующих map, xor и прочее.
**Асимптотика:** $O(N)$
**Код:** [submission:10083248]
[...
Асимптотика: $O(logN)$ на запрос, $O(MlogN)$ на все запросы.
49.
Codeforces Round #404. Разбор. Перед вами разбор задач сегодняшнего контеста. Я постарался расписать решения задач как можно более подробно, но если что-то будет непонятно, смело пишите в комментариях! :)
[problem:785A]
<spoiler summary="Подсказка">
404 Not Found
</spoiler>
<spoiler summary="Разбор">
[tutorial:785A]
</spoiler>
<spoiler summary="Код C++">
~~~~~
#include <iostream>
#include <map>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
map<string, int> vals;
vals["Tetrahedron"] = 4;
vals["Cube"] = 6;
vals["Octahedron"] = 8;
vals["Dodecahedron"] = 12;
vals["Icosahedron"] = 20;
int n; cin >> n;
int res = 0;
for (int i = 0; i < n; i++) {
string s; cin >> s;
res += vals[s];
}
cout << res << endl;
return 0;
}
~~~~~
</spoiler>
<spoiler summary="Код Java">
~~~~~
import java.io.*;
import java.util.*;
public class PolyhedronSums {
public static void main(String[] args) throws Exception {
BufferedReader reader = new...
Tutorial of Codeforces Round 404 (Div. 2)
50.
Разбор задач Looksery Cup 2015 **UPD.** Появился разбор задачи Е. Мы просим прощения за задержку, он получился действительно трудоемким, и, чтобы как-то загладить свою вину, мы публикуем несколько интерпретаций решения.
**A. Определение лиц**
Автор: [user:Monyura,2015-06-06]
Для решения этой задачи следует перебрать все квадраты 2х2 и проверить, что переставив буквы можно получить слово "face". Это можно удобно сделать, например, отсортировав буквы квадрата в алфавитном порядке и проверив, что отсортированное множество равно "acef"(Отсортированный порядок букв слова "face").
**B. Вечеринка в Looksery**
Автор: [user:Igor_Kudryashov,2015-06-06]
При любом раскладе существует такое множество людей, что, если они придут и разошлют сообщения своим контактам, то каждый сотрудник получит количество сообщений отличное от того, что указал Игорь. Покажем как построить это множество. Рассмотрим 2 случая.
Ни одно из чисел, предложенных Игорем, не равно нулю. Тогда если никто не придет на вечеринку, то всем ...
$. В обоих случаях мы получаем простую сравнимость и запрос на отрезке,
описанный выше. Если идти
Tutorial of Looksery Cup 2015
51.
Codeforces Round #359 Editorial Если заметите неточности или ошибки, сообщите личным сообщением. <br> <br>
[Div2A Раздача мороженого](http://codeforces.com/contest/686/problem/A) <br>
Автор идеи: [user:cdkrot,2016-06-24] <br>
Подготовил задачу: [user:ch_egor,2016-06-23] <br>
В задаче требовалось просто реализовать то, что было сказано в условии. <br>
Если у вас не получилось, то возможно вы забыли использовать 64-битные типы данных, или сделали какую-то ошибку. <br>
Код правильного решения: <br> <br>
<spoiler summary="C++ code">
~~~~~
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cassert>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <bitset>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
typedef long long int int64;
typedef long double double80;
const int INF...
Ответ на запрос будем "Yes" тогда и только тогда, когда: $dp_l[l][u] = true$ и
$dp_r[r][u] = true
Tutorial of Codeforces Round 359 (Div. 1)
Tutorial of Codeforces Round 359 (Div. 2)
52.
Codeforces Round #260 — Разбор [problem:456A]
Решение: [submission:7407613];
В этой задаче надо было проверить существования таких $i$ и $j$, что $i \neq j$, $a[i] < a[j]$, $b[i] > b[j]$. Если существуют такие $i$ и $j$, то Леша рад.
Для этой задачи есть очень простое решение. Просто проверить, что для всех $i$ верно, что $a[i] = b[i]$. Если это так, то Леша не рад.
Доказательство очень простое. Давайте отсортируем массивы $a$ и $b$, как пары чисел, по возрастанию. Можно увидеть что Лёша рад, если есть хотя бы одна инверсия в массиве $b$, то есть существуют такие $i$ и $j$, что $b[i] > b[j]$ и $i < j$ ($i < j \Leftrightarrow a[i] < a[j]$, так как числа в массиве $a$ идут в возрастающем порядке). То есть это значит, что массив $b$ не отсортирован, и это значит, что $a \neq b$.
[problem:456B]
Решения: [submission:7407625], [submission:7407631];
В этой задаче надо было вычислить то, что просили в условии. Правда в лоб это не легко сделать.
Но если посмотреть на формулу, то можно сделать след...
Давайте сведем запрос $1$-го типа к двум более простым более простым запросам:, Так же легко быстро выполнять запрос 2-го типа. Нужно пройтись всего по
$O(\sqrt n)$ блокам, Теперь легко быстро выполнять запрос 1-го типа. Удалить число с $r$-ой позиции
мы можем за $O(\sqrt, Чтобы вычислять ответ на запрос быстрее, чем простой проход по прямым, нужно
ипользовать Convex, запрос будет равен:
Tutorial of Codeforces Round 260 (Div. 1)
Tutorial of Codeforces Round 260 (Div. 2)
53.
Разбор задач Educational Codeforces Round 12 ### [problem:665A]
Задачу предложил Сергей Эрлих [user:unprost,2016-04-20].
Рассмотрим интервал времени, когда Симион будет находиться на трассе строго между городами $(x_1, y_1)$, ($x_1=60h+m, y_1=x_1+t_a$).
Переберём встречный автобус. Пусть $(x_2, y_2)$ — это интервал времени, когда встречный автобус будет находиться строго между городами.
Если пересечение этих интервалов $(x=max(x_1, x_2), y=min(y_1, y_2))$ не пусто, то Симион посчитает этот автобус.
<spoiler summary="Решение на С++">
~~~~~
int a, ta;
int b, tb;
int h, m;
bool read() {
if (!(cin >> a >> ta)) return false;
assert(cin >> b >> tb);
assert(scanf("%d:%d", &h, &m) == 2);
return true;
}
void solve() {
int x1 = h * 60 + m;
int y1 = x1 + ta;
int ans = 0;
for (int x2 = 5 * 60 + 0; x2 < 24 * 60; x2 += b) {
int y2 = x2 + tb;
int x = max(x1, x2), y = min(y1, y2);
if (x < y)
ans++;
}
cout << ans << endl;
}
~~~~~
</spoiler>
Сложность: $O(1)$.
### [problem...
значение для состояние $nзапрос ``посчитать количество чисел не больше $n$ с
Tutorial of Educational Codeforces Round 12
54.
Codeforces Round #276 — Editorial [problem:485A]
Производство остановится только в том случае, если существует такое целое $K \geq 0$, что $a\cdot 2^{K}$ делится на $m$. Из этого следует, что $K$ может быть максимум порядка $log_{2}(m)$. Так как $K$ — это по сути сколько пройдёт дней до этого момента, то можно промоделировать описанные в условии задачи действия, например, в течение 20-ти дней (не забыв при этом про 64-битный тип данных). Если в какой-то момент производство остановилось, то ответ "Yes". Если не остановилось в течение этих дней, то оно не остановится никогда, а значит ответ "No".
[problem:485B]
Найдём минимальную длину, необходимую чтобы покрыть все точки по оси $Ox$ — это будет в точности $Maximum(x_{i}) - Minumum(x_{i})$. Аналогично и для оси $Oy$ — это $Maximum(y_{i}) - Minumum(y_{i})$. Так как нам необходим квадрат, то следует взять максимальную из этих двух величин в качестве длины его стороны.
[problem:484A]
Опишем функцию $f(L,R)$, которая будет ответом на задачу. ...
$tree_{height}$. Теперь, чтобы ответить на вопрос выше, нужно сделать запрос
на отрезке $[l,r]$ у, Заметим, что при поиске ответа на конкретный запрос можно воспользоваться
бинарным поиском по, Итоговая сложность — $O(logR)$ на один запрос., Построение дерева займёт $O(nlogn)$ времени и памяти. Ответ на запрос займёт
$O(log^{2}n)$ времени.
Tutorial of Codeforces Round 276 (Div. 1)
Tutorial of Codeforces Round 276 (Div. 2)
55.
Разбор Codeforces Round #319 Задача A. Div2.
Заметим, что число $x$ может встречаться в столбце $i$ только один раз — в строке $x / i$. Переберем столбец $i$, проверим, что $x$ делится нацело на $i$, а также $x / i \le n$. Если все условия выполнены, обновим ответ.
Асимптотика — $O(n)$
[Код](http://pastebin.com/yGMTt9KZ)
Задача B. Div2.
Рассмотрим два случая: $n > m$ и $n \le m$.
Пусть $n > m$, рассмотрим суммы на префиксах. По принципу Дирихле, найдутся две равные суммы по модулю $m$. Пусть $S_l mod m = S_r mod m$. Тогда сумма чисел на отрезке с $l + 1$ по $r$ по модулю $m$ равна нулю, то есть ответ точно "YES".
Пусть $n \le m$, то решим задачу динамикой за $O(m^2)$. Пусть $can[i][r]$ — можем ли мы, используя первые $i$ предметов, получить остаток $r$ от деления на $m$. Переходы в динамике понятны: либо мы берем предмет и переходим в состояние $can[i + 1][(r + a_i)\ mod\ m]$, либо не берем и переходим в состояние $can[i + 1][r]$.
Асимптотика — $O(m ^ 2)$.
[Код](h...
листе, отвечаем на соответствующий запрос.
Tutorial of Codeforces Round 319 (Div. 1)
Tutorial of Codeforces Round 319 (Div. 2)
56.
Zepto Code Rush 2014 — решения ## [problem:436A]
Автор разбора: [user:Fefer_Ivan,2014-06-14]
В задача А типы съеденных конфет должны все время менятся. Так что первая съеденная конфета определяет тип всех последующих конфет.
Возможных типа всего два, так что переберем тип первой съеденной конфеты.
Пусть в какой-то момент времени Ом Ном должен съесть конфету типа $t$ и может прыгать на высоту $h$.
Очевидно, что наиболее выгодным решением будет съесть конфету с наибольшей массой среди всех конфет, которые Ом Ном может съесть на текущем этапе.
Для решения задачи необходимо промоделировать процесс поедания конфет для начального $h = x$ и $t = [0, 1]$ и выбрать лучшее значение.
## [problem:436B]
Автор разбора: [user:Fefer_Ivan,2014-06-14]
Пронумеруем столбцы таблицы начиная с 0 слева направа, а строки начиная с 0 сверху вниз.
Теперь заметим, что в момент времени $t > 0$ в клетке $(x, y)$ могут находиться только $4$ паука:
* Паук, который движется влево и в начале был в клетке $(x, y + t)$.
* ...
Tutorial of Zepto Code Rush 2014
57.
Codeforces Round #814 (Div. 1, Div. 2) Разбор Извините за не очень хорошие примеры и поздний разбор. Это был наш первый раунд, поэтому он был очень напряженным для нас, но мы надеемся, что вам понравились задачи, несмотря на это!
[problem:1719A]
<spoiler summary="Подсказка 1">
Попробуйте посмотреть на четность $n, m$.
</spoiler>
<spoiler summary="Подсказка 2">
Игрок, который победит не зависит от стратегии.
</spoiler>
<spoiler summary="Подсказка 3">
Единственное, от чего зависит победивший игрок это четность $n, m$.
</spoiler>
<spoiler summary="Разбор">
Заметим, что игра закончится только тогда, когда фишка находится в правом верхнем углу (иначе можно сдвинуть её на $1$ клетку вправо или вверх). За все ходы фишка сдвинется на $n - 1$ вправо и на $m - 1$ вверх, значит, суммарная длина всех ходов равна $n + m - 2$ (длина хода — на сколько сдвинулась фишка за ход). Так как длина любого хода нечётна, то после любого хода Бурёнки сумма длин будет нечётна, а после любого хода Тони чётна. Значит, мы можем уз...
Существуют $L$ и $R$ такие, что ответ на запрос <> тогда и, максимум среди них, их можно посчитать изначально за $O(n log n)$ для одного
$d$, каждыйзапрос это, подсчет суммы $dp[mask][big]$, что позволит ответить на запрос за ~5000
(вместо 7000) обращений к, , то запишем для него номер $i$. Теперь для ответа на запрос $(i, k)$
достаточно бинпоиском найти, }]$ (для $big$ и $case$, лежащих на отрезке). Таким образом, на запрос можно
ответить за 7000 обращений
Tutorial of Codeforces Round 814 (Div. 1)
Tutorial of Codeforces Round 814 (Div. 2)
58.
Неофициальный разбор + обсуждение длинного тура Открытой олимпиады 2023-2024 Привет, Codeforces.
Вчера закончился длинный тур Открытой олимпиады этого года, который проходил с 25.11 по 15.01. В нём было много интересных задач, которые мне хотелось бы разобрать и обсудить в этом посте.
<spoiler summary="А на 100 баллов">
Нетрудно заметить, что если $t_{i + 1} - t_i \leq m$, то задачи $i$ и $i + 1$ будут сданы либо в один день, либо в соседние дни, а для того, чтобы условие *не* выполнялось, необходимо, чтобы какие-то два соседних момента времени находились в разных не соседних днях (тогда в день между ними не будет сдана ни одна задача). Если же
$t_{i + 1} - t_i \ge 2m$, очевидно, что между этими двумя моментами времени точно есть день, в который мы ничего не сдадим. Остаётся последний случай: $m \lt t_{i + 1} - t_i \lt 2m$. В этом случае "плохие" дни могут начинаться с момента $t_i + 1$ до момента $t_{i + 1} - m$.
Дальше нам каким-то образом нужно найти такой часовой пояс, чтобы никакой день в нём не начинался в "плохой" отрезок часов. Понятно, что ...
Кажется, что после такой модификации, запрос к ДО все ещё должен работать за
$O(n)$, но я не до
59.
RCC 2014 WarmUp Analysis [problem:417A]. Автор и реализация [user:Aksenov239,2014-04-17].
Сначала нужно заметить, что если $k$ больше либо равно, чем $n \cdot m$, то ответ — 0.
Нам осталось набрать $n \cdot m - k$ человек.
Есть три способа их набрать:
- Взять раунды только первого типа: $c\lceil \frac{n \cdot m - k}{n} \rceil$.
- Взять чуть раундов второго типа до числа, делящегося на $n$: $d(n - (n \cdot m - k) mod n) + c\lceil \frac{n \cdot m - k}{n} - 1 \rceil$.
- Взять только раунды второго типа: $d(n \cdot m - k)$.
Также в данной задаче можно было написать переборное решение — сколько мы берём раундов первого типа, и сколько раундов второго.
Код: [submission:6396283]
[problem:417B]. Автор и реализация [user:Aksenov239,2014-04-17].
Заведём массив $a$ на $10^5$ элементов, изначально заполненный $-1$, и в ячейке с номером $k$ будем хранить максимальный номер посылки $k$-го участника, который сейчас есть.
Будем обрабатывать посылки последовательно. Пусть обрабатывается посыл...
вершины. Тогда при ответе на запрос — мы находим, когда путь вливается
диаметр. На это отрезке, Итого, получаем время на запрос за $O(\frac{nlog(n)}{LEN} + LEN)$. Если мы
возьмём $LEN = \sqrt
Tutorial of RCC 2014 Warmup (Div. 2)
Tutorial of RCC 2014 Warmup (Div. 1)
60.
Codeforces Round #781 (Div. 2) Editorial Опять же, я надеюсь, что вам понравились все задачи. Делитесь своими идеями и альтернативными решениями в комментариях. Итак, разбор:
<spoiler summary="A: НОД против НОК">
[problem:1665A]
<spoiler summary="Разбор">
В данной задаче достаточно вывести $n - 3$, $1$, $1$, $1$. Нетрудно убедиться, что этот ответ подходит для любого $n \ge 4$.
</spoiler>
<spoiler summary="Реализация (C++, shishyando)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T --> 0) {
int n;
cin >> n;
cout << n - 3 << ' ' << 1 << ' ' << 1 << ' ' << 1 << '\n';
}
return 0;
}
~~~~~
</spoiler>
</spoiler>
<spoiler summary="B: Техника массивного клонирования">
[problem:1665B]
<spoiler summary="Разбор">
Будем действовать жадно. Найдём элемент в исходной версии, который встречается чаще всех. Пусть этот элемент равен $x$ и он встречается $k$ раз. Тогда сделаем такую версию массива, в которой все эле...
\le i \le 23$ будем спрашивать $\gcd(x + i, x + \text{lcm} + i)$, т.е запрос
$(i, \text{lcm} + i, отрезков на минимум, после чего для ответа на запрос необходимо не более чем
31 раз найти минимум
Tutorial of Codeforces Round 781 (Div. 2)
61.
Codeforces Round #239 Разбор задач Обратите внимание на бонусы в некоторых задачах, и если вы умеете их решать, пожалуйста, напишите об этом в комментариях.
[problem:408A]
В задаче нужно было найти время ожидания для каждой очереди, просуммировав покупки по всем людям, и найти минимум.
[problem:408B]
В задаче нужно было найти максимально длинную гирлянду, которую можно составить из тех элементов, что у нас есть.<br/>
Во-первых, если какой-то цвет нужен, но его нет, то ответ — -1.<br/>
Иначе, ответ всегда существует, и является целым числом. <br/>
Просуммируем ответы по всем цветам по отдельности. <br/>
Пусть у нас есть $a$ кусков бумаги некоторого цвета, а нужно — $b$. Тогда если $a >= b$, то к ответу можно прибавить $b$ — повесить $b$ кусков по одному метру, а если $a < b$, то к ответу можно прибавить $a$, использовав все куски, что есть в наличии. Итого, каждый цвет дает к ответу $min(a, b)$.
[problem:407A]
В задаче требовалось расположить прямоугольный треугольник с катетами $a...
предыдущие случаи, можно понять, что если поступает запрос L, R, K, нужно
сделать операции, Итак, для каждого фиксированного L делаем запрос на отрезке L..maxR(L) о самом
правом числе, не, Теперь запрос "Найти самое правое число, такое, что оно не превышает k".
Сначала дерево отрезков
Tutorial of Codeforces Round 239 (Div. 1)
Tutorial of Codeforces Round 239 (Div. 2)
62.
Разбор задач (Яндекс, раунд 2) <b>А. Зеркальные числа.</b><br>
Во-первых, заметим, что если интервал содержит число, состоящее из $a$
цифр, а также число из $b$ цифр (где $a$ > $b$), то нет смысла
рассматривать число из $b$ цифр (так как вес числа $10^k$ больше весов
чисел, меньших $10^k$).<br>
Если же рассмотреть числа с фиксированным числом цифр $(s+1)$, то для
них сумма числа и его отражения — константа. Таким образом, учитывая
что произведение чисел с фиксированной суммой растет при их сближении,
картина у нас следующая: вес числа растет от $10^s$ до $5 \cdot 10^s -
1$, затем он такой же у $5 \cdot 10^s$, затем он убывает и достигает
своего минимального значения в $10^{s+1}-1$.<br>
Это доказательство, решение же такое: максимальный вес достигается либо в
$l$, либо в $r$, либо в числах вида $5 \cdot 10^s$ (можно, например,
проверить все $s$, такие, что $5 \cdot 10^s$ лежит в интервале).<br>
<br><br><b>B. И снова тетрис.</b><br>Легко видеть, что поле можно замостить фигурками всегда, ког...
одной части, то раньше идет тот запрос, у которого правый конец меньше.
Tutorial of Yandex.Algorithm 2011: Round 2
63.
Два варианта написания алгоритма Мо и 3Д Мо Кратко про алгоритм Мо
==================
<spoiler summary="Задача 1">
### Количество различных элементов на отрезке
Дан массив A длины n и q запросов.
Запросы:
- Найти количество различных элементов на отрезке [l; r] массива A.
</spoiler>
<spoiler summary="Задача 2">
### Количество различных элементов на отрезке с изменением
Дан массив A длины n и q запросов.
Необходимо уметь:
- Находить количество различных элементов на отрезке
- Изменять элемент
</spoiler>
Рассмотрим задачу 1. Заметим, что её можно решить с помощью персистентных структур данных. Однако, поставим себе цель решить задачу 2. Да и с персистентностью бывают проблемы.
### Алгоритм 1
Будем решать задачу offline. Отсортируем запросы по <$\frac{l}{k}$, r>, где k — некоторое число. Очевидно, что мы можем легко добавить/удалить одно число (для этого можно поддерживать отдельный массив B, что $B_{i}$ = количеству учтённых вхождений числа i). Разобьем запросы на блоки с одинаковым $\...
\frac{l}{k} \rfloor + 1)$). Пусть текущий запрос (l; r), а максимальная правая
граница — R, блока (изначально R = $k \cdot (\lfloor \frac{l}{k} \rfloor + 1)$). Пусть
текущийзапрос (l; r), а, указатель на последний обработанный запрос. Тогда асимптотика работы алгоритма
— $O(\frac{n}{k
64.
Быстрое умножение по модулю Рассмотрим такую задачу: даны три целых числа $x$, $y$ и $m$, $0 \leqslant x,y < m < 2^{32}$, найти $xy\bmod m$. По-хорошему хотелось бы просто перемножить эти два числа, а потом применить операцию остатка:
~~~~~
uint32_t prod(const uint32_t x, const uint32_t y, const uint32_t m)
{
return x * y % m;
}
~~~~~
Как вы, возможно, догадываетесь, это решение неверное. Всё дело в том, что в такой процедуре возможно переполнение: операция `x * y` выполняется в типе `uint32_t`, и на самом деле промежуточным результатом выполнения этой операции будет не $xy$, а $xy\bmod2^{32}$. Если после этого взять результат по модулю $m$, он может отличаться от правильного:
$$
\left(xy\bmod2^{32}\right)\bmod m\ne xy\bmod m.
$$
Выход прост — перемножать необходимо в большем типе:
~~~~~
uint64_t prod_uint64(const uint64_t x, const uint64_t y, const uint64_t m)
{
return x * y % m;
}
~~~~~
Если так делать, то, поскольку $xy<2^{64}$, это произведение точно не переполнится, и после взятия ре...
Discussion of Fast modular multiplication
65.
Codeforces Round #223 — Разбор ### [problem:381A]
Просто проделаем все операции описанные в условии.
### [problem:381B]
Посчитаем количества каждого числа. Все различные числа, кроме максимального можно использовать не более 2-х раз.
Максимальное же — только 1.
### [problem:380A]
Сгенерируем первые 100000 чисел.
Будем по очереди обратывать запросы, если запрос попадает в точку доабвления 1 числа, то просто выведем его.
Иначе посмотрим, какому элементу будет соотвествовать наш, и просто выведм его из предподсчитаного массива.
### [problem:380B]
Сгенерируем дерево, как описано в условии.
Для каждого запроса на добавление элементов. Просто для уровня будем добавлять отрезок.
На запрос количества элементов будем просто проходить по всем нижним уровням, считая самую левую
и самую правую вершину в поддереве. Далее для каждого уровня будем проходить по отрезкам, которые ему принадлежат
и для каждого проверять — пересекается ли он с тем, что у нас сгенерирован на текущем этапе. Если ...
элементов. Просто для уровня будем добавлять отрезок. На запрос количества
элементов будем просто, запрос попадает в точку доабвления 1 числа, то просто выведем его. Иначе
посмотрим, какому элементу
Tutorial of Codeforces Round 223 (Div. 1)
Tutorial of Codeforces Round 223 (Div. 2)
66.
Центроидная декомпозиция на графе с циклами Мне казалось, что этого нигде нет и я придумал что-то новое, но после того как я предложил задачу на codeforces, один из координаторов сказал, что пару лет назад уже видел задачу, где использовалось что-то похожее. Поэтому задачу отклонили. Так как я не смог придумать более интересную задачу на этот трюк, я просто напишу об этом в блоге.
Задача
------------------
Пусть дана какая-то задача, которую мы умеем решать с помощью центроидной декомпозиции. Например такая. Дано дерево, в каждой вершине записано число a[i]. Поступают 2 типа запросов.
1. Даны $v$, $d$, $c$. Надо перекрасить все вершины на расстоянии не больше $d$ от $v$ в цвет $c$.
2. Дана $v$. Надо узнать цвет вершины $v$.
Теперь эта задача не на дереве, а на связном графе. Но есть одно очень интересное ограничение. m — n + 1 $\le$ 100. То есть в дерево добавили не больше 100 рёбер.
Сначала напомню как решалась задача на дереве. Мы строили дерево центроидов глубины $O(\log n)$, для каждого центроида храни...
. Если запрос первого типа, и мы красим от $v$ на расстояние не более $d$, то
от $C$ надо покрасить на
67.
Разбор задач Codeforces Round #280 (Div. 2) [problem:492A].
По сути нужно выполнить то, что просят в условии. Находим в цикле максимальную высоту $h$, подсчитывая, сколько кубиков должно быть в $i$-м рядку и добавляя эти значения к результату. Выполняем цикл, пока результат не превышает $n$.
Авторское решение: [submission:8924831]
[problem:492B].
Отсортируем фонари в порядке возрастания. Дальше найдем максимально возможное расстояние между двумя соседними фонарями, пусть это будет $maxdist$. Также учтем границы улицы, т.е. найдем расстояния от крайних фонарей к концам улицы $(a[0] - 0)$ и $(l - a[n-1])$. Ответом будет $max(maxdist/2,max(a[0]-0,l-a[n-1]) )$
Асимптотика по времени $O(nlogn)$, учитывая сортировку.
Авторское решение: [submission:8924823]
[problem:492C].
Сортируем пары $(a_i,b_i)$ в порядке возрастания по количеству рефератов $b_i$, после этого проходимся от самого начала отсортированных пар и добавляем жадно по максимуму количество баллов, то есть добавляем значение $min(avg*n-sum,r-a_i)$, по...
Дальше можем отвечать на каждый запрос за $О(1)$, ответом будет $rez[(a_i-1)
mod (x+y)]$.
68.
Чемпионат КРОК 2013 — Раунд 2 — Разбор **[A Div 2](http://codeforces.com/contest/299/problem/A)**
Если $a_j$ делится на $a_i$, то тогда $a_i\le a_j$. Тогда число, на которое будут делиться все остальные числа будет не более чем любое выбранное число. То есть единственный возможный кандидат — это минимум в массиве. Поэтому просто проверим, что все элементы массива делятся на минимальный элемент.
**[B Div 2](http://codeforces.com/contest/299/problem/B)**
Легко видеть, что Ксюша не сможет закончить ее путешествие, если существует последовательность подряд идущих # длиное более чем $k$.
**[C Div 2](http://codeforces.com/contest/299/problem/C) / [A Div 1](http://codeforces.com/contest/293/problem/A)**
Первое наблюдение: мы не будем волноваться о том, как выглядят строки на самом деле, вся информация, которая нам нужна — это количество пар-символов вида: {0, 0}, {0, 1}, {1, 0}, {1, 1}. Посчитаем эти количества и будем следовать следующему жадному алгоритму:
Для первого игрока: будем брать сначала {1, 1},...
- Для каждого элемента (x, y) ответим на запрос $x_bound=L-x$, $y_bound=W-y$
(используем, - Ответ на запрос: идем по подструктурам и суммируем результаты., После этого ответим на запрос $x_bound=L,y_bound=W$ и добавим элемент (0, 0).
Tutorial of Croc Champ 2013 - Round 2
Tutorial of Croc Champ 2013 - Round 2 (Div. 2 Edition)
69.
Codeforces Round #127 — разбор #### Задача A(div 2) --- ЛНПП
Предполагалось, что эту задачу можно решить, не читая её условия, а только глядя на примеры :)
Найдём в заданной строке символ, который идёт в алфавите позже всех, обозначим его через $z$. Если этот символ встречается в строке $p$ раз, то ответ --- это строка $a$, состоящая из символа $z$, повторённого $p$ раз.
Почему это так? Из определения лексикографического сравнения и из того, что символ $z$ --- максимальный в строке, несложно понять, что если какая-то другая подпоследовательность $b$ заданной строки лексикографически больше $a$, то строка $b$ обязана иметь большую длину, чем $a$, и при этом $a$ должна являться префиксом (началом) $b$. Однако строка $b$ должна также быть палиндромом, поэтому последний её символ --- обязательно $z$. В таком случае в строке $b$ должно быть больше вхождений символа $z$, чем в исходной строке $s$, что невозможно, так как $b$ ---
подпоследовательность $s$.
Кроме того, ограничение на длину строки было совсем не...
Tutorial of Codeforces Round 127 (Div. 1)
70.
Разбор задач Educational Codeforces Round 6 ### [problem:620A]
Легко видеть, что ответ в задаче равен $max(|x_1-x_2|, |y_1-y_2|)$.
[С++ solution](http://pastebin.com/hkugLJiu)
Сложность: $O(1)$.
### [problem:620B]
В этой задаче достаточно было пройти по всем числам от $a$ до $b$ и прибавить к ответу количество сегментов, необходимое для отображения очередного числа.
Для подсчёта этой величины нужно пройти по всем десятичным цифрам числа и прибавить к ответу количество сегментов, необходимой для отображения очередной
цифры. Последние величины можно просто посчитать по картинке и вбить в один массив.
[C++ solution](http://pastebin.com/r7EwWskz)
Сложность: $O((b-a)logb)$.
### [problem:620C]
Будем решать задачу жадно. Давайте набирать жемчужинки в самый левый хороший подотрезок по одному, начиная с первой жемчужинки. Как только подотрезок станет
хорошим (то есть встретится повторение) начнём набирать новый хороший подотрезок. Если мы не смогли набрать ни одного хорошего подотрезка, то ответ $-1$.
В про...
Tutorial of Educational Codeforces Round 6
71.
Неофициальный разбор + обсуждение длинного тура Открытой олимпиады 2023 Привет, Codeforces!
Вчера закончился длинный тур Открытой олимпиады этого года, который проходил с 21.11 по 15.01. В нём было много интересных задач, которые мне хотелось бы разобрать и обсудить в этом посте.
Я постараюсь описать свои мысли в ходе решения как можно подробнее, но я не гарантирую, что начинающим спортпрогерам всё будет понятно ;)
Собственно, ниже мои решения + реализации (прощу прощения, если код трудночитаем):
<spoiler summary="А на 100 баллов">
Заметим тот факт, что для любого $1 < i \le n$ будет выполняться $max(p_{0:i}) \ge i$. Назовём _хорошей позицией_ такое $i$, что $max(p_{0:i}) = i$.
Понятно, что если закончить очередной подотрезок не на _хорошей позиции_, то само число $i$ не войдет в этот подотрезок -> оно точно встретится в результирующей перестановке позже $max(p_{0:i})$, противоречие.
То есть, концы отрезков могут совпадать только с _хорошими позициями_ -> перестановку можно разбить на $k$ отрезков с необходимым свойством только тогда, ког...
72.
Разбор Codeforces Round #238 #### [problem:405A]
Заметим, что в конечном расположении все высоты столбиков расположены в неубывающем порядке. Также, количество столбиков каждой высоты остаётся неизменным. Это означает, что ответом является упорядоченная последовательность данных высот столбиков.
Сложность решения: $O(n)$, так как можно упорядочить подсчётом.
#### [problem:405B]
Если самая первая толкнутая доминошка слева была толкнута влево на позиции $l$, все доминошки на префиксе $[1;l]$ падают, иначе пусть $l$ будет 0. Аналогично, если самая последняя толкнутая доминошка была толкнута направо на позиции $r$, все доминошки на суффиксе $[r;n]$ падают, иначе пусть $r$ будет $n+1$. Теперь, на отрезке $(l;r)$ остаются вертикально стоящие доминошки, а также блоки домино, поддерживающиеся одинаковыми силами с обеих сторон.
Когда доминошка на позиции $p$ на отрезке $(l,r)$ остаётся стоять вертикально? В одном случае, её не толкает ни одна другая доминошка. Это можно легко проверить, посмотрев на ближайши...
предка для соответствующей пары вершин в дереве. Так как размер дерева равен
$n$, каждыйзапрос, Теперь, каждый запрос типа 1 и 2 меняет значение ровно одного элемента на
диагонали. Поэтому мы
Tutorial of Codeforces Round 238 (Div. 2)
Tutorial of Codeforces Round 238 (Div. 1)
73.
Разбор Codeforces Round #293 (Div. 2) [517A — Виталий и строки](http://codeforces.com/problemset/problem/517/A)
------------------
Для решения данной задачи можно было, например, найти строку $next$, лексикографически следующую за строкой $s$ и проверить, что строка $next$ лексикографически меньше строки $t$. Если строка $next$ оказалась меньше строки $t$, выведем ее и закончим алгоритм. Если же строка $next$ совпала со строкой $t$, следовало вывести $No~such~string$.
Чтобы найти строку $next$, лексикографически следующую за $s$, нужно сначала найти максимальный суффикс строки $s$, состоящий из букв $'z'$, заменить все буквы $'z'$ в этом суффиксе на буквы $'a'$, а затем букву, стоящую перед этим суффиксом, увеличить на единицу. То есть, если перед суффиксом стояла, например, буква $'d'$, ее следует заменить на букву $'e'$.
Асимптотика решения — $O(|s|)$, где $|s|$ — длина строки $s$.
[517B — Таня и поздравление](http://codeforces.com/problemset/problem/517/B)
------------------
Для решени...
Tutorial of Codeforces Round 293 (Div. 2)
74.
Чемпионат КРОК 2013 — Раунд 1 (Разбор задач) [problem:292A]
Для каждого момента $i$ времени запомним количество сообщений $z[i]$, которое нужно отправить в момент времени $i$. Теперь пройдем по каждому моменту времени от $1$ до $10^6$, поддерживая текущий размер очереди $sz$. На каждой итерации попробуем уменьшить размер очереди на $1$, то есть выполним $sz = max(sz - 1, 0)$, затем прибавим сообщения, которые нужно отправить в эту секунду, то есть выполним $sz = sz + z[i]$. На каждом шаге будем обновлять максимальное значение очереди и текущее время, если $sz > 0$. После выполнения цикла, если в очереди остались неотправленные сообщения, то нужно еще раз обновить ответ.
[problem:292B]
В этой задаче нужно было посчитать степени каждой вершины и найти ответ. Замечу, поскольку $n >= 4$, $m >= 3$ и граф связный, то ответ однозначный.
1) все степени $2$ и у двух вершин степень $1$ — шина.
2) все степени $2$ — кольцо
3) все степени $1$ и у одной степень $ > 2 $ — звезда
4) иначе неизвестно
[pro...
$rdsu[M][N]$. После этого на запрос $[lf ~ ; ~ rg]$ легко ответить за время
$O(N \cdot A^{-1})$, если, запрос копирования $[lf ~ ; ~ rg]$, , тогда покрасим отрезок запроса $[lf ~ ; ~
rg]$ в цвет, равный
75.
Codeforces Round #232 Editorial (restored) ### [Div2-A](http://codeforces.com/contest/397/problem/A)
Заводим массив $used$ на $100$ элементов и заполняем его таким образом: $used[i] = 1$, если хотя бы один из однокашников Алексея претендует на часть $(i, i + 1)$. Далее проходимся циклом от $l_1$ до $r_1 - 1$ и находим количество тех $i$, для которых $used[i] = 0$. Это и будет ответом.
Эту задачу можно решать и за `O(nlogn)`, используя сортировку событий или просто сортировку и линейное решение далее. Такое решение будет находить требуемую величину сразу для всех отрезков.
### [Div2-B](http://codeforces.com/contest/397/problem/B)
Посчитаем, сколько раз по $L$ мы можем взять, не превысив $N$. Это количество равно $K = \frac{N}{L}$.
Тогда, если $R \cdot K \ge N$, будем увеличивать какое-то из $K$ чисел на $1$, в какой-то момент у нас получится в сумме $N$, так в итоге будет больше. Значит ответ — `YES`.
В обратном случае, если мы возьмем не больше $K$ чисел, то их сумма меньше $N$. Если взять больше $K$ чисел, то сумма...
отрезке и запрос в одном элементе. Также в комментариях приведен способ
несколько другой реализации, Сложность ответа на 1 запрос: `O(1)`.
Tutorial of Codeforces Round 232 (Div. 1)
Tutorial of Codeforces Round 232 (Div. 2)
76.
Codeforces Round #448(Div.2) Editorial [problem:895A]
--------------
Заметим, что если один из секторов непрерывен, то все оставшиеся куски также образуют непрерывный сектор. Для каждого непрерывного сектора найдем его угол, то есть сумму углов кусков входящих в него. Если угол одного сектора равен $x$, то разница углов секторов равна $|x - (360 - x)| = |2*x - 360| = 2*|x - 180|$. Переберем сектор, зная его угол $x$ обновим ответ.
Асимптотика $O(n^2)$ или $O(n)$.
[Решение](https://ideone.com/dX19Vz)
[problem:895B]
--------------
Для начала узнаем, как посчитать количество чисел на отрезке делящихся на x. Пусть левая граница отрезка это l, а правая r. Тогда количество чисел делящихся нацело на x и принадлежащих [l, r] равно r/x – (l-1)/x. Отсортируем массив $a$ по возрастанию. Переберем левую границу отрезка, пусть это $a[i]$. Тогда на роль правой границы подходят все числа $a[j]$ такие, что $a[j]/x – (a[i]-1)/x = k$. Значение $(a[i]-1)/x$ мы знаем, а $a[j]/x$ монотонно возрастает при возрастающем $a[j]$. То...
позиции $i$ оно равно $a[i]$. Пусть надо обработать запрос первого типа.
Каждое число из отрезка $[l1, r1
Tutorial of Codeforces Round 448 (Div. 2)
77.
Codeforces Round 931 (Div. 2) Разбор [1934A — Слишком Мин Слишком Макс](https://codeforces.com/contest/1934/problem/A)
<spoiler summary="Решение">
<spoiler summary="Подсказка 1">
Каким был бы ответ, если бы в массиве было только 4 элемента?
</spoiler>
<spoiler summary="Решение">
Предположим, что в массиве только 4 элемента. Назовем их $a \leq b \leq c \leq d$. Тогда ответом был бы максимум среди 3 вариантов, которые приведены ниже:
$$|a-b|+|b-c|+|c-d|+|d-a| = 2*d - 2*a$$
$$|a-b|+|b-d|+|d-c|+|c-a| = 2*d-2*a$$
$$|a-c|+|c-b|+|b-d|+|d-a| = 2*(d+c)-2*(a+b)$$
явно максимумом является $2*(d+c)-2*(a+b)$.
Соответственно, чтобы максимизировать ответ, нам нужно сделать $d$ и $c$ как можно больше и $a$ и $b$ как можно меньше. Мы можем этого добиться выставив $d=a_n$, $c=a_{n-1}$, $b=a_{2}$ и $a=a_{1}$ где $a_i$ обозначает $i$-й элемент в отсортированном массиве.
</spoiler>
</spoiler>
<spoiler summary="Код (C++)">
```
#include <bits/stdc++.h>
using namespace std;
int main()
{...
Что мы знаем о расположении мин, если мы сделаем запрос "? 1 1"?, диагональ, т.е. $n+m-a_2=a_1-2$, мы можем просто сделать запрос к одному из
концов этой диагонали и, Иначе, давайте сделаем запрос "? 1 m". Тогда мы узнаем еще одну диагональ,
которая перпендикулярна, Сначала сделаем запрос "? 1 1". Получим ответ $a_1$, и узнаем, что локацией
одной из мин будет $(x
Tutorial of Codeforces Round 931 (Div. 2)
78.
Разбор задач Educational Codeforces Round 16 ### [problem:710A]
Легко видеть, что в задаче возможно всего три случая. Если король находится углу доски,
то у него $3$ возможных хода. Если он стоит на краю доски, то у него $5$ возможных хода
(если конечно он не в углу). Наконец, если король не стоит на краю доски, то у него
всего $8$ возожных хода.
<spoiler summary="Решение на С++">
~~~~~
char c, d;
bool read() {
return !!(cin >> c >> d);
}
void solve() {
int cnt = 0;
if (c == 'a' || c == 'h') cnt++;
if (d == '1' || d == '8') cnt++;
if (cnt == 0) puts("8");
else if (cnt == 1) puts("5");
else if (cnt == 2) puts("3");
else throw;
}
~~~~~
</spoiler>
Сложность: $O(1)$.
### [problem:710B]
Легко видеть, что ответ всегд находится в одной из заданных точек (функция суммарного рассояния
между парой заданных точек монотонна). Далее можно либо для каждой точки посчитать суммарное расстояние
и выбрать оптимальную точку, либо заметить, что ответом является точка находящяяся посередине в отсортиров...
Легко видеть, что каждая строка перебросится не более $logm$ раз и на каждый
запрос мы умеем
Tutorial of Educational Codeforces Round 16
79.
Разбор задач Codeforces Beta Round #68 <b>A.</b> Нужно было просто сделать то, что написано в условии. Единственный подводный камень в данной задаче - лидер может иметь отрицательное количество очков.<br>[cut]<br><b>B.</b> В данной задаче предполагается придумать оптимальную стратегию "зайцу", а затем просто симулировать игру.<br><br>Выигрышная стратегия для "зайца" - держаться от контролера подальше. А именно - в минуту движения поезда нужно отходить от него, если это возможно. В минуту остановки нужно переходить в вагон, до которого контролер доберется позже всего. Это всегда либо первый либо последний вагон поезда.<br><br>Так же можно было написать простенькое дп или классическую игру.<br><br><b>C.</b> Назовем траекторией линию, которую описывает центр бильярдного шара во время своего движения. В начале своего движения шар выбирает одну из не более чем двух траекторий и движется по ней. Пусть общее количество траекторий равно $k$. Обозначит также максимальное количество попарно не бьющих друг друга шаров (ответ для нашей...
отвечать на запрос суммы на отрезке.
Tutorial of Codeforces Beta Round 68
80.
Разбор задач Codeforces Round #202 ### [problem:349A]
В задаче требовалось выяснить, может ли кассир выдать сдачу всем посетителям кинотеатра, если билет стоит 25 рублей, у посетителей купюры номиналом 25, 50 и 100 и в кассе изначально нет денег.
Рассмотрим 3 различных случая.
- Если у посетителя 25 рублей, то сдачу ему давать не нужно.
- Если у посетителя 50 рублей, то мы должны дать ему 25 рублей сдачи.
- Если у посетителя 100 рублей, то мы должны дать ему 75 рублей сдачи. Это можно сделать двумя способами. 75=25+50 и 75=25+25+25. Заметим, что всегда выгодно попробовать сначала первый способ, а потом второй. Это верно потому, что купюры номиналом 25 рублей могут быть использован как для выдачи сдачи на 50 рублей, так и на 100 рублей, а сами купюры номиналом 50 рублей могут использоваться только для выдачи сдачи на 100 рублей.
Таким образом решение – поддерживать количество купюр номиналом 25 и 50 рублей и при выдаче сдачи на 100 рублей действовать жадно – сначала пробовать выдать 25+50 рублей, а иначе 25+2...
- _Ответ на запрос для легкого множества._ Проходим по всем числам, добавляем
значения к ответу, - _Ответ на запрос для тяжелого множества._ Берем уже посчитанный ответ, затем
проходим по тяжелым, Поскольку дерево отрезков может отвечать на запрос за $O(logN)$ времени, а
задачу LCA можно
Tutorial of Codeforces Round 202 (Div. 1)
Tutorial of Codeforces Round 202 (Div. 2)
81.
Разбор Codeforces Beta Round #75 <p><strong>Задачи A(div2), B(div2)</strong><br></p>В этих задачах требовалось реализовать ровно то, что описано в условии. В задаче <em>B</em> не рекомендовалось использовать BigInteger в Java из за скорости работы с ним.<br><p><strong>Задача C(div2), A(div1)</strong><br></p>В этой задаче буквы из строки $s1$ следовало набирать жадно: брать самую левую букву справа от последней использованной, если требуемой буквы не было справа от последней использованной, то следовало начать поиск с начала строки $s1$ и увеличить ответ на единицу. Однако реализация "в лоб" получала $TL$ и имела асимптотику $O(Ans*|s1|)$. <br><br>Это решение можно оптимизировать, например, следующим образом. Для каждой позиции в $s1$ предпосчитать позиции самых левых символов от текущего для всего алфавита. Это можно было реализовать идя справа налево в строке $s1$ храня позиции последнего вхождения символа каждого вида в строку. Такое решение имеет асимптотику $O(|s1|*K + |s2|)$, где $K$ --- размер алфавита.<br>...
Tutorial of Codeforces Beta Round 75 (Div. 1 Only)
Tutorial of Codeforces Beta Round 75 (Div. 2 Only)
82.
Codeforces Beta Round #99: разбор <h3>[[problem:139A]]</h3>Вычтем из количества страниц книги количество страниц, которые Петя успеет прочесть в понедельник. Если результат неположительный, то в понедельник Петя закончит читать. Иначе перейдем ко вторнику и т.д. по циклу, после воскресенье опять рассматриваем понедельник. Заканчиваем, как только количество страниц должно стать неположительным.<br />Всего нужно пройтись по циклу не более N раз, поскольку на каждой неделе отнимается как минимум одна страница. Сложность - O(n)<br /><br /><h3>[[problem:139B]]</h3><p>Что подразумевалось в условии:</p><p>Каждый рулон можно резать только на полоски, длина которых совпадает с высотой комнаты (потому что нельзя делать горизонтальные стыки, и расположение должно быть строго вертикальным). В каждой комнате можно клеить только один тип обоев (в разных комнатах клеить одинаковые типы можно). Для каждой комнаты надо всего лишь определить оптимальный по цене тип обоев.</p><p>Ясно, что количество рулонов данного типа, нужных для обкле...
умножению и выполнить для каждого отрезка запрос "умножить числа на интервале
массива на x"
Tutorial of Codeforces Beta Round 99 (Div. 1)
Tutorial of Codeforces Beta Round 99 (Div. 2)
83.
Разбор Codeforces Round #330 (Div.1 + Div. 2) [595A — Виталий и ночь](http://codeforces.com/problemset/problem/595/A)
Простая задача на реализацию. Проитерируемся по $i$ от 1 до n, а внутри проитерируемся по $j$ от 1 до $2 \cdot m$,
причем на каждой итерации будем увеличивать $j$ на два. Если на текущей итерации $a[i][j] = '1'$ или
$a[i][j + 1] = '1'$ увеличим ответ на один.
Асимптотика решения — $O(n m)$.
[595B — Паша и телефон](http://codeforces.com/problemset/problem/595/B)
Будем считать ответ для каждого блока отдельно и умножать ответ для предыдущих блоков на ответ
для текущего блока, при этом не забывая брать результат перемножения по модулю.
Для блока длины $k$ ответ считается следующим образом. Пусть для этого блока
число должно делиться на $x$ и не должно начинаться с цифры $y$. Тогда
ответ для этого блока — количество чисел из $k$ цифр, делящихся на $x$,
минус количество чисел, начинающихся с цифры $y$ и состоящих из $k$ цифр,
плюс количество чисел, начинающихся с...
динамический массив), и ответ на запрос будет совершать $O(\log n)$ операций.
Суммарная асимптотика всего, элементы левее. Любой запрос теперь превращается в запрос на префиксе массива.
Тогда, судя по
Tutorial of Codeforces Round 330 (Div. 1)
Tutorial of Codeforces Round 330 (Div. 2)
84.
Codeforces Round #340 (Div. 2) Editorial [problem:617A]
Оптимально делать наибольший возможный шаг каждый раз. Поэтому слоник должен сделать сначала некоторое количество шагов на расстояние 5, а затем один или ноль шагов на меньшее расстояние. Следовательно, ответ равен $\lceil\frac{x}{5}\rceil$.
Решение [submission:15550796]
[problem:617B]
Нам дан массив, состоящий только из нулей и единиц. Мы должны разделить его на части, в каждой из которых ровно одна единица.
Особый случай: когда массив состоит только из нулей ответ равен нулю.
Рассмотрим общий случай. Во-первых нули на префиксе относятся к первому куску, нули на суффиксе относятся ко второму куску. Во-вторых, между каждой парой соседних единиц должно быть одно и только одно разделение частей. Между соседними единицами с индексами $a < b$ всего $b - a$ вариантов разделения. Поэтому мы должны перемножить эти значения для всех пар соседних единиц.
Бонус: каким является максимальный ответ при $n \leq 100$?
Решение [submission:15550806]
[problem:61...
Пусть мы знаем ответ на запрос (l, r) и знаем для всех $v$ $cnt[v]$ —
количество вхождений $v, Теперь запрос (l, r) заключается в подсчете количества пар $i$, $j$ ($l - 1
\leq i < j \leq r
Tutorial of Codeforces Round 340 (Div. 2)
85.
Хешируемое множество со сравнением за O(1) Итак, многие из Вас знают, что можно легко и просто хешировать множества. Например, множество $s = \{ s_1, s_2, ..., s_n \}$ можно захешировать числом $x(s_1) + x(s_2) + ... + x(s_n)$ или даже $x(s_1) \oplus ... \oplus x(s_n)$ (где $x$ — какая-то случайная функция). С такими хешом можно поддерживать операции добавления и удаления элемента, слияния множеств, нахождения симметричной разности множеств и так далее. Но у такого подхода есть и достаточно серьезный минус, например, имея на руках только хеш мы не можем понять, какие элементы содержит это множество.
Сегодня я хочу поведать о не очень сложной структуре данных, основанной на дереве отрезков, которая позволяет совершать различные операции с множествами, в частности, сравнивать эти множества за время O(1), надеюсь, после прочтения вы поделитесь своими идеями, как ее можно улучшить и какие еще операции с ней можно делать. :D
Итак, для начала рассмотрим следующую задачу. В первой строке даны числа $N,Q \leq 10^5$, отвеча...
86.
Запросы на деревьях вне путей Пусть нам очень хочется решить следующую задачку:
Дано дерево и поступают два вида запросов — добавить X на пути, посчитать минимум вне пути. И требуется отвечать на каждый запрос за $O(n \cdot log^2n)$
Решение курильщика: Давайте сделаем HLD декомпозицию, и для каждого пути будет также хранить его id и минимум в нем. И будем хранить эти величины в множестве. Тогда запрос на добавление на пути — просто делаем стандартное обновление на пути в HLD, изменяя значения в множестве. Запрос минимума уже более интеллектуальный, посмотрим, на какие пути он разбивается, и выкинем их из множества (если путь входит частично, то мы только конец пути будем учитывать в ответе, и также будем выкидывать путь из множества). А ответ — минимум из этой величины и минимума в множестве. Так как все пути в множестве нам подходят. А ничего лишнего мы также не учли. Затем все откатываем и радуемся жизни.
Нормальное решение: Давайте просто сделаем HLD Вадомара (то бишь HLD, у которого ...
и минимум в нем. И будем хранить эти величины в множестве. Тогда запрос на
добавление на пути, про поддеревья). И запрос изменения — обычный update в HLD, а чтобы получить
ответ просто, требуется отвечать на каждый запрос за $O(n \cdot log^2n)$, — добавить X на пути, посчитать минимум вне пути. И требуется отвечать на
каждыйзапрос за $O(n
87.
Разбор задач Codeforces Round #430 (Div. 2) [problem:842A])
Пусть $exp$ – количество опыта в зелье, а $cost$ — его стоимость. Мы хотим узнать есть ли такие $exp$ и $cost$ чтобы выполнялось условие $\frac{exp}{cost} = k$. Решение этой задачи: перебрать $cost$ с $x$ по $y$ и проверить, что $exp = k \cdot cost$ находится в отрезке с $l$ по $r$.
https://ideone.com/a8syda
[problem:842B])
Чтобы понять, лежит ли кусочек колбасы внутри пиццы, мы можем рассмотреть взаимное расположение окружностей (всей пиццы, пиццы без корки и куска колбасы).
Рассматривать взаимное расположение окружностей удобно, опираясь на их радиусы и расстояние между их центрами.
Чтобы кусочек колбасы находился внутри корки, он должен, во-первых, находиться в пицце $(\sqrt{x^2 + y^2} ) + cr \le r$) и, во-вторых, не должен включать в себя кусок пиццы без корки $(\sqrt{x^2 + y^2} \ge r - d + cr$).
Пройдёмся по массиву и для каждого кусочка узнаем, лежит ли он в корке.
https://ideone.com/Jd66XL
[problem:842C])
Заметим, что если зна...
Если у нас был запрос $x_i$, а дальше $x_{i + 1}$, то в качестве второго
запроса можно
Tutorial of Codeforces Round 430 (Div. 2)
88.
Прощай, codeforces.ru Нет ничего лучше, чем провести праздник с пользой. И в эти праздничные дни я успел не только сходить в Парк Победы с семьей, поздравить близких мне людей и посмотреть салют, но и начать избавление от codeforces.ru.
Да, это не ошибка. В самом деле домен codeforces.ru теперь практически не будет использоваться. Вместо пары доменов codeforces.ru/codeforces.com будет использоваться один: codeforces.com
Этот шаг упростит некоторые аспекты навигации, упростит учет статистики, улучшит pagerank и другие метрики домена.
Конечно, все ссылки на codeforces.ru теперь редиректятся на соответствующие на codeforces.com. Кроме того, пока это касается только GET-запросов, чтобы поменьше разламывать какие-нибудь автоматизации.
Внимательные пользователи заметили, что недавно изменилась и работа с картинками. Теперь, если вы вставляете картинку в текст поста/комментария, то при сохранении она выкачивается и сохраняется на Codeforces, а ссылка подменяется на использующую наш домен. Это решает ср...
89.
Heavy-light decompositon — это может быть просто! _Доброго времени суток всем._
Сегодня я хочу рассказать немного о написании элегантной структуру данных — Heavy-light decomposition (далее просто $HLD$).
Многие из вас, наверное, сталкивались с задачами вида "дано взвешенное дерево, запросы модификации ребер и запросы нахождения минимума на ребрах между двумя вершинами". HLD умеет довольно просто решать эту и многие другие задачи.
#### _Для начала краткое описание структуры._
_// Более полное описание есть на [e-maxx](http://e-maxx.ru/algo/heavy_light)._
Heavy-light decomposition — это такая разбивка графа на непересекающиеся по вершинам или ребрам пути, что на пути от любой вершины до корня этого дерева мы сменим не более $log(N)$ путей. Если мы научимся строить такие пути, то с помощью дополнительных структур (дерево отрезков (или просто ДО), например) сможем быстро отвечать на запросы.
Назовем ребро тяжелым, если поддерево сына, в которого ведет это ребро, будет по размеру не менее половины поддерева о...
: рассмотрим два пути, на которых сейчас наши вершины. Если они на одном пути,
то это простозапрос на ДО, Имеем, что ответ на запрос и нахождение $lca$ можно делать одновременно.
90.
Sqrt Beats, Treap Beats? Вступление
----------
Пожалуй, большинство из вас встречалось с такой структурой данных (точее, расширением обычного _Дерева Отрезков_), как _Segment Tree Beats_. Как известно, эта структура помогает в решении множества задач (подробнее про это здесь: https://codeforces.com/blog/entry/57319). Но, тем не менее, этот набор идей ограничивается не только лишь Деревом Отрезков. Его также можно успешно использовать и с другими структурами, которые позволяют выполнять запросы на отрезках. Например, STB можно совместить с _корневой декомпозицией_ или _Декартовым Деревом_.
### ...А главное, зачем?
На самом деле, это несёт больше теоретическое значение, чем практическое. Тем не менее:
1) Существуют запросы на отрезках, которые не решаются с помощью ДО. Использовать STB в таких случаях не представляется возможным, однако применить корневую декомпозицию или Декартово дерево можно.
2) Есть задачи, решение которых гораздо упрощается, если применять _"Sqrt Beats"_. Иногда такой способ дости...
-во вхождений}. А запрос циклического сдвига, соответственно, обрабатывается за
$O(\frac{n}{k} + k, 1) Операция реверса отрезка, $\%=$ на отрезке, $=$ на отрезке + запрос суммы на
отрезке. (Также, 2) Вставить элемент на позию $x$ в массив, min= на отрезке + запрос суммы и
максимума на отрезке, 2) Запрос циклического сдвига влево на 1 на отрезке., 3) Есть запрос "посчитать количество чисел равных $k$ на отрезке ($k$ могут
быть различные для, 3) Циклический сдвиг отрезка на $k$, деление нацело на отрезке, прибавление на
отрезке +запрос, 4) Запрос поменять местами четные и нечетные элементы отрезка местами, min= на
отрезке, прибавление
91.
Разбор задач Coder-Strike 2014 Раунд 2 ###[problem:413A]
Посчитаем минимум и максимум в заданном массиве размера $m$. Если минимум уже меньше заданного $min$, либо если уже максимум больше заданного $max$, то ответ Incorrect.
Посчитаем минимальное значение $0 \le need \le 2 $, которое будет равняться числу элементов, которые надо добавить в исходный массив, чтобы его минимум стал равен $min$, а максимум стал равен $max$. Для этого нужно попарно сравнить минимум заданном массиве со значением $min$ и максимум в заданном массиве со значением $max$. Тогда ответ Correct, если $n-m \ge need$. Иначе ответ Incorrect.
###[problem:413B]
Обработаем все запросы и будем поддерживать следующие величины: для каждого сотрудника будем поддерживать число сообщений, которые он отправил в какой-нибудь чат и для каждого чата количество сообщений, которые были отправлены в этот чат. Тогда ответ для каждого сотрудника — это сумма числа сообщений, отправленных во все чаты, участником которых является данный сотрудник, минус чис...
Tutorial of Coder-Strike 2014 - Round 2
92.
Обсуждение регионального этапа ВСОШ по информатике 2022-2023 Я немного удивлён, но ещё никто не сделал такого поста.
Хочу предложить вам обсуждать этот РЭ в данном посте:)
Кратко: [user:imachug,2023-01-21] уже третий год делает неофициальную склеенную сводную табличку (но теперь на новом домене): [reg.algocode.ru](https://reg.algocode.ru)
Там можно оставить свой результат, туда добавляются результаты доступных на текущий момент табличек.
Пожалуйста, если у вас есть неприватные таблички регионов, оставьте на них ссылку в комметариях:) Думаю, все будут очень благодарны.
Также, если правилами уже разрешено (все написали), то здесь можно обсудить задачи с туров)
Удачи всем на втором дне 🍀
UPD: краткий разбор задач первого дня от меня.
<spoiler summary="Задача A:">
Там получается уравнение
(x + 1) * (y + 1) = m.
x + y = k.
Поэтому получаем
(x + 1) * (k — x + 1) = m
Это квадратное уравнение.
Раскроем скобочки и решим.
Получим 2 пары корней. Проверим, подходят ли.
</spoiler>
<spoiler summary="Зад...
93.
Дерево палиндромов: немного закулисья Всем привет!
Как некоторые уже знают, на этих летних сборах в Петрозаводске [user:MikhailRubinchik,2014-09-25] презентовал новую структуру данных, а именно дерево палиндромов. Я имел честь поучаствовать в изучении структуры за полгода до этого, о чём и хочу теперь рассказать :)
[cut]<br>
Но для начала краткий экскурс. Если вы уже знаете базовые идеи реализации, можете смело <a href="#inter">переходить</a> к интересной части. Давайте каждому палиндрому поставим в однозначное соответствие строку, равную его правой половине, то есть, радиус и булеву переменную, обозначающую его чётность. Теперь объединим все радиусы подпалиндромов строки $S$ в два бора — для чётных и нечётных длин раздельно. Утверждение: такой бор будет занимать $\mathit O(n)$ памяти. Ну действительно, в строке может быть не больше $n$<sup><a name = "ref10" href="#ref11">[1]</a></sup> различных палиндромов, а каждая вершина в дереве соответствует одному уникальному подпалиндромы. Следовательно, у нас не бол...
94.
Вытаскиваем дерамиду по неявному ключу из недр С++. Всем привет! Не буду долгих предисловий тут писать, поэтому сразу к делу. Читая книгу Мейерса "Эффективное использование STL", я вдруг наткнулся на упоминание о наличии в некоторых версиях STL структуры данных [rope](http://goo.gl/yZYcFw). Если кратко, то эта структура данных позволяет быстро вырезать/вставлять куски массива в произвольные позиции, аналогично декартовому дереву по неявному ключу (с аналогичной сложностью — подробности смотрите в статье на вики). Она иногда используется для обработки сверхдлинных строк.
Как выяснилось, rope действительно реализована в некоторых версиях STL, например в [SGI STL](http://www.sgi.com/tech/stl/Rope.html). Сразу замечу, что это наиболее полная документация по классу rope, которую мне удалось найти в сети. А теперь давайте разыщем rope в GNU C++. Поскольку кто-то ранее находил расширенную версию красно-черных деревьев в GNU, я подумал, почему бы и rope где-нибудь не заваляться. Для тестинга я взял вот [эту](http://informatics.mccme.ru...
95.
Количество различных элементов на отрезке + изменение элемента OFFLINE <spoiler summary="Предыстория">
На днях решал задачу, которую свел к описанной ниже. В интернете(по крайней мере на русском языке) описаны менее эффективные решения, в отличие от описанного ниже.
</spoiler>
Формальная постановка: дан массив $a$ из $n$ натуральных чисел. Также даны $q$ запросов двух типов:
1. посчитать количество различных чисел на отрезке $[l, r]$;
2. выполнить присвоение $a_p := x$.
Запросы даны offline (т.е. все сразу).
У этой задачи существует менее оптимальное решение с помощью алгоритма 3Д Мо, например, описанное [тут](https://codeforces.com/blog/entry/83630?locale=ru). Опишем решение, работающее за $(n+q)*\sqrt{n+q}$.
Т.к. запросы даны заранее, то мы сможем сжать числа и считать, что в любой момент времени $a_i \le n+q$.
Разобьем $q$ запросов на $b$ блоков по $m$ запросов $(m*b=q)$.
Будем обрабатывать запросы блоками. После завершения обработки всех запросов очередного блока выполним все операции присвоения и "забудем" про них.
Предполо...
Для ответа на запрос первого типа(посчитать количество различных чисел на
отрезке) $j, l, r$ ($j, Для ответа на очередной запрос будет необходимо учесть изменения массива,
которые произошли до
96.
Сравнение производительности разных реализаций дерева отрезков Иногда я задумываюсь, какую реализацию дерева отрезков написать в задаче. Обычно я при помощи метода "пальцем в небо" выбираю какую-то и в большинстве случаев она проходит ограничения.
Я решил подвести основу, так сказать базу, под этот выбор и протестировал на производительность 4 разные реализации:
<ul>
<li>
Простой рекурсивный "Разделяй и властвуй"
<spoiler summary="Код">
~~~
struct SimpleRecursiveSegmentTree {
unsigned size;
private:
std::vector<long long> t;
void _build(const std::vector<int> &v, unsigned p, unsigned l, unsigned r) {
if (r == l + 1) {
t[p] = v[l];
return;
}
unsigned m = (l + r) / 2;
_build(v, 2 * p + 1, l, m);
_build(v, 2 * p + 2, m, r);
t[p] = t[2 * p + 1] + t[2 * p + 2];
}
long long _get(unsigned p, unsigned l, unsigned r, unsigned a,
unsigned b) const {
if (b <= l || r <= a) {
return 0LL;
...
97.
Разбор задач Codeforces Round #140 ### [A div2. Куда свернуть?](http://codeforces.com/contest/227/problem/A)
Посмотрим на векторное произведение $\overrightarrow{AB}$ на $\overrightarrow{BC}$, численно равное $\overrightarrow{AB_x} \cdot \overrightarrow{BC_y} - \overrightarrow{AB_y} \cdot \overrightarrow{BC_x}$.
Знак векторного произведения определяется знаком синуса ориентированного угла между векторами (т.к. векторное произведение также равно $|\overrightarrow{AB}| \cdot |\overrightarrow{BC}| \cdot sin(\overrightarrow{AB}, \overrightarrow{BC})$), а именно этот-то знак нам и нужно узнать.
Если произведение равно нулю, то это в данной задаче означает, что $A, B$ и $C$ лежат на одной прямой, а значит ответ — <<TOWARDS>>.
Если произведение больше нуля, то ответ — <<LEFT>>.
И, наконец, если оно меньше нуля, то ответ — <<RIGHT>>.
Также стоит обратить внимание, что вычисление векторного произведения требуется производить в 64-битном типе, чтобы избежать переполнения.
[Решение](http://past...
(log$ $n)$ (вначале бинпоиск по версиям, затем запрос к дереву/спуск по дереву)., Теперь, когда нам будет поступать запрос первого типа, будем сопоставлять
позиции первого вхождения
Tutorial of Codeforces Round 140 (Div. 1)
98.
Видео про Disjoint Sparse Table или как отвечать на все запросы за O(1) Привет!
Я сделал видео про disjoint sparse table. Это некоторое обобщение обычного sparse table'а, который расширяет возможности его применения.
[Ссылка на видео](https://youtu.be/NbAtm1j5gVA)
Буду рад, если вы посмотрите этот ролик и оставите комментарий со своими впечатлениями, замечаниями, мыслями или идеями насчет новых видео. Также можете написать мне в [телеграм](https://t.me/peltorator), если вы чего-то не поняли в видео или у вас возникли любые вопросы. Буду рад ответить!
Я собираюсь регулярно выпускать видео по алгоритмам в будущем. Как по основам (префиксные суммы, бинарный поиск, сортировки и тд), так и по провинутым темам (heavy-light декомпозиция, link-cut tree, лямбда-оптимизация, FFT и другие). Так что если вам это интересно, подписывайтесь на канал, чтобы их не пропустить!
Реализации можете посмотреть по ссылкам:
[Самая простая](https://pastebin.com/wc1FsZri)
[Удобная версия ...
99.
Codeforces Round #199 (Div. 2) Разбор Задач [problem:342A]
В этой задаче нужно было догадаться, что существует только 3 корректные тройки:
1) 1, 2, 4
2) 1, 2, 6
3) 1, 3, 6
Будем жадно набирать их пока получается. Если остались какие то неиспользованные числа (в том числе 5 и 7, которые очевидно сразу являются плохими), то выведем -1. Иначе выведем найденный ответ.
[problem:342B]
Эта задача решается жадно. Будем всегда двигаться только по направлению от $s$ до $f$. Причем, если в данный момент можно совершить действие, обязательно будем его совершать. Иначе не будем передавать записку соседу и оставим ее у себя (такой ход можно делать в любой ситуации). Очевидно, что такой подход приводит к правильному решению, остается его аккуратно реализовать.
[problem:342C]
В задаче нужно было аккуратно выписать формулу. Оптимальное решение укладывает шарики по два в ряд, пока это возможно.
А потом сверху кладет еще один шарик, если это возможно. Основная хитрость и сложность была именно в последнем шаге.
В ком...
. Далее, чтобы выполнить запрос на вывод ответа из текущего блока нужно взять
значение полученное, . После этого, чтобы ответить на запрос типа 2, нужно взять $min(d[v], dist(v,
u))$, где $u$ &mdash
Tutorial of Codeforces Round 199 (Div. 2)
100.
Про эйлеров обход **TL;DR**: можно ли одновременно поддерживать эйлеровым обходом LCA, сумму в поддереве и переподвешивание?
Дерево эйлерова обхода -- это способ представлять подвешенное неориентированное дерево массивом чисел. Построить это представление можно несколькими способами. У каждого есть свои плюсы и минусы. Здесь я хочу обсудить, можно ли придумать алгоритм, объединяющий плюсы всех описанных. Может быть, новичкам пост будет полезен как туториал.
[cut]
Первый способ -- выписать все рёбра дерева (ориентированные) в порядке обхода DFS'а. Так эйлеров обход определяется в [Википедии](http://en.wikipedia.org/wiki/Euler_tour_technique).
~~~~
1
/ \
2 5
/ \
3 4
[1-2] [2-3] [3-2] [2-4] [4-2] [2-1] [1-5] [5-1]
~~~~
Второй способ -- хранить вершины. Каждая вершина добавляется в массив дважды: когда мы в неё спускаемся и когда выходим. Каждому листу (кроме, возможно, корня) соответствует два последовательных вхождения.
~~~~
1
/ \
2 5
/ \
...
101.
Codeforces Round #109: разбор Формулы генерируются со скрипом, надо обновлять страницу, чтобы они появлялись.
[problem:155A]
Надо сделать, что написано: считать массив и посчитать количество элементов, больших или меньших всех предыдущих. Массив для этого можно даже не хранить, а поддерживать текущий минимум и максимум. Сложность --- O(N), хотя проходил и квадрат.
[problem:155B]
Заметим, что мы всегда можем сперва сыграть все карты с $b_i > 0$, т.к. каждая из них дает хотя бы один дополнительный ход. Количество оставшихся дополнительных ходов после этого не зависит от порядка их отыгрыша. После этого у всех оставшихся карт $b_i = 0$, и из них надо играть те, у которых максимально $a_i$. Простой вариант того же решения: отсортировать все карты по убыванию $b_i$, а при равенстве --- по убыванию $a_i$, а затем идти от начала к концу, моделировать счетчик оставшихся ходов и суммировать очки. При этом надо не вылететь за границу массива, если дополнительных ходов больше, чем карт. Сложность --- $O(n \log{n...
Tutorial of Codeforces Round 109 (Div. 1)
Tutorial of Codeforces Round 109 (Div. 2)
102.
Codeforces #308 (Div. 2) Editorial [problem:552A]
В этой задаче проходило множество решений:
1) С каждым новым прямоугольником добавляется его площадь к результату, так что будем считать площадь каждого прямоугольника и прибавлять к ответу, т.е. для каждой строки $x_1,y_1,x_2,y_2$ прибавляем к ответу $(x_2-x_1+1)*(y_2-y_1+1)$
Асимптотика данного решения по времени $O(n)$.
2) Просто сделаем все, что описано в условии, создадим массив и с каждым запросом будем прибавлять прямоугольник к массиву, после чего просто сложим все элементы массива.
Асимптотика по времени $O(n*x*y)$
[C++ code](http://ideone.com/uFAzzC) [user:Wild_Hamster,2015-06-19]
[Java code](http://ideone.com/9FPeh9) [user:Wild_Hamster,2015-06-19]
[Python code](http://ideone.com/kIXn7c) [user:Zlobober,2015-06-19]
[problem:552B]
Можно вывести формулу результата:
для $n < 10$ ответом будет $n = n - 1 + 1 = 1*(n+1)-1$;
для $n < 100$ ответом будет $2*(n-9) + 9 = 2*n - 9 = 2*n - 10 - 1 + 2 = 2*(n+1)-11$;
для $n < 1000$ отве...
Tutorial of Codeforces Round 308 (Div. 2)
103.
Разбор задач финального раунда Яндекс.Алгоритма 2018 Интеллектуальный вендинг
------------------
Автор идеи и разработчик: [user:glebshp,2018-05-29].
Заметим, что в любом случае Аркадий не может потратить больше денег, чем у него есть, поэтому количество купленных бутылок не превзойдёт $z = \lfloor \frac{b \cdot 10^{6} + c}{r} \rfloor$. Однако, может так получится, что Аркадию придётся купить меньше бутылок, если в какой-то момент у Аркадия не будет хватать мелочи на покупку без сдачи, а нужно количество сдачи в автомате не будет.
Заметим, что суммарное количество мелочи в обороте не меняется и составляет $c + d$. При этом, если $c + d \geq 999\,999$, то либо у Аркадия всегда найдётся мелочь, чтобы купить очередную бутылку, либо автомат сможет дать сдачу, если платить только с помощью банкнот. В этом случае ответ равен $z$.
Если же $c + d < 999\,999$, то может быть, что у Аркадия хватает мелочи для совершения покупки без сдачи, может быть, что в автомате достаточно сдачи для покупки банкнотами, но не может быть одновременно вы...
Tutorial of Yandex.Algorithm 2018, final round
104.
Codeforces Round #136 — Разбор ###[problem:221A]
В этой задаче все что нужно заметить это то, что ответ всегда имеет следующею форму: $n$, 1, 2, 3, ..., $n$-1. При такой перестановке не трудно заметить, что после полого выполнения алгоритма перестановка будет отсортирована.
###[problem:221B]
Нужно найти все делители числа $n$. Это можно сделать простым перебором от 1 до $sqrt(n)$. После этого нужно написать функцию, которая умеет определять, существуют ли две одинаковые цифры в паре чисел. Это тоже можно сделать простым перебором по цифрам.
###[problem:220A]
Существует несколько решений этой задачи. Например, можно найти максимальное $x$ такое, что существует $y$ (минимальное возможное) такое, что $(y < x)$ и $A_x < A_y$. После этого остается проверить ровно два варианты --- либо менять местами $x$-е и $y$-е числа, либо не делать ничего.
###[problem:220B]
Задачу можно решить за $O(NsqrtN)$, но я опишу решение за $O(NlogN)$.
Будем решать задачу в оффлайне, тоесть сначала считаем все запросы, а...
$ ответом на запрос $[l; x]$ будет число $D_l + D_{l+1} + ... + D_r$. Для
правильной поддержки массива
Tutorial of Codeforces Round 136 (Div. 1)
Tutorial of Codeforces Round 136 (Div. 2)
105.
X (XXI) открытый командный студенческий чемпионат Поволжья по спортивному программированию **В связи с неблагоприятной эпидемической ситуацией чемпионат Поволжья не может быть проведён в запланированные сроки.**
**Решение о новом сроке проведения чемпионата будет принято в середине апреля. Если всё будет складываться благополучно — то наиболее вероятны даты в период с 4 по 8 мая. В противном случае будут рассматриваться различные варианты.**
**9 — 12 апреля 2020 года** Самарский университет при поддержке Министерства образования Самарской области, компаний Mercury Development, Maxifier, Magenta Technology, CQG проводит **X (XXI) открытый командный студенческий чемпионат Поволжья по спортивному программированию**.
Подробная и регулярно обновляемая информация содержится на [странице чемпионата](http://contest.uni-smr.ac.ru/ru/championship2020/).
[cut]
<BR/>
**Чемпионат проводится в один тур в формате ACM ICPC.**
Ориентировочное количество участников — до 75 команд.
_Оргвзнос за участие в чемпионате не предусмотрен._
Первый этап реги...
106.
Вторая номинация Всесибирской 2020 / Гран-при Сибири: разбор 9. Решающий удар
----------------
<pre>
Для определения вероятности посчитаем динамику
v[n][d] — количество исходов при бросании n игральных костей,
при которых сумма результатов равна d.
База динамики
Для первой кости и каждого из исходов 1 <= d_roll <= f
v[1][d_roll] = 1.
Переход динамики
Уже бросили (n - 1) кость и сумма результатов равна d,
бросаем ещё одну кость и выбрасываем на ней d_roll, тогда
v[n][d + d_roll] увеличивается на v[n - 1][d].
При добавлении очередной кости суммируем по всем d и d_roll.
Количество нужных нам исходов получаем суммой
S = sum v[n][d], max(1, D - m) <= d <= n * f.
Итоговая вероятность равна
S / f^n.
</pre>
7. Планировщик
--------------
<pre>
Пусть X[i] = P[i] + T[i].
В задаче нужно выбирать среди N значений X[i] минимальное — для этого отлично подойдёт бинарная куча.
Кроме того, нужно на каждой итерации прибавлять единичку ко всем X[i] (кроме одного).
Чтобы этого не делать...
; это и будет положение цели. Хватает 5 запросов, считая последний запрос на
попадание в цель
107.
Разбор задач Codeforces Round #150 **Adiv2.** Рассмотрим массив $A$ целых чисел от 1 до $nk$. Удалим из него все числа $a_i$, а все, что осталось, запишем в массив $B$. Массив $B$ будет состоять из $(n-1)k$ элементов. Теперь для $i$-го ребенка следует вывести числа $a_i$, $B[(n-1)*(i-1) + 1]$, $B[(n-1)*(i-1) + 2]$, ... $B[(n-1)*(i-1) + n - 1]$ (индексация $B$ начинается с 1).
Автор --- [user:Gerald]
[cut]
.
**Bvid2.** Решение 1. Напишем перебор по всем числам, состоящим из не более чем 9 цифр (число $10^9$ преверим отдельно). Схематично это будет выглядеть так:
~~~~~
dfs( int num ) // запускать как dfs(0)
if (num > 0 && num <= n) ans++
if (num >= 10^8) return
for a = 0..9 do
if num*10+a>0 then
if число num*10+a содержит не более 3х цифр then
dfs( num*10+a )
~~~~~
В ans теперь будет находиться ответ. Напишем, запустим — увидим, что работает быстро (это решение выполняется одинаковое время на всех тестах). Отошлем.
Решение 2. Будем строить все безусловно счастл...
Tutorial of Codeforces Round 150 (Div. 1)
Tutorial of Codeforces Round 150 (Div. 2)
108.
10 причин использовать Polygon для подготовки задач <img src="http://assets.codeforces.com/images/poly21.jpg" style="float:right;margin:0 0.5em 1em 1em;"/>
Привет, Codeforces.
Уверен, многие в курсе — просто напомню. Polygon — это сервис для подготовки задач по
программированию. Обычно используется в подготовке к олимпиадам, но часто и для учебных задач
по информатике. Расположен он по адресу https://polygon.codeforces.com/ и открыт для всех желающих.
Я недавно обнаружил, что вот уже прошло более 5-ти лет как была создана система разработки задач Polygon.
Самое время обобщить накопленный опыт использования.
Впервые о Polygon я публично рассказал в узком коллективе тренеров российских сборных на
финале ACM-ICPC в 2009-м году. Я не скажу, что все восприняли разработку с энтузиазмом, были
и те, кто высказал откровенный скепсис жизнеспособности и востребованности такой системы.
Прошло 5 лет и на финале ACM-ICPC в Екатеринбурге Олег Христенко (человек-Снарк) сказал, что считает создание Polygon
моей большей зас...
109.
Codeforces Round #357 (Div. 2) Editorial [problem:681A]
Если хотя бы для одного участника $before_i \ge 2400$ и $after_i > before_i$, то ответ "YES", иначе "NO"
[Код](https://ideone.com/kzMYfl)
[problem:681B]
Ограничения в этой задаче таковы, что можно перебрать $a$ от $0$ до $n / 1234567$ и $b$ от $0$ до $n / 123456$, и проверить, что $n - a * 1234567 - b * 123456$ не отрицательно и делится на c.
Если хотя бы одна такая пара чисел $a$ и $b$ нашлась, то ответ "YES", иначе "NO"
[Код](https://ideone.com/zbPSkF)
[problem:681C]
Будем решать эту задачу жадно.
Выполняем оставшиеся запросы в порядке, в котором они нам даны.
Если текущий запрос – $insert$ $x$, то добавим элемент $x$ в кучу.
Если текущий запрос – $removeMin$, то если куча не пуста, то просто удалим минимум, а если куча пуста, то вставим запрос $insert$ $x$, где $x$ – любое число, и затем выполним $removeMin$
Если текущий запрос – $getMin$ $x$ то выполним следущее:
1. Пока куча не пуста и минимальный элемент в ней меньше $x$, выполн...
1. Пока куча не пуста и минимальный элемент в ней меньше $x$, выполним запрос
удаления минимума из, Если текущий запрос – $getMin$ $x$ то выполним следущее:, Если текущий запрос – $insert$ $x$, то добавим элемент $x$ в кучу., Если текущий запрос – $removeMin$, то если куча не пуста, то просто удалим
минимум, а если куча
Tutorial of Codeforces Round 357 (Div. 2)
110.
IOI 2013, 1 тур Первый тур никак не может начаться :(
Сейчас уже доступна [видео-трансляция](http://new.livestream.com/accounts/4506465/ioi2013) (говорят зацикленная)
Мы надеемся, что с началом контеста появятся результаты.
Через некоторое время после начала контеста, мы выложим условия и будем рады их обсудить.
**UPD** [Scoreboard](http://live.ioi2013.org/Ranking.html)
За происходящим будем следить мы с [user:powerful.aloe,2013-07-08].
8.53 Контест должен был начаться в 8:00, но из-за технических проблем участников только запустили.
Обещают начать в 9:00 по местному.
9.01 Участников куда массово повели. Что там вообще происходит?
9.02 Вроде все вернулись. У одного из участников мы заметили 4 минуты да начала контеста на мониторе.
9.11 Видимо отложили еще. Или не отложили. Никто ничего не говорит.
9.25 На трансляции наконец-то показали участников. Контест уже идет. Интересно, когда он начался?
9.31 Вроде обещают сделать табличку в ближайшее время. Тем временем ~KOTEHO...
111.
Codeforces Round #218 (Div. 2): разбор задач Разбор задач подготовили: [user:Fefer_Ivan,2013-12-08], [user:NALP,2013-12-08].
### [problem:371A]
Для того, чтобы массив был периодическим, элементы $1, 1 + k, 1 + 2*k, \dots$ должны быть равны. Также, элементы $2, 2 + k, 2 + 2*k, \dots$ должны быть равны. И так далее до $k$.
То есть существует $k$ групп элементов, таких что каждый элемент принадлежит ровно одной группе. Каждая группа может рассматриваться независимо.
Рассмотрим группу в которой $a$ единичек и $b$ двоек. Все элементы в одной группе должны быть равны. Для того, чтобы этого достичь необходимо либо все единички сделать двойками (что потребует $a$ операций изменения), либо все двойки сделать единичками (что потребует $b$ операций изменения). Для того, чтобы решение было оптимальным, необходимо выбрать способ, который требует наименьшее количество операций изменения.
### [problem:371B]
Из условия понятно, что лисица может производить над числами лишь три операции: поделить какое-то из них на $2$, поделить на ...
каждом сосуде в массиве $v$. Тогда для ответа на запрос второго типа надо
просто взять значение из этого, , если у нас есть $n$ сосудов вместимости $1$, то запрос вида $1 1 n$ потребует
$O(n)$ времени на
Tutorial of Codeforces Round 218 (Div. 2)
112.
Двумерное дерево отрезков с прибавлением и суммой на прямоугольнике Для понимания этой статьи необходимо знать базовое ДО и желательно понимать, как работает обычное 2D ДО.
Решим следующую задачу:
Дана таблица $n \cdot m$, поступают 2 вида запросов:
1) Прибавить $x$ на прямоугольнике $[l1, r1], [l2, r2]$.
2) Посчитать сумму на прямоугольнике $[l1, r1], [l2, r2]$.
Почему нельзя использовать пуши? Для массовых операций с пушами должно быть выполнено свойство, что отложенная операция может складываться, но в случае 2D ДО мы должны складывать не числа, а отрезки, и их объединять уже не получится. Но помимо пушей есть другой тип массовых операций.
Сперва научимся делать прибавление на отрезке и сумму на отрезке без пушей в одномерном ДО.
В каждой вершине будем хранить $sum[v]$ и $add[v]$ — сумму на отрезке и сколько мы прибавим каждому элементу на отрезке. Рассмотрим запрос прибавления: для всех вершин, посещенных нашей функцией (на картинке желтые и зелёные), мы корректно пересчитаем значение в вершине, для суммы это $sum[v] +...
Теперь запрос суммы. Чтобы узнать актуальную сумму в вершине, нужно взять сумму
$add[p]$ по всем
113.
Codeforces Round #316 Editorial <a href="http://codeforces.com/contest/570/problem/A" title="Codeforces Round 315 (Div. 2)">570А — Выборы </a>
**Реализация**
Для каждого города определим: за кого он голосует. Просуммируем для каждого кандидата и определим победителя.
$O(n * m)$
<a href="http://codeforces.com/contest/570/submission/12523729" title="Codeforces Round 315 (Div. 2)">Решение</a>
<a href="http://codeforces.com/contest/570/problem/B" title="Codeforces Round 315 (Div. 2)">570B — Простая игра </a>
**Математика, разбор случаев**
Поймем, какие ходы интересные. Заметим, что Андрею нет смысла делать ход, при котором $|a – m| > 1$ так, как мы можем увеличить вероятность победы, если подвинем число a ближе к $m$.
Таким образом, мы рассматриваем два варианта хода $a = c – 1$ и $a = c + 1$. Вероятность победы в первом случае $c / n$, во втором $(n – c + 1) / n$. Выбираем наилучший вариант. Нужно помнить про случай $n = 1$.
$O(1)$
<a href="http://codeforces.com/contest/570/s...
Tutorial of Codeforces Round 316 (Div. 2)
114.
Разбор Codeforces Round #275 ## [problem:483A]
Автор задачи [user:gridnevvvit,2014-10-25]
В задаче предполагалось два решения:
1. Перебрать всевозможные тройки, и проверить, правда ли, что для этой тройки гипотеза неверна. Асимптотика такого решения
$O(n ^ {3} log A)$
2. Разобрать несколько случаев. Например, это можно сделать так:
~~~~
if (l % 2 != 0)
l++;
if (l + 2 > r)
out.println(-1);
else
out.println(l + " " + (l + 1) + " " + (l + 2));
~~~~
Авторское решение: [submission:8394832]
## [problem:483B]
Автор задачи [user:gridnevvvit,2014-10-25]
Авторское решение — бинпоиск по ответу. Во-первых, заметим, что если из набора $1, 2, \ldots, v$ можно собрать подарки, то и из набора
$1, 2, \ldots, v, v + 1$ можно собрать подарки.
Пусть $f(v)$ — функция, возвращающая ответ на вопрос: правда ли, что из набора $1, 2, \ldots, v$ можно собрать подарки друзьям.
пусть $f_1$ — количество чисел, которые делятся на $x$, а $f_2$ — колич...
Tutorial of Codeforces Round 275 (Div. 1)
Tutorial of Codeforces Round 275 (Div. 2)
115.
Разбор задач КРОК 2016 — Квалификация Лучше поздно, чем никогда...
------------------
### [problem:644A]
Из условия задачи следует, что либо демократов и республиканцев поровну (если $n$ чётно), либо демократов на одного больше (если $n$ нечётно). Так как представители одной и той же партии не должны сидеть на соседних креслах, представим парламентский зал в виде шахматной доски, где левая верхняя клетка будет белой. Затем начнем перебирать ряды клеток сверху вниз, а клетки в каждом ряду слева направо и будем по очереди сажать парламентариев — демократов в белые клетки, а республиканцев в черные.
Таким образом, если $n > a \cdot b$, ответом будет $-1$. В противном случае рассадка всегда найдется.
Для определения того, какого цвета клетка (и, соответственно, кого нужно в нее посадить), находящаяся в $i$-й строке и $j$-м столбце (в случае, если они нумеруются с единицы), можно поступить следующим образом. Если $(i + j) mod 2 = 0$, значит соответствующая клетка должна быть белой, иначе чёрной.
...
, которые закончат обрабатываться не позднее, чем появился текущий запрос,
нужно просто удалять их
116.
CF #900 (Div.3) G за O(n*log(A)) У меня есть решение [задачи G](https://codeforces.com/contest/1878/problem/G) с Codeforces Round #900 (Div.3), которое работает за $O(n \cdot (log(A) + log(n)) + q \cdot log(A))$ по времени.
Я заметил, что никто не упоминал это решение, поэтому я попробую его объяснить.
<spoiler summary="Авторское решение подразумевает сделующее:">
1. Посчитаем бинарные подъёмы для каждой вершины. Это включает в себя вычисление предка при подъёме и вычисление побитового ИЛИ при этом подъёме. Это занимает $O(n \cdot log(A))$ по времени и памяти.
2. Для каждого запроса найдём LCA при помощи бинарных подъёмов.
3. Пусть $x$ — одна вершина из запроса, $y$ — вторая и $l$ — их LCA. Давайте переберём промежуточную вершину $z$ на пути $path(x, y)$. Будет не более $log_2(A)$ вершин, которые изменяют значение ИЛИ на пути $path(x, y)$, потому что в числе не может быть больше бит.
4. Чтобы найти эту вершину $z$, нам нужно подниматься от вершины $x$ пока значение ИЛИ не меняется. Затем ...
117.
Всероссийский школьный этап всероссийской олимпиады по информатике В этом году случилось уникальное событие — для большинства школьников России школьный этап всероссийской олимпиады школьников по информатике проводился по едиными правилам, общим комплектам задач (всего было 4 варианта заданий на всю страну), с использованием тестирующей системы.
Организация
------------------
Формально по порядку проведения ВсОШ за проведение школьного этапа отвечают муниципалитеты, поэтому уровень организации школьного этапа зачастую оставляет желать лучшего, а местами он и вообще не проводится. Образовательный центр "Сириус" взялся организовать [школьный этап всероссийской олимпиады по шести предметам — математике, информатике, физике, химии, биологии, астрономии](https://siriusolymp.ru/). В прошлом году была апробация для шести регионов. В этом году было предложено присоединиться всем регионам, "подписаться" можно было только на комплект из шести предметов.
Согласились почти все — проще перечислить регионы, которые не участвовали и р...
118.
Разбор квалификационного раунда Яндекс.Алгоритм 2017 Этот раунд был подготовлен разработчиками минского офиса Яндекса.
[Задача А. Управление задачами](https://contest.yandex.ru/algorithm2017/contest/4502/problems/A/)
------------------
Рассмотрим решение, которое работает с квадратичной асимптотикой. Для этого будем действовать в соответствии с условием задачи: заведем счетчик последней закрытой задачи, будем проходить по списку задач от начала до конца, увеличивая счетчик, когда проходим через элемент массива задач, соответствующий следующей задаче. Из-за достаточно больших ограничений это решение не укладывается по времени.
Рассмотрим, в каком случае, мы уже не найдем никакой подходящей задачи до конца списка. Оказывается, только в том случае, когда после закрытия задачи с номером $x$ следующая задача с номером $(x+1)$ расположена ближе к началу списка. Следовательно, для решения задачи нужно по каждому номеру задачи узнать ее позицию в списке задач, а затем подсчитать количество различных номеров $x$ таких, что позиция задач...
) следовало бы до обработки запросов. Это позволило бы всегда отвечать на запрос
за время
119.
Разбор Летней олимпиады по программированию #1 [contest:329695]
Разбор в PDF:
https://drive.google.com/file/d/1idV_I1xRuPN2PgfEliYZLReB7XJ5cCGd/view?usp=sharing
[problem:329695A]
Автор задачи: [user:Jugo,2021-06-09]
Автор перевода: [user:MatesV13,2021-06-09]
Автор решения: [user:Jugo,2021-06-09]
<spoiler summary="разбор">
Просто переберём все числа на отрезке $[l;r]$ и с помощью деления чисел на 2, 3, 5 проверить, является ли полученное число единицей. Асимптотика этого решения будет $n * \sigma(n)$, где $\sigma(n)$ — количество двоек, троек и пятёрок в факторизации числа.
</spoiler>
<spoiler summary="код">
~~~~~
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
bool f(int n){
while((n & 1) == 0)
n >>= 1;
while(n % 3 == 0)
n /= 3;
while(n % 5 == 0)
n /= 5;
return n == 1;
}
int32_t main() {
int l, r;
cin >> l >> r;
int cnt = 0;
for(int i = l; i <= r; i++)
cnt += f(i);
cout << cnt;...
120.
IX (XX) открытый командный студенческий чемпионат Поволжья по спортивному программированию **11 — 14 апреля 2019 года** Самарский университет при поддержке Министерства образования Самарской области, Департамента информационных технологий и связи Самарской области, компаний Mercury Development, Maxifier, Magenta Technology, CQG, Вебзавод проводит **IX (XX) открытый командный студенческий чемпионат Поволжья по спортивному программированию**.
Подробная и регулярно обновляемая информация содержится на [странице чемпионата](http://contest.uni-smr.ac.ru/ru/championship2019/).
[cut]
<BR/>
**Чемпионат проводится в один тур в формате ACM ICPC.**
Ориентировочное количество участников — до 75 команд.
_Оргвзнос за участие в чемпионате не предусмотрен._
Первый этап регистрации — до 20 марта (порядок регистрации описан на [странице чемпионата](http://contest.uni-smr.ac.ru/ru/championship2018/)) — ждём заявки с указанием количества команд. Если в команде есть студенты, не являющиеся гражданами РФ, просим срочно связаться с оргкомитетом (написа...
121.
Codeforces Round #368 (Div.2) разбор Спасибо всем, кто написал раунд.
Надеюсь, задачки вам понравились.
A — Фотографии Брейна
Нужно сделать ровно то, что написано в задачке: считать все символы, и, если есть хоть один из набора ${C, M, Y}$ вывести "#Color" иначе — "#Black&White"
B — Пекарня
Заметим, что нет смысла выбирать город для пекарни и город со складом так, чтобы между ними было больше одной дороги, т.к. каждая дорога увеличивает расстояние, за которое нужно платить.
Таким образом, задача сводится к следующей: выбрать два соседних города так, чтобы в одном был склад, а в другом — нет. Для этого просто перебираем все города со складом, среди соседей каждого ищем город без склада и обновляем ответ. Если такой пары городов нет, выводим -1.
C — Пифагоровы тройки
Пожалуй, самая интересная задачка этого раунда.
Формализуем задачку:
Дано число a. Найти такие два числа b и c, чтобы выполнялось одно из следующих двух равенств:
$a^2 = b^2 + c^2$ или
$a^2 = abs(...
Давайте обрабатывать каждый запрос следующим образом:
Tutorial of Codeforces Round 368 (Div. 2)
122.
Codeforces и Polygon: несколько улучшений [март 2019] Привет, Codeforces!
Вот несколько последних улучшений здесь и в Polygon.
### Слабые и утекшие пароли
Мы часто слышим об утечках паролей от различных сервисов. Учитывая, что иметь одинаковые пароли распространённая (но небезопасная) практика, на Codeforces и в Полигоне были внедрены улучшения для определения слабых или утекших паролей. Если сверху сайта вы видите плашку, что ваш пароль небезопасен, то просто тут же смените его.
### Указание типа раунда при создании предложения о контесте
Этот пункт немного лучше упорядочивает работу с авторами. При создании предложения контеста, пожалуйста, указывайте тип контеста. Оставьте поле пустым только, если вы совсем не уверены в типе раунда (что странно).
### Календарь
Исправлены ошибки при синхронизации официальных контестов Codeforces [в календаре](https://codeforces.com/calendar). Теперь всё должно быть чётко.
### Я доверяю этому пользователю
В настоящее время Codeforces предоставляет развитую инфраструктуру для ор...
123.
Видео: Segment Tree Beats Всем привет!
В новом видео мы поговорим про удивительную структуру данных Segment Tree Beats (Анимешное дерево отрезков), которая позволяет поддерживать огромное количество операций, с которыми не справляется обычное дерево отрезков. Узнаем, как брать числа на отрезке по модулю, применять операции min= и max=, добавлять к ним +=, а также еще и искать НОД на отрезке с этими операциями. Все это с понятными доказательствами, так что не бойтесь, все будет несложно! В следующей части мы рассмотрим еще больше удивительных запросов, так что не пропустите.
[Ссылка на видео](https://youtu.be/58csqxAD8vM)
**There's also the English version of this video** [here](https://youtu.be/NwkO73jGSPA)
Буду рад, если вы посмотрите этот ролик и оставите комментарий со своими впечатлениями, замечаниями, мыслями и идеями насчет новых видео. Также можете написать мне в [телеграм](https://t.me/peltorator), если вы чего-то не поняли в видео или у вас возникли любые вопросы. Буду рад ответить!
Може...
124.
Разбор Codeforces Round #Pi [problem:567A]
Можно сделать очевидный вывод — наибольшей стоимостью отправки письма из $i$-го города будет являться максимум из расстояний от $i$-го города до первого и от $i$-го города до последнего ($max(abs(x_i - x_0), abs(x_i - x_{n-1})$). А минимальной стоимостью отправки будет являться минимум из расстояний до соседних городов (для $i$-го города соседними являются города с номерами $i-1$ и $i+1$), то есть ($min(abs(x_i - x_{i - 1}), abs(x_i - x_{i + 1})$). Для всех городов, кроме самого левого и самого правого, это считается нормально. Так как у самого левого нет соседей левее, значит минимальная стоимость определяются однозначно ($abs(x_i - x_{i+1})$). Аналогично для самого правого города ($abs(x_i - x_{i-1})$).
[Авторское решение](https://gist.github.com/VladimirPetrov/ad0ecbd0e81a578d7797)
[problem:567B]
Чтобы корректно обрабатывать события, нам необходимо знать, находится ли в библиотеке на данный момент человек. Для этого будем использовать массив $in$ тип...
Итак, если к нам поступает запрос вида "$+ a_i$", то мы увеличиваем $state$ на
единицу, отмечаем
Tutorial of Codeforces Round #Pi (Div. 2)
125.
Интернет-тур Всесибирской 2020 / Гран-при Евразии: разбор задач ### 7. Придорожная оптимизация
Для каждого теста нужно вывести число рёбер в лесе: количество вершин — число компонент связности.
Поскольку в условии дана матрица достижимости (уже транзитивно замкнутая матрица смежности), то ответ можно найти проходом по матрице.
Например, посмотреть на значения в позиции i, j над главной диагональю:
если стоит 1 и индекс j ещё не использован, то увеличить ответ на 1 и пометить индекс j как использованный.
### 6. Дробь
Задача сводится к тому, что для запроса (знаменателя) $X$ нужно найти ближайшее $X_0$ ($X_0$ >= $X$) такое, что в системе счисления $B$ дробь $1/X_0$ конечная.
Введем функцию $F(a)$ — множество различных простых чисел в факторизации числа $a$.
Тогда, $X_0$ подходит к ответу, если $F(X_0)$ является подмножеством $F(b)$,
то есть в разложении $X_0$ используются только те простые, которые используются в разложении $b$.
Предпосчитаем для заданного $B$ всевозможные $X_0$ в массив $V$, отсортировать их.
Дальше ...
ответа на запрос нам нужно найти ближайшее число, которое больше или равно
числу из запроса. Это можно
126.
Интересная задачка на структуры данных. Мне очень интересно, умеют ли сейчас люди решать вот такую задачу (я приведу сперва основную идею, а потом несколько вариаций условия):
Дана плоскость т.е. бесконечный грид точек с целыми координатами. На плоскость упали по очереди N прямоугольников (по очереди, значит, порядок важен) со сторонами параллельными осям координат и значением $value_i$ внутри. Для всех точек, покрытых прямоугольником, нужно сделать некоторую **операцию** с $value_i$. После этого вам поступают K **запросов** вида "посчитайте что-нибудь на прямоугольнике".
Предполагается, что структуру данных для N прямоугольников можно строить в Offline, а вот на запросы нужно отвечать в Online.
1. операция +=, запрос сумма
2. операция +=, запрос минимум
3. операция присваивание, запрос сумма
4. операция присваивание, запрос минимум
Утверждается, что я умею решать все 4 задачи за следующее время:
1. Time = $N log$, Memory = $N log$, AnswerQuery = $log$
2. Time = $N log^2$, Memory = $N log^2$, AnswerQuery =...
1. операция +=, запрос сумма 2. операция +=, запрос минимум 3. операция
присваивание,запрос
127.
Разбор задач Codeforces Round #152 **Задача A (div2) — Шкафы**
Автор: [user:max777alex,2012-11-27]
В этой задаче можно рассмотреть независимо все левые дверцы шкафов и, аналогично, все правые. Очевидно, чтобы привести все левые дверцы шкафов в одинаковое положение, нужно определить какое из двух состояний ("левая дверца открыта" или "левая дверца закрыта") встречается чаще. Все левые дверцы, которые находятся в другом состоянии требуется привести к этому. Аналогично надо поступить и с правыми дверцами. Если аккуратно посчитать в таком случае количество операций изменения состояния дверцы, то это оно и будет ответом.
**Задача B (div2) — Котенок Гав**
Авторы: [user:max777alex,2012-11-27], [user:KhaustovPavel,2012-11-27]
В данной задаче требовалось найти минимальное положительное $N$-значное число, которое делится без остатка на $2$, $3$, $5$ и $7$. Очевидно, раз все эти четыре числа являются простыми, то число, которое делится на все эти четыре числа, должно делиться на их произведение $2 \cdot ...
128.
Codeforces Round #226 (Div. 2) — Editorial [problem:385A]
В этой задаче нужно было понять, что ответ это максимум из $a[i] - a[i - 1] - c$, для $i$ = $2..n$ и не забыть,
что ответ не может быть отрицательным, так как медведь может не занимать в долг бочонок меда.
[problem:385B]
В этой задаче нужно было написать решение оптимальней наивного.
Для этого, например, можно перебирать первым циклом левый индекс $l$ рассматриваемой подстроки,
а вторым циклом правый индекс $r$ рассматриваемой подстроки $(l \le r)$.
Если на какой-то позиции $i$ нашлась подстрока "bear", значит все подстроки $x(l,j)$ $(i \le j)$,
также содержат "bear" в качестве подстроки. Значит к ответу можно сразу прибавить $|s| - j + 1$ и
выйти из второго цикла.
Также требовалось понять, что если в строке $x(l,j)$ не было подстроки "bear", тогда в строке $x(l,j + 1)$ подстрока "bear"
могла появиться только в последних четырех символах.
[problem:385C]
В этой задаче нужно было решить несколько подзадач:
1) Посчитать количество вхождений к...
4) Зная префиксные суммы, можно отвечать за $O(1)$ на запрос $[l,r]$. Это
делается так $pre[r
Tutorial of Codeforces Round 226 (Div. 2)
129.
Разбор Codeforces Round #200 #### [problem:344A]
По определению каждый островок состоит из последовательных одинаково направленных домино. Значит, в местах, где соседние домино направлены не одинаково, кончается один островок и начинается следующий. Значит, если таких мест $x$, то ответ равен $x+1$.
Сложность решения $O(n)$. Автор задачи: [user:gen,2013-09-15].
**Бонус:** Задача была придумана в день перед контестом и полностью дополнила физически направленный комплект для DivII :]
#### [problem:344B]
Первое решение. Во-первых, заметим, что сумма $a+b+c$ должна быть чётной, потому что каждое ребро прибавляет два к сумме. Теперь допустим, что между 1-ым и 2-ым, 2-ым и 3-им, 3-им и 1-ым атомами есть $x$, $y$ и $z$ связей, соответственно. Поэтому нам нужно решить систему $x+z=a$, $y+x=b$, $z+y=c$. Можно заметить, что решением этого уравнения являются длины касательных на треугольнике со сторонами $a$, $b$, $c$ к его вписанной окружности, и равняются $\frac{b+c-a}{2}$, $\frac{c+a-b}{2}$, $\frac{b+a-c}{2...
Tutorial of Codeforces Round 200 (Div. 1)
Tutorial of Codeforces Round 200 (Div. 2)
130.
Codeforces Round #130 (Div. 2) Разбор Задач Сначала расположим задачи по сложности, как предполагалось авторами: A, D, B, C, E. Теперь разберем задачи по порядку следованию в соревновании.
[problem:208A]
Эта задача носила технический характер. Сначала нужно было удалить все вхождения слова WUB в начале и в конце исходной строки. А затем распарсить оставшуюся строку, разделяя токены словом WUB. Пустые токены нужно было пропустить. Ограничения были небольшие, реализовать это можно было как угодно.
[problem:208B]
В этой задаче можно было написать поиск в ширину. В качестве состояния можно взять следующую четверку: количество оставшихся стопок, а также три строки, которые обозначают три крайние правые карты на трех крайний стопках. Соответственно мы имеем два перехода в общем случае, когда перекладываем последнюю карту на $1$, либо на $3$ влево. Если количество стопок в какой-то момент окажется равным $0$ выводим $YES$, иначе $NO$. Состояний $O(N^4)$, переходов $2$, итого временная сложность решения $O(N^4)$.
[problem...
Tutorial of Codeforces Round 130 (Div. 2)
131.
Codeforces Round #123 (Div. 2) Разбор Задач [problem:195A]
Полное видео скачается через $all = (c \cdot a + b - 1) / b$ секунд. В этой задаче можно было перебрать величину ответа $1<=t<=all$. Чтобы удовлетворить условию задачи, достаточно проверить, что в последний момент времени t0 = all выполняется условие, написанное в тексте задачи, а именно $t0 \cdot b >= (t0 - t) \cdot a$.
[problem:195B]
В этой задаче нужно было аккуратно реализовать описанный в условии процесс. Вначале заметим, что мяч с номером $i > m$ попадет в одну корзину с мячом под номером $i - m$. Поэтому достаточно распределить первые $m$ мячей. Это удобно сделать при помощи двух указателей $lf$, $rg$, начиная с середины. Поочередно кладем мяч сначала слева, затем справа и двигаем указатели. Единственный раз, когда нужно дважды подвинуть левый указателей, возникает в самый первый момент, если $m$ нечетно.
[problem:195C]
Данная задача носила реализационный характер. В своем решении я поступал следующим образом. Удалим из текста все пробелы, кроме...
Аккермана http://en.wikipedia.org/wiki/Ackermann_function#Inverse) на запрос
при применении ранговой
132.
Codeforces Round #197 — Разбор [problem:339A]
Разбор написан [user:Fefer_Ivan,2013-08-26]
Для решения этой задачи можно посчитать количество цифр 1, 2 и 3 во входных данных. Пусть в данных $c_1$ цифр 1, $c_2$ цифр 2 и $c_3$ цифр 3.
Тогда необходимо вывести последовательность из $c_1$ цифр 1, $c_2$ цифр 2 и $c_3$ цифр 3, разделяя соседние цифры знаком +.
[problem:339B]
Разбор написан [user:Fefer_Ivan,2013-08-26]
Для решения этой задачи необходимо быстро вычислять время на перемещение между зданиями $a$ и $b$. Пусть $a \le b$, тогда Ксения попадет из $a$ в $b$ за $b - a$ шагов.
Иначе, т.е. если $a > b$, Ксении придется ехать через здание с номером 1. Таким образом ей потребуется совершить $n - a + b$ шагов.
[problem:339C]
Разбор написан [user:Fefer_Ivan,2013-08-26]
Для решения этой задачи введем понятия баланса. Баланс — это разность суммы весов гирь на левой чаше весов и суммы весов гирь на правой чаше. В самом начале, баланс равен нулю.
На каждом шаге Ксения кладет одну гирю на од...
дерева отрезков, которые лежат на этом пути. Если все делать правильно, то
каждыйзапрос обновления
Tutorial of Codeforces Round 197 (Div. 2)
133.
Анонс MemSQL start[c]up [MemSQL](http://www.memsql.com) с радостью сообщает о проведении **start[c]up** -- соревнования по программированию, проводимого на Codeforces. Start[c]up состоит из двух раундов.
Оба раунда подготовлены программистами MemSQL:
[**<font color=red>pieguy</font>**](http://community.topcoder.com/tc?module=MemberProfile&cr=22777893), [**<font color=red>nika</font>**](http://community.topcoder.com/tc?module=MemberProfile&cr=20315020), [**<font color=red>exod40</font>**](http://community.topcoder.com/tc?module=MemberProfile&cr=20036294), [**<font color=red>SkidanovAlex</font>**](http://community.topcoder.com/tc?module=MemberProfile&cr=22662189) и [**<font color=red>dolphinigle</font>**](http://community.topcoder.com/tc?module=MemberProfile&cr=22752635).
Раунд 1 состоится онлайн 13 июля и будет проведен по стандартным правилам Codeforces. На нем будет представлено пять задач, сложность которых сопоставима со средним раундом на Codeforces. Для участия в первом раунде допускаются все жел...
134.
Codeforces Round #114 — Разбор #### Задача [problem:168A] Автор ~kuniavski,2012-03-27.
В этой задаче надо было написать ровно то, что было описано в условии.
В частности, надо было чтобы на митинг пришло $\left\lceil \frac{N \cdot Y}{100} \right\rceil$
людей. Соответственно, для этого надо было создать
$\max(0,\left\lceil \frac{N \cdot Y}{100} \right\rceil-X)$ клонов.
#### Задача [problem:168B] Автор ~kuniavski,2012-03-27.
В этой задаче опять-таки надо было написать ровно то, что было описано в условии.
Считываем строки по одной. Кроме того храним последний блок строк, не являющихся
усиливающими. Если очередная строка --- усиливающая (что проверяется
линейным проходом), то выводим последний блок, если он есть, и саму строку.
Иначе удаляем из строки все пробелы и добавляем к последнему блоку. [cut]
Остается только различить пустой блок и блок из пустых строк.
#### Задача [problem:167A] Автор ~Alex-Gran,2012-03-27.
В этой задаче наконец-то надо было немного отойти от перевода условия
на язык пр...
Tutorial of Codeforces Round 114 (Div. 1)
Tutorial of Codeforces Round 114 (Div. 2)
135.
Разбор задач Codeforces Beta Round #80 <table border="0" cellpadding="5" cellspacing="0" width="100%">
<tbody><tr>
<td bgcolor="#cccccc" width="2%" nowrap="nowrap"><div align="center"></div></td>
<td bgcolor="#cccccc"><div align="center"> <p><strong>Блэкджек (<a href="http://codeforces.com/contest/104/problem/A">задача A, 2-ой дивизион</a>). Автор задачи - <span class="Apple-style-span" style="font-family: verdana, arial, sans-serif; font-size: 12px; "><a href="http://codeforces.com/profile/Alex_KPR" title="Подполковник Alex_KPR" class="rated-user user-red" style="font-family: arial; text-decoration: none !important; font-weight: bold; color: rgb(0, 0, 204); ">Alex_KPR</a></span></strong></p>
</div></td>
<td bgcolor="#cccccc" width="2%" nowrap="nowrap"> </td>
</tr>
<tr>
<td bgcolor="#eeeeee"><p align="justify"> </p> </td>
<td bgcolor="#eeeeee"><p align="justify">Очевидно, что масти никакой роли не играют. Рассмотрим теперь подробно все случаи:</p>
<p align="justi...
Tutorial of Codeforces Beta Round 80 (Div. 2 Only)
136.
Оптимизации динамики (максимум с запретами) :D Всем привет! Хочу рассказать о достаточно простом приеме (не знаю как называется) для оптимизации динамики. Очень часто бывает так, что при пересчете нам надо искать минимум в какой-нибудь уже посчитанной таблице, но при этом игнорируя некоторое конечное количество строк и столбцов; как оптимизировать такое и подобное, описано в блоге.
Постановка задачи
==================
Итак, у нас есть таблица, предположим, что большая — $N \times N$, и мы хотим сделать какое-то большое количество запросов вида «Найди максимальное значение в таблице, которое не лежит в столбцах из множества $C$ и строках из множества $R$», при этом для каждого запроса гарантируется, что $max ( |C|, |R| ) \leq K$, где $K$ -- какая-то очень маленькая константа. Эту задачу мы бы могли решать, например, с помощью двумерного ДО -- но это работает долго и занимает гораздо больше памяти.
Решается задача просто, давайте для начала, найдем $x_1$ — глобальный максимум в таблице и запомним его позицию ...
137.
Белорусская областная олимпиада 2019 Не хотел создавать данный пост — надеялся, что кто-то другой сделает, но нет :) На этой неделе проходят областные олимпиады в Беларуси. Все как обычно, два тура по 4 задачи, 5 часов на их решение. Здесь предлагаю обсудить задачки, решения и так далее.
## Первый тур
[Условия задач](https://yadi.sk/i/DGcfOZgO9Ot-SQ), [обзорный лист](https://yadi.sk/i/PCiXXAbsxJhlNg).
#### Задача 1. Олимп-Сити
<spoiler summary="Решение">
Сложность по времени $O(\sqrt n)$</spoiler>
#### Задача 2. Дружелюбные соседи
<spoiler summary="Решение">Решим задачу для полоски. А решать такую задачу можно жадно. Ведь действительно, если мы можем поставить очередную перегородку в позициях $i$ и $i + 1$, то будет не хуже, если мы поставим в $i + 1$. Чтобы понять, нужно ли нам ставить перегородку, будем хранить текущий $OR$ чисел, между которыми еще нет перегородок. Если $AND$ с очередным числом дает больше $1$, то мы обязаны поставить перед этим числом перегородку.
Чтобы решить исходную зада...
138.
Разбор задач Educational Codeforces Round 1 Задачи учебные — постараемся сделать разбор подробным.
### [problem:598A]
Если бы в этой задаче не было бы "хитрости" и надо бы было просто найти сумму $1 + 2 + \dots + n$, то, воспользовавшись формулами суммирования арифметической прогрессии, можно было прийти к результату $s=n \cdot (n+1) / 2$ (числа такого вида называются треугольными).
Однако каждое число, которое является степенью двойки, должно быть просуммировано не со знаком "плюс", а со знаком "минус". Давайте вычтем по два раза (так как первое вычитание просто изымет число из суммы, а второе — вычтет) каждую из степеней двойки, которые не превосходят $n$. Проще всего это сделать с помощью цикла вроде этого:
~~~~~
long long pow2 = 1;
while (pow2 <= n)
s -= pow2 * 2, pow2 *= 2;
~~~~~
Значение $s$ после такого цикла и будет ответом. Количество итераций этого цикла не превосходит двоичного логарифма числа $n$ (точнее — еще плюс единица), что является числом около 30 для максимального возмо...
$" от позиции $l$). Следовательно, весь запрос обрабатывается фрагментом кода:
139.
Разбор задач Coder-Strike 2014 Финал [problem:421A]
В данной задаче нужно было для каждого яблока определить, кому оно нравится, и отдать его этому хомяку. Так как гарантировалось, что ответ существует, то каждое яблоко нравилось либо Александру, либо Артуру.
[problem:420A]
В данной задаче нужно было проверить, что заданная строка является палиндромом, и что она состоит только из симметричных символов. Симметричные символы — $AHIMOTUVWXY$.
[problem:420B]
Прежде всего, добавим в ответ всех людей, которые ни разу не упоминались в сообщениях.
Далее рассмотрим два случая.
1) Есть участник с номером $i$ такой, что первое сообщение с его участием $- i$.
Рассмотрим всех таких участников. Среди них выберем того, первое упоминание о котором встречается позже остальных. Тогда лишь он может быть лидером, так как другие ушли раньше, а те участники, о которых первое сообщение начинается с $<<+>>$, не могут быть лидерами, так как когда они пришли $i$ уже был. Но нужно проверить, может ли он на самом деле быт...
Будем идти по заданным запросам. Пусть текущий запрос утверждает, что число $a$
стоит на позиции $b, Пусть мы рассматриваем $i$-ый запрос, утверждающий, что число $a$ стоит на
позиции $b$. Нужно
Tutorial of Coder-Strike 2014 - Finals
140.
Codeforces Round #171 (Div. 2) Разбор Задач [problem:279A]
---------------
Из-за небольших ограничений в данной задаче можно было просто промоделировать шаги коня. Удобнее всего это делать, храня текущее направление движения и счетчик со значением, сколько шагов в эту сторону осталось. Заметим, что конь движется по спирали по следующему шаблону: 1 шаг вперед, поворот, 1 шаг вперед, поворот, 2 шага, поворот, 2 шага, поворот, 3 шага, поворот, 3 шага, поворот, 4 шага и так далее.
[problem:279B]
---------------
При решении этой задачи проще всего было воспользоваться методом двух указателей: левый указатель означает начало отрезка, правый — конец. При передвижении левого указателя на единицу вправо, правый надо двигать до тех пор, пока сумма $a_i$ внутри отрезка меньше или равна $t$. Так мы сможем для каждого левого конца найти максимально удаленный правый, а ответ на задачу — это максимальная длина из этих отрезков.
[problem:279C]
---------------
Давайте перед выполнением запросов выпишем в массив $down$...
141.
Codeforces Round #365 (Div. 2) Editorial ####[703A — Мишка и игра](http://codeforces.com/contest/703/problem/A)
Всё, что Вам требовалось сделать в этой задаче, — посчитать количество раундов, в которых победит Мишка, количество раундов, в которых победит Крис. Для этого следовало завести две переменные $countM$ и $countC$. Если в очередном раунде Мишка выкидывала на костях большее значение, чем Крис, то 1 следовало прибавлять к переменной $countM$. Если меньшее — к переменной $countC$. В конце нужно было сравнить полученные значения и вывести ответ.
####[703B — Мишка и путешествие](http://codeforces.com/contest/703/problem/B)
Рассмотрим первую столицу. Заметим, что стоимость исходящих из неё дорог равна $c[id_1] \, \cdot \, (sum - c[id_1])$, где $sum$ — суммарная красота **всех** городов. Таким образом, переходя от одной столицы к другой, мы сможем посчитать суммарную стоимость дорог, исходящих из столиц. Однако не стоит забывать, что дороги между столицами в таком случае будут посчитаны...
заметим, что ответом на запрос на отрезке $[l, \, r]$ ($l \le r$) будет
являться $\sum_{i = l}^{r} cnt[i
Tutorial of Codeforces Round 365 (Div. 2)
142.
Белорусская областная олимпиада 2018 Привет всем. На этой неделе (8-12 января 2018 года) проходит областная олимпиада по информатике в Беларуси. Олимпиада проходит во всех областях (а их у нас всего шесть) в одно и то же время с одним и тем же набором задач. Здесь можно обсудить олимпиаду, ознакомиться с уловиями задач (надеюсь, что все участники олимпиады ознакомятся с условиями на самой олимпиаде) и, может быть, если я смогу решить, с решениями.
**Всем участникам желаю удачи!**
[cut]
_Условия и решения задач для каждого из туров появятся не раньше их завершения._
## Первый тур
#### Задача 1. Два квадрата
<spoiler summary="Решение">_Задачу можно решать разными способами, но я попоробую рассказать самое короткое решение, которое только смог придумать._
Найдем bounding box закрашенных клеточек. Пускай мы будем знать его левую границу $l$, правую границу $r$, верхнюю границу $u$ и нижнюю границу $d$. Теперь заметим, что у нас может быть только два случая:
1. Левая верхняя клетка одного квадрата нахо...
и ответ на отрезке. Таким образом, мы сможет отвечать на каждый запрос за
время $O(\log n)$.
143.
Разбор Codeforces Beta Round #13 Представляю разбор Codeforces Beta Round #13. Если будут какие-то вопросы или замечания - прошу писать в комментариях.<div><br></div><div>[cut]</div><div><b>Задача A.</b></div><div>Достаточно просто перебрать все основания системы исчисления, просуммировать цифры числа по всем основаниям, а затем найти наибольший общий делитель полученной суммы и числа А-2 (количество оснований систем исчисления) и сократить полученную дробь на найденный НОД. Сложность алгоритма O(A).</div><div><br></div><div><b>Задача B.</b></div><div>Эта задача оказалась довольно неприятной для реализации, но все что нужно было сделать - аккуратно проверить выполнение трех пунктов, данных в условии. В вычислениях рекомендуется использовать целочисленную арифметику, делать все проверки при помощи векторных и скалярных произведений.</div><div><br></div><div><b>Задача C.</b></div><div>Заметим, что существует неубывающая подпоследовательность, которую можно получить из данной за минимальное количество ходов и у которой в...
Для того чтобы обработать запрос вбрасывания шарика, просто из лунки i будем
перепрыгивать
Tutorial of Codeforces Beta Round 13
144.
Разбор Codeforces Round #322 (Div. 2) [581A — Хипстер Вася](http://codeforces.com/problemset/problem/581/A)
------------------
Первое ответное число (количество дней, которое Вася сможет быть одет по моде) это $min(a, b)$, так как каждый из этих дней он будет надевать по одному красному и по одному синему носку.
После этого у него останутся либо только красные носки, либо только синие носки, либо не останется носков вовсе. Поэтому второе ответное число это $max((a - min(a, b)) / 2, (b - min(a, b)) / 2)$.
Асимптотика решения — O(1).
[581B — Элитные дома](http://codeforces.com/problemset/problem/581/B)
------------------
Данная задача решается следующим образом. Пойдем по массиву справа налево и будем поддерживать в переменной $maxH$ максимальную высоту дома, который мы уже рассмотрели. Тогда ответом для $i$-го дома будет число $max(0, maxH + 1 - h_i)$, где $h_i$ количество этажей в $i$-м доме.
Асимптотика решения — O($n$), где $n$ — количество домов.
[581C — Развитие навы...
Теперь, чтобы ответить на конкретный запрос стартовой позиции нужно найти
первую завправку правее
Tutorial of Codeforces Round 322 (Div. 2)
145.
Разбор Codeforces Round #124 [problem:197A]
Если первый игрок своим ходом не может поставить тарелку на стол (стол слишком маленький, и тарелка не помещается, т.е. $2r > min(a,b)$), выигрывает второй игрок.
Иначе выигрывает первый игрок. Выигрышная стратегия такова: первый игрок ставит свою первую тарелку в центр стола, а затем симметрично отражает ходы соперника относительно центра стола стола. Легко видеть, что если в этом случае второму игроку удастся совершить ход, первому это также удастся. А если не удастся, первый игрок победит, что ему и было нужно.
[problem:197B]
Решение задачи --- разбор случаев.
Легко понять, что важны лишь степени многочленов и их коэффициенты при старшем члене, остальные числа в инпуте --- для отвода глаз.
1. Если степень знаменателя больше, ответ равен "0/1".
2. Если степень числителя больше, ответ --- бесконечность. Чтобы понять, какая именно, надо посмотреть на знаки при старших коэффициентах. Если знаки одинаковые, то положительная, иначе --- отрицательная.
3. ...
одного символа и запрос, является ли данная подстрока палиндромом. Это можно
делать с помощью хешей
Tutorial of Codeforces Round 124 (Div. 1)
Tutorial of Codeforces Round 124 (Div. 2)
146.
Codeforces Round #429 [Editorial] **Щедрый Кефа — Adiv2** <br>
**(Авторы: [user:Fedosik,2017-08-18], [user:ZZzzZZzzzZzzzZZzz38,2017-08-18])** <br> <br>
Рассмотрим каждый цвет по отдельности. Мы можем раздать все шарики цвета $c$ друзьям Кефы только если $c \leq k$. Потому что иначе, по принципу Дирихле, хотя бы один из друзей получит два или более шариков одинакого цвета. <br>
Поэтому сделать нужно следующее: посчитать количество шариков каждого цвета, $cnt_{c}$. <br>
А потом просто проверить, что $cnt_{c} \leq k$ для всех возможных $c$. <br>
**Сложность: $O(N + K)$** <br>
<br>
**Находка — Bdiv2** <br>
**(Автор: [user:Fedosik,2017-08-24])** <br> <br>
Первый игрок выигрывает, если в массиве есть хотя бы одно нечетное число. Давайте докажем это. <br>
Обозначим суммарное количество нечетных чисел как $T$. <br>
Тогда есть два случая: <br>
1) $T$ нечетное. Первый игрок может забрать весь массив и выиграть. <br>
2) $T$ четное. Предположим, что позиция самого правого нечетного числа $pos$. Тогда стр...
-08-20])**
Используем метод разделяй и властвуй.
Допустим, текущий запрос на отрезке $[L
147.
Codeforces Round #204 — разбор ### Разбор задач Codeforces Round #204
#### [problem:352A]
Рассмотрим решение как разбор случаев:
1. Если у нас нету нулей, то ответ \-$1$.
2. Если у нас меньше чем $9$ пятерок, то ответ $0$.
3. Иначе ответ имеет вид:
4. 1. максимальное количество пятерок, кратное $9$
4. 2. все нули, что у нас есть
#### [problem:352B]
Будем идти по массиву слева направо. На каждом шаге будем хранить массивы:
1. $next_x$ — последнее вхождение числа $x$
2. $period_x$ — период, с которым встречается $x$
3. $fail_x$ — был ли момент, когда число $x$ перестало подходить
Теперь когда мы получаем число рассматриваем случай, когда оно первое, второе или встречалось больше чем два раза.
Все случаи описаны в любом прошедшем системное тестирование решении.
#### [problem:351A]
Изначально запомним количество целых чисел — $C$. Далее округлим все числа вниз, и посчитаем сумму. Теперь мы можем изменить сумму, округлив некоторые чис...
Tutorial of Codeforces Round 204 (Div. 1)
148.
IOI 2016: второй тур Вот-вот начнется второй тур IOI.
[Результаты](http://pcms.ioi2016.ru/)
[Таблица от снарка](http://ioi2016.snarknews.info/index.cgi?data=2016/day1pre&class=ioi2016&year=2016)
0:00 Кажется контест начался по расписанию. Как и в прошлый раз после первого успешного сабмита, выложу краткие условия задач (на этот раз с решениями).
0:11 В таблице появились первые баллы. Пока это 7 и 10 по первой. Это переборы в частных случаях. Но это повод выложить задачи.
0:19 Появилось 32 балла по 4-ой. Это разбор случая "нет данных исходно, только длина". Наши пока молчат. Думаю по этой задачи большинство будет сразу писать 100. Ну или хотя бы 80-90, если почему-то получился квадрат.
0:24 Появилось 38 по 5-ой и 4 по 6-ой. 4 это какой-то бессмысленный случай. 38 это осмысленное неоптимальное решние. Его думаю более-менее все сдадут.
0:30 ~gritukan,2016-08-16 — первая 100 по 4-ой. Думаю сейчас посыпятся еще много 100.
0:32 Появилось 49 по 5-ой. Это чуть другое неоптимально...
149.
Great Permutator — головоломка для программистов [важный UPD в конце записи] **важный UPD в конце записи**
Всем привет!
Хочу представить вам мой небольшой проект, над которым я тружусь в свободное время уже более полугода. Это игра, которая называется Great Permutator.
<img src="http://media.indiedb.com/images/games/1/21/20335/wallpaper_small.png" alt="image"/>
Почему здесь? Дело в том, что данная игра представляет собой головоломку особого жанра, так называемого engineering puzzle. Примеры игр такого жанра: LightBot, Manufactoria, The Codex of Alchemical Engineering и, конечно же, SpaceChem. Мне такие игры очень нравятся и, вроде бы, нравятся многим программистам.
<blockquote>На самом деле первоначальная версия этой статьи была подготовлена для Хабра. Но я по глупости опубликовал ее не в тот хаб и меня забанили. Когда разбанят (и разбанят ли) - непонятно, поэтому публикую здесь.</blockquote>
Чтобы было интереснее, я расскажу некоторые моменты о том, как создавалась эта игра. Такое повествование еще называют постмортемом, но здесь это слово, ...
которые было не стыдно отослать запрос). Некоторые ответили вежливым отказом,
другие ничего не ответили
150.
Петр Калинин: Про областную олимпиаду **(C) Петр Калинин, 2015-16. Этот текст можно свободно распространять на условиях лицензии Creative Commons Attribution-ShareAlike 2.0 (CC-BY-SA).**
Областная олимпиада по информатике (формально — региональный этап Всероссийской олимпиады) пройдет в два тура 4 и 6 февраля в ННГУ им. Лобачевского.
Немалая часть статьи конкретно про Нижний Новгород, но информация интересная :)
Отбор на область
----------------
Отбор на нее осуществляется следующим образом. Решения районной (она же городская в ряде городов области — Дзержинске, Арзамасе и т.д.) олимпиады от всех школьников, набравших на районе 200 и более баллов, отправляются в жюри областной олимпиады (точнее, я точно не знаю, в жюри ли, или людям, ответственным за район на уровне области, но это не так существенно). Там все эти решения перепроверяются и сводятся по каждому классу в единую таблицу. И в этой таблице проводится граница: для каждого класса выбирается проходной балл, и все, кто набрал столько баллов или больше, ...
151.
Codeforces Round #163 (Div. 2) Разбор Задач [problem:266A]
В этой задаче нужно было посчитать количество пар подряд идущих одинаковых букв. Это можно сделать в один цикл за время $O(N)$.
[problem:266B]
В этой задаче нужно было аккуратно реализовать процесс, описанный в условии. Нужно было $t$ раз обменять два элемента $i$ и $i+1$ местами, если на $i$-ом месте стоял мальчик, а на $i+1$-ом стояла девочка. Главное, не нужно было одну девочку двигать влево несколько раз за одну итерацию. Решение можно реализовать за $O(N \cdot T)$.
[problem:266C]
Эту задачу будем конструктивно, даже скорее используя индуктивный подход. В начальный момент у нас есть квадратная матрица размера $n$ и $n-1$ единица в ней. Следовательно, существует столбец, в котором нет ни одной единицы. Поставим этот столбец на $n$-ое место. Таким образом, правый нижний элемент будет равен $0$. Теперь найдем любую строку, в которой есть хотя бы одна единица, и поставим ее на $n$-ое место.
Мы добились того, что в клетке $(n, n)$ стоит $0$, а также в по...
(ответ на запрос дерева) вторую (то что нужно получить). Получится выражение,
которое нужно вычесть
Tutorial of Codeforces Round 163 (Div. 2)
152.
Обзор решений задачи KQUERY _За последнее время у меня набралось определённое количество заметок на различные темы, с которыми до конца не ясно что делать. Скорее всего, для синих эта информация не слишком актуальна, для красных — давно очевидна. Из этих заметок вряд ли получится сделать статьи, а достаточно заинтересованный человек вполне может собрать всю приведённую в них информацию из интернета по частям самостоятельно. Тем не менее, я всё же решил сделать пост (или, может быть несколько) на Codeforces, в надежде, что эти сведения для кого-нибудь окажутся полезными._
Оригинальная задача [KQUERY](http://www.spoj.com/problems/KQUERY/) формулируется следующим образом. Дан массив $\relax a$ размера $\relax N \le 3 \cdot 10^4$, а также $\relax Q \le 2 \cdot 10^5$ запросов вида $\relax (l, r, k)$ — определить количество элементов, больших $\relax k$, на отрезке $\relax [l; r]$.
Сразу следует заметить, что из-за достаточно малого TL вердикт Accepted по оригинальной задаче получает только одно из пр...
153.
Разбор личной олимпиады для 6-9 классов Разбор [contest:368205].
[problem:375720A]
<spoiler summary="Разбор">
Для тестов до 10 было достаточно повыписывать ответы на листочке.
Для второй группы можно было перебрать все возможные пары $i$, $j$ и проверить выполнение условия. $O(n^2)$
Для третьей группы нужно было понять, что для фиксированного $i$ $j = n - i$. $O(n)$
Для полного решения заметим, что для каждого числа от $0$ до $n$ мы сможем найти пару. Тогда ответ это $n + 1$. Итоговая асимптотика $O(1)$.
</spoiler>
<spoiler summary="Код">
~~~~~
#include <bits/extc++.h>
#define int int64_t
using namespace std;
int32_t main() {
int n;
scanf("%lld", &n);
n++;
printf("%lld", n);
}
~~~~~
</spoiler>
[problem:375720B]
<spoiler summary="Разбор">
Для первой группы было достаточно заметить, что ответ всегда равен $k$.
Для второй группы необходимо было найти количество единиц и двоек и решить аналогично первому случаю.
Для третьей группы необходимо было ...
154.
Реализация встречного дерева Фенвика для RMQ или ДО для курильщиков Доброго времени суток!
Началось все с того, что после прочтения [статьи](https://neerc.ifmo.ru/wiki/index.php?title=%D0%92%D1%81%D1%82%D1%80%D0%B5%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%A4%D0%B5%D0%BD%D0%B2%D0%B8%D0%BA%D0%B0) про встречное дерево Фенвика, я начал искать в интернете его реализацию, но (спойлер) так и не нашел. Безусловно, тема не нова, но, к сожалению, статью, описывающую эту структуру данных с приведенными примерами реализации, я так и не нашел. Перед прочтением данного поста советую ознакомиться с указанной статьей, т.к. на нее будут опираться все дальнейшие рассуждения.
Встречное дерево Фенвика
==================
Для начала, вспомним определение: Встречное дерево Фенвика (англ. counter tree Fenwick) — дерево Фенвика, в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле $f_{rev}[i]=\sum\limits_{j=i+1}^{i+2^{h(i)}}a[j]$. Сразу сделаю уточнение, что под прямым деревом Фенвика подразумевается массив, посчита...
// Ответ на запрос int bit_ask(int l, int r) { int res = NEUTRAL; for(; (r&r+1)
>= l && r >= l
155.
Разбор задач Codeforces Round #266 (Div. 2) [problem:466A]
-------------
Решение этой задачи основано на двух утверждениях: <br>
— Если $m\cdot a\le b$, то вообще не имеет смысла покупать абонементы. <br>
— Иногда имеет смысл купить абонементов на суммарное количество проездов больше чем нужно. <br>
Если нам выгодно купить абонемент на проезд, то максимальное количество абонементов которое мы используем полностью будет $x = \lfloor \frac{n}{m} \rfloor$. Для оставшихся $n - m\cdot x$ проездов мы можем либо накупить билетов, либо купить еще один абонемент и использовать его не полностью.
**Асимптотика**: $O(1)$<br>
**Решение**: [submission:7784793]
[problem:466B]
-------------
Без ограничения общности можем считать, что $a\le b$.
Во первых, надо рассмотреть случай, в котором уже можно поселить всех людей. Если
$6\cdot n\le a\cdot b$, то ответ $a\cdot b$ $a$ $b$.
В ином случае нам нужно увеличить какую-то сторону(возможно обе). Делать это будем так: переберем меньшую сторону комнаты $new_a$...
множеств для определению в одной/разных ли компонентах связности лежат
вершины. Отвечать назапрос при
Tutorial of Codeforces Round 266 (Div. 2)
156.
Russian Code Cup 2014 Final — Разбор задач **UPD:**Также специально для финала мы выпустили [видео-разбор](http://www.youtube.com/playlist?list=PLyQCF5K78w9_QRbUZHLsEeEe9RhJLu6ib).
<div> <h2>Задача A. Игра</h2>
<b>Идея:</b> Анна Малова<br>
<b>Реализация:</b> Анна Малова<br>
<b>Разбор:</b> Анна Малова<br>
<p>
Рассмотрим двудольный граф — первая команда, вторая команда. На ребре написано, какими подсказками владеет участник второй команды, которые еще не знает участник первой, то есть разность множеств подсказок участников.
Оставим только те ребра, на которых записано одно число. Среди таких ребер оставим только те, на которых записано только одно число.
</p>
<p>
Используя построенный граф, составим другой двудольный граф: вершинами первой доли являются участники первой команды, вершины второй доли — те подсказки, которые еще неизвестны первой команде.
Между двумя вершинами есть ребро, если было ребро в предыдущем двудольном графе, выходящее из той же вершины, ...
запрос на поддереве. Тогда запросы первого вида очень легко обрабатывать с
помощью суммы в
157.
Online LCA и подвешивание деревьев друг за друга. O(log n) Наименьший общий предок и подвешивание деревьев друг за друга (Online) && (O(log n)).
==================
### Постановка задачи:
**Дается изначально лес подвешенных деревьев. Дальше следуют запросы двух видов:**
- Найти наименьшего общего предка двух вершин a и b, или вывести то, что они в разных деревьях.
- Провести ребро между вершиной u и вершиной v. Гарантируется, что вершины u и v в разных деревьях, а также что, вершина u это корень дерева. (Получается после проведения ребра между вершиной u и v, они сольются в одно дерево, корнем которого будет корень дерева, в котором была вершина v)
_*Пример соединения двух деревьев, путем проведения ребра между двумя вершинами, выделенными красным*_
Решение:
------------------
Напомню, что задачу о нахождении **LCA** ( _Lowest Common Ancestor_ ) сводится к задаче **RMQ** ( _Range minimum query_ ), или по-русски, минимум на отрезке. Более подробно про эт...
Асимптотика была бы `O(1)` на запрос (если использовать DSU со всеми
эвристиками, то можно сказать
158.
Динамическое sos dp с удалением и вставкой элементов за O(2^(k/2)) Я придумал это около двух месяцев назад (хотя это скорее всего хорошо известная структура), когда пытался решить задачу, которую я и придумал. Я не видел ни одного блога на эту тему, поэтому решил написать свой.
Основная идея здесь это применение meet-in-the-middle.
В наивном алгоритме, для вставки, или удаления, мы просто создадим вектор размера $2^k$, где $dp_{mask}$ означает количество элементов с данным значением, и просто сделаем $dp_{mask}++$ (либо $dp_{mask}--$), поэтому это зайтем $O(1)$ времени, и чтобы сделать запрос просто пробежимся по всем подмаскам of за $O(2^k)$. Довольно очевидно, что мы можем это сбалансировать.
Разделим биты пополам, для вставки, или удаления, мы пробежимся по всем надмаскам первой половины бит (назовем $maskup$) и добавим сюда вторую половину (назовем $masksec$), то есть сделаем $dp_{maskup+masksec}++$ (либо, если хотим удалить, отнимем единицу).
Чтобы сделать запрос, сделаем наоборот: первая половина зафиксирована, и мы пробежимся по вс...
Чтобы сделать запрос, сделаем наоборот: первая половина зафиксирована, и мы
пробежимся по всем
159.
Codeforces WatchR 1.9.0 (Doyle): Аутентификация Привет, Codeforces! Начиная с прошлого ноября мы работали над множеством нового функционала для нашего приложения Codeforces WatchR, обновление которого наконец-то доступно [App Store](https://apps.apple.com/us/app/codeforces-watchr-contests/id1495591299) и [Google Play](https://play.google.com/store/apps/details?id=com.bogdan.codeforceswatcher).
Бизнес-логика переехала на сервер
-----------------------------------
Мы добавили серверную логику еще несколько майлстоунов назад, но использовалась она только для функционала "Новостей". Другие части приложения работали с [Codeforces API](https://codeforces.com/apiHelp) напрямую из мобильных приложений, что доставляло немало хлопот и негативно влияло на стабильность работы приложения.
В частности, подтягивание обновлений рейтинга требовало множества запросов (один на пользователя) каждый раз когда вы пытались обновить список. Такой подход плохо масштабировал...
160.
Codeforces Beta Round #30. Разбор E <h1>Разбор задачи "E. Хитрый и умный пароль"</h1><h3>Общая схема решения</h3><p>Общая схема авторского решения следующая. Переберём позицию $pos$ центра средней части $middle$ ответа (той, которая является палиндромом). Дальше возьмём в качестве $middle$ максимальный подпалиндром, имеющий середину ровно в позиции $pos$. После этого надо взять в качестве $prefix$ и $suffix$ такие максимальные по длине строки, что они удовлетворяют всем условиям задачи, и при этом не пересекаются с выбранной серединой.</p><p>Выполнив эту процедуру для каждой позиции $pos$ и выбрав среди всех найденных ответов наилучший, - получим ответ на задачу.</p><h3>Реализация</h3><p>Фактически, задача состоит из двух подзадач:</p><p>Во-первых, определение максимальной длины палиндрома, имеющего центр в заданной позиции. Это делается за $O(n)$ алгоритмом, описанным <a href="http://e-maxx.ru/algo/palindromes_count">у меня на сайте</a>. Иначе это можно делать с помощью бинпоиска и, например, хешей: переберём бинарным п...
заранее ответы на всевозможные запросы - тогда ответ на запрос будет за
$O(1)$).
161.
Codeforces Round #857 Editorial [problem:1802A]
------------------
Автор: [user:Aleks5d,2023-03-13], разработчик: [user:vaaven,2023-03-13]
<spoiler summary="Решение">
Давайте покажем конструкцию, которая максимизирует количество лайков. Нам нужно сначала оставить все лайки, которые мы можем поставить, а только потом убирать их.
Для того, чтобы минимизировать количество лайков, нам нужно убирать лайк (если мы можем) сразу после того как мы его поставили.
Приведенный ниже код реализует эти конструкции.
</spoiler>
<spoiler summary="Код">
~~~~~
#include "bits/stdc++.h"
using namespace std;
void solve() {
int n;
cin >> n;
int likes = 0, dislikes = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > 0) likes++;
else dislikes++;
}
for (int i = 1; i <= n; ++i) {
if (i <= likes) cout << i << ' ';
else cout << likes * 2 - i << ' ';
}
cout << '\n';
for (int i = 1; i <= n; ++i) {
if (i...
которого записан диапазон цен для этой вершины. Запрос это пара путей равной
длины, цены на $i$-ых
162.
Codeforces Round #852 Editorial [problem:1793A] придумал и подготовил [user:Ormlis,2023-02-12]
[problem:1793B] придумал и подготовил [user:TheEvilBird,2023-02-12]
[problem:1793C] придумал [user:fedoseev.timofey,2023-02-12], а подготовил [user:vaaven,2023-02-12]
[problem:1793D] придумал и подготовил [user:Gornak40,2023-02-12]
[problem:1793E] придумал и подготовил [user:Tikhon228,2023-02-12]
[problem:1793F] придумал [user:Tikhon228,2023-02-12], а подготовил [user:vaaven,2023-02-12]
[problem:1793A]
------------------
Пусть $n = (m + 1) \cdot q + r$.
Заметим, что акцией выгодно пользоваться если $a \cdot m \leq b \cdot (m + 1)$. В таком случае $q$ раз купим картошку по акции. Оставшуюся картошку (или всю, если акция не выгодна) можно купить по цене $\min(a, b)$ за килограмм.
Тогда ответ: $$q \cdot \min(a \cdot m, b \cdot (m + 1)) + r \cdot \min(a, b)$$
Асимптотика решения: $\mathcal{O}(1)$
<spoiler summary="Code">
~~~~~
t = int(input())
for i in range(t):
a, b = map(int, inpu...
Tutorial of Codeforces Round 852 (Div. 2)
163.
Разбор контеста (нерейтингового) по случаю окончания учебного года и экзаменов Всем привет! А вот и разбор контеста!
[Вот анонс контеста](https://codeforces.com/blog/entry/78415)
[Задача А — Ромка и калькулятор](https://codeforces.com/gym/282524/problem/A)
<spoiler summary="Разбор">
Хочу сделать несколько замечаний по задаче. Вообще здесь не должны заходить long long, но я забыл в генераторе после проверки поставить обратно 10^18. Второе замечание такое: заметил, что у многих полетели задачи из-за того, что они просто выводили trunk(ans). Но требовалось вывести целое число, а trunk возвращает double, поэтому большие числа выводились у многих в экспоненциальной форме, что неверно. Обработка первого, второго и третьего запросов должна быть ясна, запрос четвёртого типа я пояснил. Многие писали, что не описано деление на 0. Но в условии гарантируется существование ответа Для запроса 5-го типа я забыл написать, что a >= 0 && b > 0. А так задача довольно простая, если писать её на Python или с помощью [int128].(https://codeforces.com/blog/entry/75004) ...
164.
Дерево Фенвика: инициализация за O(N) Привет, CodeForces.
Недавно решил поближе познакомиться с такой структурой данных как дерево Фенвика или binary indexed tree.
_В данной статье я буду рассматривать дерево Фенвика для суммы, но все написанное легко обобщается на случай любой ассоциативной, коммутативной и обратимой операции._
<spoiler summary="Немного реализации">
Я буду использовать 0-индексированное дерево Фенвика на векторах (практически так, как это показано на [e-maxx.ru](http://e-maxx.ru/algo/fenwick_tree))
~~~~~
vector<int> fenwick;
void init_empty(int size_) {
fenwick.assign(size_, 0);
}
int sum(int r) {
int res = 0;
while (r >= 0) {
res += fenwick[r];
r = (r & (r+1)) - 1;
}
return res;
}
int sum(int l, int r) {
return sum(r) - sum(l-1);
}
void inc(int i, int delta) {
while (i < fenwick.size()) {
fenwick[i] += delta;
i |= i+1;
}
}
~~~~~
</spoiler>
Прочитав статьи о нем на [e-maxx.ru](http://e-ma...
165.
Разбор задач VK Cup 2015 — Квалификация 1 ## [problem:522A]
Для решения этой задачи надо было проитерироваться по записям о репостах и поддерживать для каждого пользователя длину цепочки, которая заканчивается в нем. Здесь удобно воспользоваться ассоциативным массивом из строки (имени пользователя) в целое число (длину цепочки). Например, для С++ такой структурой данных будет просто map<string,int>. Назовем такую структуру `chainLengths`, тогда при обработки строки вида <<`a reposted b`>> надо просто выполнить присвоение `chainLengths[a] = chainLengths[b] + 1`. В качестве ответа надо вывести максимальное из значений `chainLengths`, что можно подсчитывать на лету.
Пара тонкостей: в начале надо занести `chainLengths["polycarp"] = 1;`, а всюду при работе со строками приводить их к нижнему регистру (или верхнему), чтобы сделать сравнение строк нечувствительным к регистру букв.
Пример такого решения: [submission:10209456].
## [problem:522B]
В этой задаче для каждого $i$ фактически надо было найти:
* $W_i$, равное ...
166.
Простой метод rmq O(n)/O(1) и его улучшенная версия, поддерживающая изменения(с
другой асимптотикой)
Простой метод rmq O(n)/O(1) и его улучшенная версия, поддерживающая изменения(с другой асимптотикой) **RMQ $O(n)/O(1)$**
<spoiler summary="Задача">
Дан массив $a$ из $n$ чисел от $1$ до $10^9$.
Нужно уметь отвечать на запрос минимум на отрезке с $l$ по $r$ за $O(1)$ в онлайне и $O(n)$ предподсчета.
</spoiler>
Для удобства будем считать, что нумерация массива с нуля.
Разобьем наш массив на блоки по $\lceil\log_{2}(n)\rceil$ чисел. Для удобства обозначим $bl = \lceil\log_{2}(n)\rceil$. В первом блоке числа с $a_{0}$ до $a_{bl - 1}$, во втором с $a_{bl}$ до $a_{2 * bl - 1}$ и так далее, в последнем блоке может быть меньше $bl$ чисел.
Таким образом, мы получили $\lceil\frac{n}{bl}\rceil$ блоков. Научимся находить минимум для отрезка, находящегося целиком внутри блока.
Будем рассматривать блоки независимо, в каждом блоке пойдем слева направо и будем поддерживать стек минимумов. Для каждой граинцы $r$ запомним стек минимумов с начала блока, в котором находится $r$, заканчивая $r$. Будем запоминать стек минимумов, как маску нулей и единиц, в $iм$ бите будет стоять $1$, если...
Рассмотрим запрос минимума на отрезке: Если границы в одном блоке на самом
длинном уровне, то, Рассмотрим запрос обновления: У нас изменится стек минимумов в одном блоке на
самом длиннов уровне
167.
Разбор задач Codeforces Round #291 (Div. 2) [problem:514A]
--------------
**Автор:** [user:Rebryk,2015-02-15]
Очевидно, что все цифры, которые больше 4, нужно инвертировать. Кроме цифры 9, если она первая цифра числа.
**Асимптотика:** $\mathcal{O}(\text{длина числа})$
[problem:514B]
--------------
**Автор:** [user:Antoniuk,2015-02-15]
Переберем точки, в которых находятся солдаты. Если в данной точке солдаты еще не убиты, то сделаем выстрел и уничтожим всех солдатов, находящихся на прямой, проходящей через месторасположение пушки и данную точку.
Точки $(x_1, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$ лежат на одной прямой, если $(x_2 - x_1)(y_3 - y_1) = (x_3 - x_1)(y_2 - y_1)$.
**Асимптотика:** $\mathcal{O}(N^2)$
[problem:514C]
--------------
**Автор:** [user:Rebryk,2015-02-15]
При добавлении строки в множество, посчитаем от нее полиномиальный хэш и добавим его в массив. Затем этот массив отсортируем.
Теперь для ответа на запрос будем пробовать менять каждый символ в строке и с помощью бинарного поиска про...
. Затем этот массив отсортируем. Теперь для ответа на запрос будем пробовать
менять каждый символ в
Tutorial of Codeforces Round 291 (Div. 2)
168.
Codeforces Round #329 (Editorial) [problem:593A]
------------------
Для каждой буквы будем поддерживать суммарную длину слов ($cnt1_{c_{i}}$), в которых встречается она одна, а для каждой пары букв будем поддерживать суммарную длину слов, в которых встречаются только они($cnt2_{c_{i}, c_{j}}$).
Для каждой строки определим количество различных букв в ней.
Если она одна, то добавим к этой букве длину этого слова.
Если их две, то добавим к этой паре букв длину этого слова.
Переберем пару букв, которая будет ответом. Для пары букв $c_{i}, c_{j}$ ответом будет $cnt1_{c_{i}} + cnt1_{c_{j}} + cnt2_{c_{i}, c_{j}}$. Среди всех таких пар найдем максимум и выведем его.
Решение за O(суммарная длина всех строк + 26 * 26)
[problem:593B]
------------------
Заметим, что если $i$-я прямая пересекаются с $j$-й в данной полосе, а при $x = x_{1}$ $i$-я прямая находится выше, то при $x = x_{2}$ выше окажется $j$-я прямая.
То есть отсортируем прямые по координате $y$ при $x = x_{1} + eps$, и при $x = x_{2} - eps$.
...
Итоговое время работы $O(log x)$ на запрос первого типа и $O(1)$ в среднем на
запрос второго типа.
Tutorial of Codeforces Round 329 (Div. 2)
169.
IOI 2014: первый тур Примерно через 15 минут по плану должен начаться первый тур IOI 2014.
[Результаты](http://live.ioi2014.org/Ranking.html)
[Результаты от снарка](http://ioi.snarknews.info/index.cgi?data=2014/day1pre&class=ioi2014&year=2014)
[Видеотрансляция](http://new.livestream.com/accounts/9099718/events/3149562)
[Таблица по странам от Снарка](http://ioi.snarknews.info/index.cgi?data=2014/day1cou&class=ioi2014&year=2014)
С началом тура я постараюсь следить за результатами российской (и других русскоговорящих) команд,
верхом таблицы, а также немного напишу про задачи.
0:03 Судя по таблице контест начался по расписанию. Чтобы быть в этом уверенным, я дождусь появления первых баллов, после чего выложу условия.
0:04 У них что-то кешируется слишком злобно, так что если у вас все еще "подождите" Ctrl+F5 должно помочь.
0:12 На IOI-Conference подтвердили, что тур начался по расписанию.
0:13 Первые баллы! 42 от ~stevenkplus,2014-07-15
0:17 Первые баллы по rail. 8 от Conor Griff...
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Apr/24/2024 00:52:56 (j2).
Desktop version, switch to mobile version.
Supported by
