**Привет.**↵
↵
Меня зовут Ватолин Александр. Я несколько лет занимаюсь обучением людей в разных областях IT — кому-то заходил с алгоритмами, кому-то системный дизайн, кому-то прикладное программирование. Последнее время стало всё больше ML. И в какой-то момент поймал себя на ощущении, которое долго не мог сформулировать: накопилось.↵
↵
Накопились заметки, которые я писал для одного ученика. Накопились объяснения, которые я повторял по двадцать раз — и каждый раз чуть точнее. Накопились задачи, которые я отбирал руками, потому что в стандартных подборках они либо слишком скучные, либо слишком жестокие. И вот это всё хочется наконец достать из черновиков и отдать наружу — людям, которым это пригодится.↵
↵
Так появилась идея серии. Начну со спортивного программирования — потому что это та область, где у меня больше всего материала и где, как мне кажется, в рунете до сих пор не хватает спокойных разборов без академического надрыва или излишне завышенных ожиданий. На Codeforces в целом много чего есть, так что мои посты — скорее сублимация моих мыслей и мнений и не претендуют на истину в последней инстанции.↵
↵
Сегодняшний пост — обзорный: про что вообще CP (спортивное программирование), зачем оно, и как будет устроена серия дальше.↵
_Серия постов ориентирована больше на новичков, но я всегда буду рад критике и предложениям от ветеранов._ ↵
↵
## Что такое спортивное программирование↵
↵
Если в одно предложение: **дана хорошо известная задача из Computer Science — реши её как можно быстрее**.↵
_Это прекрасное описание я приведу из книги CP4, которое собственно меня натолкнуло на мысли об этой серии постов_↵
↵
В этой фразе три важных слова, и про каждое стоит сказать отдельно.↵
↵
**«Хорошо известная»** — значит, задача уже решена. Это не research, никто не ждёт, что вы откроете новый алгоритм. Автор знает решение, и сотни людей до вас его находили. Ваша работа — поднять свой уровень до того, чтобы *узнать* задачу и применить нужный инструмент.↵
↵
**«Решить»** — значит, написать код, который выдаст тот же ответ, что и у автора, на его *скрытых* тестах, в рамках лимита по времени. Скрытые тесты- отдельная важная штука: они заставляют самому продумывать краевые случаи, а не вычитывать их из условия.↵
↵
**«Как можно быстрее»** — это спортивная часть. Без неё CP не было бы CP. Да и решить можно как просто быстрее своего соперника, так и иногда твое решение может оказаться быстрее. Об этом подробнее как-то потом.↵
↵
## Выливается это примерно в это↵
↵
Возьмём простую задачу. Есть $N$ стойл на прямой в точках с координатами $x_1 < x_2 < \dots < x_N$. Нужно расставить в них $C$ коров так, чтобы **минимальное расстояние между любыми двумя коровами было максимально возможным**. Никто не любит быть в тесноте, даже коровы.↵
↵
А теперь смотрите, как с ней справляются разные люди.↵
↵
**Новичок А** видит «расставить так, чтобы максимизировать минимум» и пробует перебор: какие $C$ из $N$ стойл выбрать. Получается $C$ из $N$ — при $N = 10^5$ это никогда не досчитается. **Time Limit Exceeded**.↵
↵
**Новичок B** пробует жадность: ставим первую корову в первое стойло, дальше — каждый раз в ближайшее свободное, где помещается. Не работает — **Wrong Answer**. Жадность здесь нечестная: оптимальный ответ зависит от того, *какое* минимальное расстояние мы целимся обеспечить, а оно заранее неизвестно.↵
↵
**Опытный C** говорит: Ага. Мы не знаем, какое расстояние $d$ достижимо, но если зафиксировать $d$, то проверка становится тривиальной — жадно ставим коров слева направо, каждую следующую не ближе $d$ от предыдущей, считаем, поместились ли все $C$. И заметьте: если $d$ работает, то любое меньшее $d$ тоже работает. То есть ответ монотонен по $d$. Значит — бинпоиск по ответу.↵
Пишет за полчаса, получает **Accepted**.↵
↵
**Спортсмен D** видит фразу максимизировать минимум и *сразу* пишет бинпоиск по ответу. Десять минут. Эта связка у него рефлекторная.↵
↵
Разница между B и D — не талант. Разница в том, что D однажды узнал паттерн максимизируй минимум / минимизируй максимум — попробуй бинпоиск по ответу, увидел его в десятке задач и теперь распознаёт автоматически. Этому можно и нужно научиться. Собственно, в этом весь смысл тренировок. К слову, как мне кажется эти 4 уровня в целом сочетаются с 4 дивизионами, что мы видим на CF.↵
↵
## Зачем мне это (и, возможно, вам)↵
↵
Скажу важное: **CP — не самоцель**. Никто не платит зарплату за решённые задачи на Codeforces или других платформах.↵
↵
CP — это средство. Средство стать инженером, который:↵
↵
- быстро узнаёт знакомые задачи в незнакомой обёртке;↵
- держит в голове готовый инструментарий и умеет его собирать под задачу;↵
- автоматически думает о краевых случаях;↵
- спокойно отлаживает под давлением и не разваливается, когда всё идет не по плану.↵
↵
Эти навыки потом окупаются везде — от собеседований до системного дизайна, от research до обычной продакшен-разработки. Не зря IOI и ICPC изначально задумывались как способ воспитать разностороннего инженера, а не как самостоятельная дисциплина.↵
↵
## Как будет устроена серия↵
↵
План такой:↵
↵
- **Каждый пост — одна тема.** Попробую начать с базовых тем, а потом уйдем в дебри. Может чего необычного из этого и выйдет.↵
- Посты в целом будут про то, как до алгоритмов дойти, как их запомнить, какие есть признаки для их использования.↵
- **В конце — подборка задач** на Codeforces и на моём сайте: от базовой интерпретации алгоритма до сложных задачек.↵
- Разборы всех задач вы уже найдете и без меня. На CF разборы обычно есть у большинства задач. На моем сайтике я тоже разборы публикую. Ну и там в основном будут задачи попроще.↵
↵
Если откликается — оставайтесь. В следующем посте начнём с самой базовой, но от не менее полезной техники полного перебора. Постараюсь выпустить его поскорее.↵
↵
До встречи. Буду рад вашим задачам, вопросам и пожеланиям в комментариях.↵
↵
*Все статьи серии найдёте по тегуHello there.**↵
↵
My name is Alexander Vatolin. For several years I've been teaching people across different areas of IT — some came for algorithms, some for system design, some for applied programming. Lately it's been more and more ML. And at some point I caught myself with a feeling I couldn't put into words for a long time: it's piled up.↵
↵
Piled up are the notes I once wrote for a single student. Piled up are the explanations I've repeated twenty times — each time a little sharper. Piled up are the problems I picked by hand, because in the standard sets they're either too dull or too brutal. And all of this I finally want to pull out of my drafts and put out there — for the people it might help.↵
↵
That's how the idea of this series came about. I'll start with competitive programming — because that's the area where I have the most material, and where, as it seems to me, the Russian-speaking internet still lacks calm walkthroughs without academic pomp or wildly inflated expectations. There's plenty on Codeforces already, so my posts are more of a sublimation of my own thoughts and opinions and don't claim to be the final word.↵
↵
Today's post is an overview: what CP (competitive programming) is about, why anyone does it, and how the series will be laid out further on.↵
_The series is aimed more at beginners, but I'll always be glad to hear criticism and suggestions from veterans._↵
↵
## What competitive programming is↵
↵
In one sentence: **you're given a well-known problem from Computer Science — solve it as fast as you can**.↵
_This wonderful description I borrow from the book CP4, which, in fact, is what nudged me toward this series in the first place._↵
↵
There are three important words in that sentence, and each deserves its own paragraph.↵
↵
**"Well-known"** — means the problem has already been solved. This isn't research; nobody expects you to invent a new algorithm. The author knows the solution, and hundreds of people before you have found it. Your job is to lift your level enough to *recognize* the problem and reach for the right tool.↵
↵
**"Solve"** — means writing code that produces the same answer as the author's, on their *hidden* tests, within the time limit. Hidden tests are a separate important thing: they force you to think through edge cases yourself, rather than reading them off the statement.↵
↵
**"As fast as you can"** — that's the sporting part. Without it, CP wouldn't be CP. And "faster" can mean both faster than your opponent and, sometimes, that your solution itself runs faster. More on that some other time.↵
↵
## What this looks like in practice↵
↵
Let's take a simple problem. There are $N$ stalls on a line at coordinates $x_1 < x_2 < \dots < x_N$. You need to place $C$ cows in them so that **the minimum distance between any two cows is as large as possible**. Nobody likes being cramped — not even cows.↵
↵
Now watch how different people approach this.↵
↵
**Beginner A** sees "place them to maximize the minimum" and tries brute force: which $C$ out of $N$ stalls to pick. That's $C$-choose-$N$ — at $N = 10^5$ it'll never finish. **Time Limit Exceeded**.↵
↵
**Beginner B** tries greedy: put the first cow in the first stall, then each next cow in the closest free stall where it fits. Doesn't work — **Wrong Answer**. The greedy here is dishonest: the optimal answer depends on *which* minimum distance you're aiming to guarantee, and you don't know it in advance.↵
↵
**Experienced C** says: Aha. We don't know which distance $d$ is achievable, but if we fix $d$, the check becomes trivial — greedily place cows left to right, each next one no closer than $d$ from the previous, and count whether all $C$ fit. And notice: if $d$ works, then any smaller $d$ also works. So the answer is monotone in $d$. Which means — binary search on the answer.↵
Writes it in half an hour, gets **Accepted**.↵
↵
**Sportsman D** sees "maximize the minimum" and *immediately* writes binary search on the answer. Ten minutes. That connection is a reflex for them.↵
↵
The difference between B and D isn't talent. The difference is that D once learned the pattern "maximize the minimum / minimize the maximum — try binary search on the answer," saw it in a dozen problems, and now recognizes it on autopilot. This can — and should — be learned. That, in essence, is what training is for. By the way, it seems to me these four levels line up rather nicely with the four divisions we see on CF.↵
↵
## Why I'm doing this (and maybe you should too)↵
↵
Important note: **CP isn't an end in itself**. Nobody pays you a salary for solved problems on Codeforces or any other platform.↵
↵
CP is a means. A means of becoming an engineer who:↵
↵
- quickly recognizes familiar problems in unfamiliar wrappers;↵
- keeps a ready toolkit in their head and can assemble it for the problem at hand;↵
- automatically thinks about edge cases;↵
- debugs calmly under pressure and doesn't fall apart when nothing goes according to plan.↵
↵
These skills pay off everywhere afterwards — from interviews to system design, from research to ordinary production work. It's no accident that IOI and ICPC were originally conceived as a way to cultivate well-rounded engineers, not as a self-contained discipline.↵
↵
## How the series will be laid out↵
↵
The plan goes like this:↵
↵
- **One post — one topic.** I'll try to start with the basics, then we'll wander into deeper territory. Maybe something unusual will come of it.↵
- The posts will mostly be about how to *arrive* at the algorithms, how to remember them, what cues hint that they're the right tool.↵
- **At the end — a problem set** on Codeforces and on my own site: from a baseline implementation of the algorithm to something properly tricky.↵
- Solutions for all the problems you can find without me. On CF most problems have editorials. On my little site I also publish solutions. And there the problems will mostly be on the easier side.↵
↵
If this resonates — stick around. The next post will start with the most basic but no less useful technique: brute force. I'll try to get it out soon.↵
↵
See you. I'll be glad to receive your problems, questions, and suggestions in the comments.↵
↵
*All posts in the series are tagged* **#EDU-M**.
↵
Меня зовут Ватолин Александр. Я несколько лет занимаюсь обучением людей в разных областях IT — кому-то заходил с алгоритмами, кому-то системный дизайн, кому-то прикладное программирование. Последнее время стало всё больше ML. И в какой-то момент поймал себя на ощущении, которое долго не мог сформулировать: накопилось.↵
↵
Накопились заметки, которые я писал для одного ученика. Накопились объяснения, которые я повторял по двадцать раз — и каждый раз чуть точнее. Накопились задачи, которые я отбирал руками, потому что в стандартных подборках они либо слишком скучные, либо слишком жестокие. И вот это всё хочется наконец достать из черновиков и отдать наружу — людям, которым это пригодится.↵
↵
Так появилась идея серии. Начну со спортивного программирования — потому что это та область, где у меня больше всего материала и где, как мне кажется, в рунете до сих пор не хватает спокойных разборов без академического надрыва или излишне завышенных ожиданий. На Codeforces в целом много чего есть, так что мои посты — скорее сублимация моих мыслей и мнений и не претендуют на истину в последней инстанции.↵
↵
Сегодняшний пост — обзорный: про что вообще CP (спортивное программирование), зачем оно, и как будет устроена серия дальше.↵
_Серия постов ориентирована больше на новичков, но я всегда буду рад критике и предложениям от ветеранов._ ↵
↵
## Что такое спортивное программирование↵
↵
Если в одно предложение: **дана хорошо известная задача из Computer Science — реши её как можно быстрее**.↵
_Это прекрасное описание я приведу из книги CP4, которое собственно меня натолкнуло на мысли об этой серии постов_↵
↵
В этой фразе три важных слова, и про каждое стоит сказать отдельно.↵
↵
**«Хорошо известная»** — значит, задача уже решена. Это не research, никто не ждёт, что вы откроете новый алгоритм. Автор знает решение, и сотни людей до вас его находили. Ваша работа — поднять свой уровень до того, чтобы *узнать* задачу и применить нужный инструмент.↵
↵
**«Решить»** — значит, написать код, который выдаст тот же ответ, что и у автора, на его *скрытых* тестах, в рамках лимита по времени. Скрытые тесты- отдельная важная штука: они заставляют самому продумывать краевые случаи, а не вычитывать их из условия.↵
↵
**«Как можно быстрее»** — это спортивная часть. Без неё CP не было бы CP. Да и решить можно как просто быстрее своего соперника, так и иногда твое решение может оказаться быстрее. Об этом подробнее как-то потом.↵
↵
## Выливается это примерно в это↵
↵
Возьмём простую задачу. Есть $N$ стойл на прямой в точках с координатами $x_1 < x_2 < \dots < x_N$. Нужно расставить в них $C$ коров так, чтобы **минимальное расстояние между любыми двумя коровами было максимально возможным**. Никто не любит быть в тесноте, даже коровы.↵
↵
А теперь смотрите, как с ней справляются разные люди.↵
↵
**Новичок А** видит «расставить так, чтобы максимизировать минимум» и пробует перебор: какие $C$ из $N$ стойл выбрать. Получается $C$ из $N$ — при $N = 10^5$ это никогда не досчитается. **Time Limit Exceeded**.↵
↵
**Новичок B** пробует жадность: ставим первую корову в первое стойло, дальше — каждый раз в ближайшее свободное, где помещается. Не работает — **Wrong Answer**. Жадность здесь нечестная: оптимальный ответ зависит от того, *какое* минимальное расстояние мы целимся обеспечить, а оно заранее неизвестно.↵
↵
**Опытный C** говорит: Ага. Мы не знаем, какое расстояние $d$ достижимо, но если зафиксировать $d$, то проверка становится тривиальной — жадно ставим коров слева направо, каждую следующую не ближе $d$ от предыдущей, считаем, поместились ли все $C$. И заметьте: если $d$ работает, то любое меньшее $d$ тоже работает. То есть ответ монотонен по $d$. Значит — бинпоиск по ответу.↵
Пишет за полчаса, получает **Accepted**.↵
↵
**Спортсмен D** видит фразу максимизировать минимум и *сразу* пишет бинпоиск по ответу. Десять минут. Эта связка у него рефлекторная.↵
↵
Разница между B и D — не талант. Разница в том, что D однажды узнал паттерн максимизируй минимум / минимизируй максимум — попробуй бинпоиск по ответу, увидел его в десятке задач и теперь распознаёт автоматически. Этому можно и нужно научиться. Собственно, в этом весь смысл тренировок. К слову, как мне кажется эти 4 уровня в целом сочетаются с 4 дивизионами, что мы видим на CF.↵
↵
## Зачем мне это (и, возможно, вам)↵
↵
Скажу важное: **CP — не самоцель**. Никто не платит зарплату за решённые задачи на Codeforces или других платформах.↵
↵
CP — это средство. Средство стать инженером, который:↵
↵
- быстро узнаёт знакомые задачи в незнакомой обёртке;↵
- держит в голове готовый инструментарий и умеет его собирать под задачу;↵
- автоматически думает о краевых случаях;↵
- спокойно отлаживает под давлением и не разваливается, когда всё идет не по плану.↵
↵
Эти навыки потом окупаются везде — от собеседований до системного дизайна, от research до обычной продакшен-разработки. Не зря IOI и ICPC изначально задумывались как способ воспитать разностороннего инженера, а не как самостоятельная дисциплина.↵
↵
## Как будет устроена серия↵
↵
План такой:↵
↵
- **Каждый пост — одна тема.** Попробую начать с базовых тем, а потом уйдем в дебри. Может чего необычного из этого и выйдет.↵
- Посты в целом будут про то, как до алгоритмов дойти, как их запомнить, какие есть признаки для их использования.↵
- **В конце — подборка задач** на Codeforces и на моём сайте: от базовой интерпретации алгоритма до сложных задачек.↵
- Разборы всех задач вы уже найдете и без меня. На CF разборы обычно есть у большинства задач. На моем сайтике я тоже разборы публикую. Ну и там в основном будут задачи попроще.↵
↵
Если откликается — оставайтесь. В следующем посте начнём с самой базовой, но от не менее полезной техники полного перебора. Постараюсь выпустить его поскорее.↵
↵
До встречи. Буду рад вашим задачам, вопросам и пожеланиям в комментариях.↵
↵
*Все статьи серии найдёте по тегу
↵
My name is Alexander Vatolin. For several years I've been teaching people across different areas of IT — some came for algorithms, some for system design, some for applied programming. Lately it's been more and more ML. And at some point I caught myself with a feeling I couldn't put into words for a long time: it's piled up.↵
↵
Piled up are the notes I once wrote for a single student. Piled up are the explanations I've repeated twenty times — each time a little sharper. Piled up are the problems I picked by hand, because in the standard sets they're either too dull or too brutal. And all of this I finally want to pull out of my drafts and put out there — for the people it might help.↵
↵
That's how the idea of this series came about. I'll start with competitive programming — because that's the area where I have the most material, and where, as it seems to me, the Russian-speaking internet still lacks calm walkthroughs without academic pomp or wildly inflated expectations. There's plenty on Codeforces already, so my posts are more of a sublimation of my own thoughts and opinions and don't claim to be the final word.↵
↵
Today's post is an overview: what CP (competitive programming) is about, why anyone does it, and how the series will be laid out further on.↵
_The series is aimed more at beginners, but I'll always be glad to hear criticism and suggestions from veterans._↵
↵
## What competitive programming is↵
↵
In one sentence: **you're given a well-known problem from Computer Science — solve it as fast as you can**.↵
_This wonderful description I borrow from the book CP4, which, in fact, is what nudged me toward this series in the first place._↵
↵
There are three important words in that sentence, and each deserves its own paragraph.↵
↵
**"Well-known"** — means the problem has already been solved. This isn't research; nobody expects you to invent a new algorithm. The author knows the solution, and hundreds of people before you have found it. Your job is to lift your level enough to *recognize* the problem and reach for the right tool.↵
↵
**"Solve"** — means writing code that produces the same answer as the author's, on their *hidden* tests, within the time limit. Hidden tests are a separate important thing: they force you to think through edge cases yourself, rather than reading them off the statement.↵
↵
**"As fast as you can"** — that's the sporting part. Without it, CP wouldn't be CP. And "faster" can mean both faster than your opponent and, sometimes, that your solution itself runs faster. More on that some other time.↵
↵
## What this looks like in practice↵
↵
Let's take a simple problem. There are $N$ stalls on a line at coordinates $x_1 < x_2 < \dots < x_N$. You need to place $C$ cows in them so that **the minimum distance between any two cows is as large as possible**. Nobody likes being cramped — not even cows.↵
↵
Now watch how different people approach this.↵
↵
**Beginner A** sees "place them to maximize the minimum" and tries brute force: which $C$ out of $N$ stalls to pick. That's $C$-choose-$N$ — at $N = 10^5$ it'll never finish. **Time Limit Exceeded**.↵
↵
**Beginner B** tries greedy: put the first cow in the first stall, then each next cow in the closest free stall where it fits. Doesn't work — **Wrong Answer**. The greedy here is dishonest: the optimal answer depends on *which* minimum distance you're aiming to guarantee, and you don't know it in advance.↵
↵
**Experienced C** says: Aha. We don't know which distance $d$ is achievable, but if we fix $d$, the check becomes trivial — greedily place cows left to right, each next one no closer than $d$ from the previous, and count whether all $C$ fit. And notice: if $d$ works, then any smaller $d$ also works. So the answer is monotone in $d$. Which means — binary search on the answer.↵
Writes it in half an hour, gets **Accepted**.↵
↵
**Sportsman D** sees "maximize the minimum" and *immediately* writes binary search on the answer. Ten minutes. That connection is a reflex for them.↵
↵
The difference between B and D isn't talent. The difference is that D once learned the pattern "maximize the minimum / minimize the maximum — try binary search on the answer," saw it in a dozen problems, and now recognizes it on autopilot. This can — and should — be learned. That, in essence, is what training is for. By the way, it seems to me these four levels line up rather nicely with the four divisions we see on CF.↵
↵
## Why I'm doing this (and maybe you should too)↵
↵
Important note: **CP isn't an end in itself**. Nobody pays you a salary for solved problems on Codeforces or any other platform.↵
↵
CP is a means. A means of becoming an engineer who:↵
↵
- quickly recognizes familiar problems in unfamiliar wrappers;↵
- keeps a ready toolkit in their head and can assemble it for the problem at hand;↵
- automatically thinks about edge cases;↵
- debugs calmly under pressure and doesn't fall apart when nothing goes according to plan.↵
↵
These skills pay off everywhere afterwards — from interviews to system design, from research to ordinary production work. It's no accident that IOI and ICPC were originally conceived as a way to cultivate well-rounded engineers, not as a self-contained discipline.↵
↵
## How the series will be laid out↵
↵
The plan goes like this:↵
↵
- **One post — one topic.** I'll try to start with the basics, then we'll wander into deeper territory. Maybe something unusual will come of it.↵
- The posts will mostly be about how to *arrive* at the algorithms, how to remember them, what cues hint that they're the right tool.↵
- **At the end — a problem set** on Codeforces and on my own site: from a baseline implementation of the algorithm to something properly tricky.↵
- Solutions for all the problems you can find without me. On CF most problems have editorials. On my little site I also publish solutions. And there the problems will mostly be on the easier side.↵
↵
If this resonates — stick around. The next post will start with the most basic but no less useful technique: brute force. I'll try to get it out soon.↵
↵
See you. I'll be glad to receive your problems, questions, and suggestions in the comments.↵
↵
*All posts in the series are tagged* **#EDU-M**.
