В этом блоге я сделал тест, который поможет вам определить, оптимален ли ваш сетап или нет. Ниже я напишу список критериев, по которым я буду его оценивать и разбаловку. И в конце вы сможете узнать, к какой "группе людей" вы относитесь, прямо как в тестиках на персонажа из аниме в Вконтакте.

Я сюда включил практически всё, что мне пришло в голову, если я что-то забыл, предложите в комментариях. Но добавлять вещи как У меня есть интернет и На моей клавиатуре есть большая часть клавиш я не буду :)

Это несерьёзный блог, но если вы новичок, вы, может быть, найдёте для себя что-то новое. Но это всё равно никак не поможет вам поднять рейтинг, для этого нужно решать задачи.

Вы можете компилировать код перед посылкой

• $$$0$$$ баллов: Я не знаю, как компилировать код самостоятельно, и просто отправляю его на проверку
• $$$10$$$ баллов: Я умею запускать код до отправки

Я видел много школьников, которые отправляют посылки никогда не запуская. Даже в институте такие встречались. На последнем див 4 соревновании [73 страницы Compilation Error] в задаче А (https://codeforces.me/contest/2009/status/page/1?order=BY_JUDGED_DESC) Кажется, таких людей даже больше, чем я ожидал)

Если вы не умеете это делать, вам нужно этому научиться. Даже турист проверяет свои решения на сэмплах, иногда даже в простых задачах

Ваша среда работает стабильно и без лагов

• $$$0$$$ баллов: Моя среда постоянно падает и зависает
• $$$2$$$ балла: Моя среда иногда глючит и даже иногда падает.
• $$$4$$$ балла: Моя среда работает отлично и никогда не глючит

Когда я в школьные годы участвовал в олимпиадах, я постоянно мучался с предложенным компьютером. Он зависал, крашился, несколько раз мне даже давали поменять компьютер. Но я тогда ничего не знал и зачем-то пользовался вижлой на слабых машинах. Это очень неудобно и тратит много времени

Вы можете запускать свой код без интернета

• $$$0$$$ баллов: Я пользуюсь онлайн редактором и при падении интернета не могу запускать свой код
• $$$2$$$ балла: Всё установлено на моём компьютере, и отсутствие интернета никак не повлияет на то, могу ли я запускать свой код

Существуют такие онлайн компиляторы, которыми я совсем не рекомендую пользоваться. Зависеть от посторонних сайтов или от интернет провайдера — странная проблема, её лучше избегать

Вам может быть полезна подсветка синтаксиса, и вы ей пользуетесь

• $$$0$$$ баллов: Я не использую подсветку синтаксиса, но если бы я знал как её включить, я бы пользовался
• $$$2$$$ балла: Я использую подсветку синтаксиса
• $$$2$$$ балла: Я не использую подсветку синтаксиса, хотя знаю как её включить.

Если вы дальтоник, или вы, как мой батя, просто привыкли писать синими буквами на синем фоне, то подсветка кода разными цветами должна вам помочь, это облегчает его чтение.

Вы можете проверить, сколько секунд работала ваша программа

• $$$0$$$ баллов: Я не могу проверить, сколько секунд работала моя программа
• $$$1$$$ балл: Я могу проверить, сколько секунд работала моя программа, и мне для этого не нужно писать ничего нового в коде

Полагаться на то, что если на вашем компьютере работает решение < 1 секунды, то на проверяющих серверах произойдёт то же самое — нельзя. Но иметь возможность сравнить, быстрее ли работает ваше решение или нет после какого-нибудь фикса — бывает очень полезно.

Вы можете проверить, сколько памяти потребила ваша программа

• $$$0$$$ баллов: Я не могу проверить, сколько мегабайт использовала моя программа
• $$$1$$$ балл: Я легко могу проверить, сколько мегабайт использовала моя программа

Иногда сложно точно сказать, сколько памяти потребляет ваша программа на макс тесте, и бывает удобно запустить её самому и проверить это, а не тратить лишнюю одну посылку

Вам подсвечиваются ошибки во время написания кода (другими словами, вы используете Language Server)

• $$$0$$$ баллов: Когда я допускаю ошибку в синтаксисе, я это вижу только после компиляции/запуска программы
• $$$3$$$ балла: Когда я допускаю описку в коде, то это место подсвечивается, чтобы я сразу мог это исправить.

Если у вас не включено подсвечивание ошибок на ходу, то тогда вам нужно перезапускать код несколько раз, чтобы исправить такие ошибки как vctor<int> A;. Это тратит лишнее время

Ваш язык программирования легко решает все те задачи, до которых вы доходите в контесте

• $$$0$$$ баллов: Случалось, что я не смог решить задачи, и это произошло исключительно из-за языка программирования, который я выбрал
• $$$3$$$ балла: Мой язык программирования никогда не был причиной моего неуспеха

У некоторых задач слишком жёсткий тайм лимит, чтобы заливать её на медленных языках. Иногда это всё-таки можно сделать, но нужно приложить дополнительные усилия. Я не буду называть какие же языки нужно относить к "проблемным" — у меня нет такой компетенции, но если вы когда-нибудь сталкивались с похожими проблемами, вероятно, вы неоптимальны.

Вы можете быстро копировать к себе готовые алгоритмы/структуры данных

• $$$0$$$ баллов: Я никогда не копирую код и пишу всё руками / Я постоянно копирую код, который нахожу в интернете
• $$$2$$$ балла: У меня есть своя библиотека с алгоритмами/структурами данных, если мне что-то нужно, я ищу нужный алгоритм в ней и копирую его себе в код.
• $$$3$$$ балла: У меня есть своя библиотека и я могу горячими клавишами (сниппетами?) легко вставлять из неё в мой код, не покидая моего текстового редактора

Писать дерево отрезков руками 3 раза за контест — точно плохая идея. Скопировать его даже 1 раз всегда быстрее. Особенно если вы можете это сделать, не выходя из своего редактора. Часто приходится в алгоритмах что-то поменять, поэтому лучше пользоваться своей библиотекой, чтобы на 100% понимать, как всё работает, и если что быстро менять.

Вам не нужно копировать и вставлять тест каждый раз при запуске программы

• $$$0$$$ баллов: Каждый раз, когда я запускаю мой код, мне приходится скопировать тест из задачи и вставить его
• $$$2$$$ балла: Мой сетап позволяет запускать один и тот же тест несколько раз, не копируя его каждый раз.
• $$$3$$$ балла: Я могу вставить несколько тестов сразу, и по нажатию 1 кнопки запускать моё решение на всех из них

Копировать тест каждый раз при запуске программы — тратит очень много времени. Не стоит выполнять лишнюю работу. Также не стоит забывать, что иногда удобно иметь возможность вводить тест по частям, например в интерактивных задачах.

У вас удобное сообщения о ворнингах/ошибках

• $$$0$$$ баллов: Ворнинги/ошибки, которые я вижу после компиляции, мне не понятны и никогда мне не помогают
• $$$1$$$ балл: Ворнинги/ошибки, которые я вижу, мне иногда помогают, но я знаю что они могут быть лучше
• $$$2$$$ балла: Ворнинги/ошибки, которые я вижу, мне всегда помогают понять, что конкретно не так с моим кодом

Я использую C++ и после того, как я настроил флаги компиляции, стало намного удобней. Раньше сообщения мне совсем не помогали, а теперь я всегда смотрю на окошко ошибок. Я не смог настроить по-нормальному санитайзеры, так что знаю, что можно сделать ещё удобней. Если вам интересны такие вещи, советую почитать этот блог.

Использование авто-парсера контестов

• $$$0$$$ баллов: Мне приходится копировать тесты из задач руками
• $$$1$$$ балл: Я использую парсеры контестов, которые автоматически копируют тесты с контеста

Есть удобные тулы которые позволяют копировать тесты из контестов, очень удобно.

Ваш код легко прочитать, и как следствие легче взломать

• $$$0$$$ баллов: У меня большой темплейт (>50 строк), который делает мой код непонятным
• $$$1$$$ балл: У меня нет темплейта / он <= 50 строчек / он > 50 строчек, но я уверен, что он не мешает читаемости кода.

Из-за того, что на кодфосес всё ещё есть взломы, лучше делать код понятнее. Так как всегда лучше, если вас взломают на контесте и вы исправите ошибку, чем если вы упадёте на системных тестах. (Ну, кроме анти-хэш тестов и прочего)

У вас есть возможность запустить дебаггер (так, чтобы вам было удобно им пользоваться).

• $$$0$$$ баллов: У меня нет возможности запустить дебаггер / есть возможность, но им очень неудобно пользоваться
• $$$1$$$ балл: Если я захочу, я могу запустить удобный дебаггер, просто предпочитаю им никогда не пользоваться
• $$$1$$$ балл: Если я захочу, я могу запустить удобный дебаггер, и пользуюсь этим

Даже если вы не используете дебаггер, иметь возможность запустить его — точно плюс. Принтить в консольку не всегда быстрее.

Использование функций для принта в консоль для дебага

• $$$0$$$ баллов: Я использую стандартный cout или print для дебага.
• $$$1$$$ балл: Я использую продвинутые способы принтов для дебага, например использую макросы, чтобы выводить название переменных вместе с их значением, могу легко вывести содержимое массива одной строкой.
• $$$3$$$ балла: У меня есть большая библиотека для дебага, с помощью которой я даже могу выводить в удобном формате графы и структуры данных

У вас настроен удобный способ для стресс-тестирования

• $$$0$$$ баллов: Я не использую стресс тестирование и у меня нет сетапа, чтобы это делать.
• $$$2$$$ балла: Мой шаблон сделан так, чтобы я мог стресс тестировать свои решения
• $$$3$$$ балла: У меня есть скрипт, который позволяет мне стресс тестировать мои решения.

Если вы не слышали про стресс тестирование, то вы получаете 0 очков за этот пункт, но также вам стоит посмотреть это крутое видео, которое хорошо про это рассказывает.

Вы используете vim motions/ или другие продвинутые горячие клавиши для редактирования текста.

• $$$0$$$ баллов: Я не использую vim motions или другие похожие продвинутые горячие клавиши для редактирования текста
• $$$2$$$ балла: Я использую vim motions или другие похожие продвинутые горячие клавиши для редактирования текста.

Выделять тексты мышкой — точно не оптимально. Если вы убираете постоянно руки с клавиатуры, или вы перемещаетесь по тексту стрелочками, знайте, что есть способ лучше, vim motions очень вас ускорит.

WPM при печатаньи (Слов в минуту).

• $$$0$$$ баллов: У меня < 30 WPM
• $$$1$$$ балл: У меня >= 30 WPM
• $$$2$$$ балла: У меня >= 100 WPM

Если вы не знаете свою скорость, рекомендую затестить её тут. Я понимаю, что скорость печатанья это не совсем "сетап", но, мне кажется, это достаточно относится к делу, чтобы включить в блог.

Вообще я думаю, что скорость печатанья почти не влияет на результат, за исключением крайних случаев. Если вы печатаете уж слишком медленно, это может вам мешать. Также если вы очень очень быстрые, то тогда вы можете заработать много рейтинга в speedforces контестах.

Использование нескольких файлов для кода

• $$$0$$$ баллов: Я использую 1 файл, там я пишу все мои решения. Если мне нужно писать 2 решения параллельно, я сохраняю одно из них в блокнотике.
• $$$1$$$ балл: Я могу писать код в нескольких окнах параллельно.

Часто бывает, когда не дописав текущую задачу, вы начнёте писать другую. Если для этого вам нужно копировать куда-то ваш код, то тогда вы тратите лишнее время.

Использование класса для модульной арифметики

• $$$0$$$ баллов: Я не использую специальных классов для модульной арифметики и мой код выглядит примерно так d = ((a+b)%mod - c + mod)%mod * e % mod
• $$$1$$$ балл: Я использую специальный класс для модульной арифметики и мой код выглядит примерно так d = (a+b-c)*e

Сравнение результатов работы тестов и правильных ответов

• $$$0$$$ баллов: Когда я запускаю тесты, я вручную проверяю, совпадают ли они с ответами или нет .
• $$$1$$$ балл: Когда результат теста не совпадает с ожидаемым, в моём интерфейсе это подсвечивается

Когда в самплах большие тесты, сравнивать их вручную с правильными ответами похоже на игру "найди 5 отличий на картинке". Лучше автоматизировать этот процесс.

Считаем баллы

Теперь сложите все очки, которые вы получили, и найдите себя в табличке ниже, чтобы узнать какой же вы спортивный программист:

• 47-50) Либо у вас $$$\color{orange}{2300}+$$$ рейтинга и вы используете крутой удобный сетап, либо вы ~ $$$\color{green}{1200}$$$ и тратите слишком много времени на оптимизирование вашей среды, когда на самом деле вам просто нужно решать задачи
• 36-46) У вас неплохой сетап, бабушки называют вас "хакером".
• 20-35) В вашем сетапе есть проблемы, либо вы слишком близко к сердцу восприняли фразу "чтобы решать задачи, нужно просто решать задачи", либо вы панк $$$\color{black}{L}\color{red}{GM}$$$, которому без разницы, что использовать, чтобы выиграть контест.
• 13-19) Вы олимпиадный математик, и вы сидите на кодфорсес только потому, что математические олимпиады намного скучнее в онлайн формате.
• 0-12) Вы должны быть счастливее, чем остальные группы в этом списке, так как у вас реально есть способ повысить свой рейтинг, не решая задачи по программированию, потому что ваш сетап сравним с написанием контеста с кнопочного Нокиа.

Кстати я веду занятия по программированию, $$${1900}$$$ руб в час за индивидуальные, $$${600}$$$ рублей за групповые занятия (группы из 3х человек), бесплатное первое занятие. Напишите мне на Codeforces, если заинтересованы.

I noticed that sometimes I do some horrible things while solving easy problems. If you struggled with the first $$$2$$$ problems from the previous round, you might also have made some huge mistakes that should not happen.

The point of this blog: I will show you my terrible ways of approaching each of these problems and you will be able to see all of the stupid things that I did. Then I will show you the proper way to approach the tasks, and then you can think which approach is more similar to yours, and maybe it will help you to improve.

Problem A. Turtle and Good Strings

My approach during contest (terrible way)

• I open the statement, incorrectly rephrase it: you are given a string, you should divide it into several substrings, so in each substring the first and the last letters are different
• I think of a dp solution, then I sloppily prove that I should take no more than $$$2$$$ substrings. I submit my non-dp solution $$$\color{red}{WA 2}$$$.
• I look at my solution for a minute or two without being able to find the issue. Then I decide to write dp $$$\color{red}{WA 2}$$$.
• After solving $$$D1$$$ and $$$D2$$$, I return to the problem and find a bug in my dp solution: I fix it and resubmit $$$\color{red}{WA 2}$$$.
• I reread the statement. This time I understand it correctly. I feel relieved, make a quick fix to the first submission $$$\color{red}{WA 2}$$$
• I scan through my code. Somehow I figure out that the condition $$$ \texttt{s[0] } != \texttt{ s[n-1]} $$$ is the only condition that matters. I make a submission and finally get an $$$\color{green}{AC}$$$.

What went wrong

It is clear as day that everything I did here was horrifying.

• a) I did not read the statement properly and was solving a different problem
• b) I did not believe in the "proof" I came up with, it was just hopeful guessing with self-deception.
• c) The whole thing from start to finish is very messy. I did not think clearly

I think there are $$$2$$$ main reasons why all of it happened:

• 1) I was trying to be as fast as possible and was cutting corners
• 2) I was treating the problem as an "easy one", and was not properly solving it. I was hoping that my experience would be enough to solve the problem without putting any effort into it.

Good way to solve the problem

• I read the problem statement and correctly rephrase it: You are given string $$$S$$$. Divide it into $$$2$$$ or more substrings. If a substring starts with a letter $$$X$$$ , no substrings after it can end with this letter $$$X$$$
• I don't rush into thinking how to solve the problem. Instead, I try to understand how the statement "works". I make two simple observations: The first substring will always start with letter $$$s[0]$$$. The last substring will always end with $$$s[n-1]$$$.
• These observations help me to deduce that $$$if \texttt{ s[0] } == \texttt{ s[n-1] }$$$, the first substring will always start with the same letter as the last substring ends, so the answer will always be $$$\color{red}{NO}$$$. From this point I should only think about case $$$\texttt{ s[0] } != \texttt{ s[n-1] }$$$.
• If we take only $$$2$$$ substrings, the first one will always start with $$$s[0]$$$, and the second one will always end with $$$s[n-1]$$$. $$$\texttt{ s[0] } != \texttt{ s[n-1] }$$$ => no matter how we divide the string into $$$2$$$ substrings, it will always be good.
• We end up with the simplest solution: we output $$$\color{green}{YES}$$$ only in case when the first and the last letters of the string are different.

Problem B. Turtle and Piggy Are Playing a Game 2

My approach during contest (terrible way)

• The first thing I think is that both players should do operations that change $$$a_1$$$
• If the $$$a_1$$$ and $$$a_2$$$ are the same, it is impossible to change $$$a_1$$$. I get stuck here for several minutes
• I look through testcases, waste some additional minutes, and skip the problem.
• I return to it and reread the statement. Immediately after rereading it, I say: Oh, I got it! If $$$n$$$ is even, the last operation is $$$max()$$$ , otherwise it is $$$min()$$$
• I start writing code: I write if(n%2 == 0). Then I get stuck. I have no idea what to do from this point.
• In both cases the last operation would be on $$$a_1, a_2$$$ elements, I know what $$$a_1$$$ is equal to, I have to figure out $$$a_2$$$
• I look at the sample and notice it is roughly equal to the median value out of all elements except $$$a_1$$$
• I notice that my solution does not work because of the $$$a_1$$$ elements. I delete that part of the solution. I submit $$$\color{red}{WA 2}$$$
• I decide to return to idea "The first element is the only one that matters". I write this greedy solution $$$\color{red}{WA 2}$$$
• I make a guess that solution with median values is closer to the truth I decided to submit it without extra things $$$\color{green}{AC}$$$.

What went wrong

I think the paragraph above is so crazy that it is pretty difficult to point out specifically what was wrong(everything). Here is my attempt:

• 1) I have made a lot of incorrect assumptions, it seems like I did not bother to prove anything.
• 2) I was not thinking about the problem at all, I tried to guess my way through the whole process.

Good way to solve the problem

• Let's not rush, and instead of trying to solve the problem straight away, let's analyze what is happening in the problem.
• Let's look at the operation $$$a[i] = min(a[i], a[i+1])$$$.
• if $$$a[i] < a[i+1]$$$, then this operation is the same as just deleting $$$a[i+1]$$$
• if $$$a[i] \geq a[i+1]$$$, then this operation is the same as just deleting $$$a[i]$$$.
• So both players are basically deleting elements from the array each turn. Note that the first player cannot delete local maximum, and the second player cannot delete local minimum, but they never want to do that
• Let's rephrase the statement: We have an array $$$a$$$, $$$2$$$ players are deleting elements turn by turn. The first player wants the last remaining number to be maximum, the second player — minimum.
• It is obvious that the first player wants to delete small elements, and the second player wants to delete big elements. They take turns one after the other. In the end the remaining element will be somewhere in the middle.
• Let's be more specific. If there were $$$n$$$ elements in the array, then there were made $$$n-1$$$ operations before the array consisted of only 1 element. The first player will make $$$\lceil(n-1) / 2 \rceil$$$ operations and the second player $$$\lfloor (n-1) / 2 \rfloor$$$. If we sort the array in the non-decreasing order, the first $$$\lfloor (n-1) / 2 \rfloor$$$ and the last $$$\lceil (n-1) / 2 \rceil$$$ elements will be deleted. If we use 0-indexation, the remaining element will lie in $$$\lfloor (n-1) / 2 \rfloor$$$ index.

How to always solve problems the proper way

I think I can summarize the text above in the following way:

• In the bad solutions logical steps were huge, and most of the time they contained mistakes.
• In the good solutions I make small obvious steps that little by little get me closer to the correct solution.

You should always strive to solve problems the second way, but it is hard to be disciplined enough to do so. During the contests, there is always an incentive to rush and guess, because sometimes it leads to good performance. For me, the best way to deal with it is to record myself solving problems. It is quite boring to watch through it, but I make it interesting this way: I open a screencast of a highly rated participant, I watch him solve a problem in several minutes and then I ask myself "how on earth have I spent 20 minutes on the problem", and then I watch myself doing stupid things. And in the next contest I try to stop myself from repeating the same mistakes.

Shameless plug

If I somehow have not lost all of your respect by showing you my insane solutions to these problems and you still want me to teach you programming, send me a message on codeforces for more info, the first lesson is free (｡◕‿‿◕｡)

Consider rotating coordinate plane by $$$45$$$ degrees when you encounter Manhattan distance problem

Before I learned this trick, I had heard this phrase several times, but I never understood what it means. Turns out it is a pretty cool and easy trick. In this blog, I explain the trick in $$$2$$$ different ways, and show how to use it in practice on one of the recent problems. I tried to make this blog approachable, tested it on a $$$1200$$$~ rated participant

Let's look at this problem. I recommend thinking about it on your own for $$$10$$$-$$$15$$$ minutes.

Summary of the statement: you are given n = $$$2e5$$$ points. You have to find $$$3$$$ points, so that the Manhattan distance between each pair is d ( d is always even). Definition of Manhattan distance: $$$dist = |x_1 - x_2| + |y_1 - y_2|$$$

The solution above, in my opinion, is not trivial to think of neither to implement. But I think the trick in a way helps with both of the issues.

There are 2 ways to think about it, in a purely algebraic, or geometrical form. I suggest you read both of them.

The Algebra form:

It is a bit hard to work with the formula of Manhattan distance $$$dist = |x_1 - x_2| + |y_1 - y_2|$$$. It has 4 variables, and 2 summands of absolute values. Let's try to simplify it.

1) Let's start with introducing 2 new variables for convenience:

• $$$x_d = x_1-x_2$$$
• $$$y_d = y_1-y_2$$$
• $$$|x_1 - x_2| + |y_1 - y_2|$$$ <=> $$$|x_d| + |y_d|$$$

2) Let's divide our formula into 2 cases:

case where signs of $$$x_d$$$ and $$$y_d$$$ are the same (for this section I treat $$$0$$$ as positive number)

• if $$$\color{green}{(x_d \geq 0 \texttt{ and } y_d \geq 0) \texttt{ or } (x_d < 0 \texttt{ and } y_d < 0)}$$$ then: $$$|x_d| + |y_d|$$$

case where signs of $$$x_d$$$ and $$$y_d$$$ are the oposite:

• if $$$\color{green}{(x_d \geq 0 \texttt{ and } y_d < 0) \texttt{ or } (x_d < 0 \texttt{ and } y_d \geq 0)}$$$ then: $$$|x_d| + |y_d|$$$

For now part after " then " is the same, but in the next step we will transform both of them.

3) Under these 2 conditions we can put everything under one $$$abs()$$$ function.

When signs of $$$x_d$$$ and $$$x_y$$$ are the same, it is clear how to do it, just summarize them inside of the $$$abs()$$$ function.

• when $$$\color{green}{(x_d \geq 0 \texttt{ and } y_d \geq 0) \texttt{ or } (x_d < 0 \texttt{ and } y_d < 0)}$$$ : $$$|x_d| + |y_d| = |x_d + y_d|$$$

And if the signs are different, let's make them the same, and then summarize them.

• when $$$\color{green}{(x_d \geq 0 \texttt{ and } y_d < 0) \texttt{ or } (x_d < 0 \texttt{ and } y_d \geq 0)}$$$ : $$$|x_d| + |y_d| = |x_d + (-y_d)| = |x_d - y_d|$$$

4) Now the most interesting part: let's try combining conditions together once again.

So we know that we can use the formula $$$|x_d + y_d|$$$ when signs of $$$x_d$$$ and $$$y_d$$$ are the same. But what happens to it when the signs are opposite?

We can see that $$$(|x_d + y_d| \color{red}{=} |x_d| + |y_d|)$$$ no longer holds true. To be more specific:

• when $$$\color{green}{(x_d \geq 0 \texttt{ and } y_d < 0) \texttt{ or } (x_d < 0 \texttt{ and } y_d \geq 0)}$$$ : $$$|x_d + y_d| \leq |x_d| + |y_d|$$$

We can make a similar statement with formula $$$|x_d - y_d|$$$: when signs of $$$x_d$$$ and $$$y_d$$$ are the same, the following is true:

• when $$$\color{green}{(x_d \geq 0 \texttt{ and } y_d \geq 0) \texttt{ or } (x_d < 0 \texttt{ and } y_d < 0)}$$$ : $$$|x_d - y_d| \leq |x_d| + |y_d|$$$

We can make a very interesting conclusion:

When signs are the same:

• $$$|x_d - y_d| \leq |x_d| + |y_d|$$$.
• $$$|x_d + y_d| = |x_d| + |y_d|$$$
• That means that $$$|x_d - y_d| \leq |x_d + y_d|$$$
• when $$$\color{green}{(x_d \geq 0 \texttt{ and } y_d \geq 0) \texttt{ or } (x_d < 0 \texttt{ and } y_d < 0)}$$$ : $$$|x_d - y_d | \leq |x_d + y_d|$$$

When signs are the opposite:

• $$$|x_d + y_d| \leq |x_d| + |y_d|$$$.
• $$$|x_d - y_d| = |x_d| + |y_d|$$$
• That means that $$$|x_d + y_d| \leq |x_d - y_d|$$$
• when $$$\color{green}{(x_d \geq 0 \texttt{ and } y_d < 0) \texttt{ or } (x_d < 0 \texttt{ and } y_d \geq 0)}$$$ : $$$|x_d + y_d | \leq |x_d - y_d|$$$

5) Now we have everything in place. Let's summarize it in human words.

• We had a formula that we divided into 2 cases, depending on $$$x_d$$$ and $$$y_d$$$ having the same or the opposite sign.
• We understood that when signs are the same, we can use formula $$$|x_d + y_d|$$$, and when they are the opposite, we can use $$$|x_d - y_d|$$$
• When the signs are the same, that $$$|x_d + y_d|$$$ gets us the biggest result out of 2 formulas, and when they are the opposite |$$$x_d - y_d$$$| gives the biggest.

So:

• signs are the same: we want to use $$$|x_d + y_d|$$$ and it is bigger (or equal)
• signs are the opposite: we want to use $$$|x_d - y_d|$$$ and it is bigger (or equal)

We can make a conclusion that to combine this 2 formulas we can always take the biggest one, and it will be the one we want to use.

So we end up with this beautiful formula

• $$$max(|x_d+y_d|, |x_d-y_d|)$$$

6) Let's rewrite it in terms of $$$x$$$ and $$$y$$$

• $$$max(|x_1-x_2+y_1-y_2|, |x_1-x_2+y_2-y_1|)$$$

And shuffle it around

• $$$max(|(x_1+y_1) - (x_2+y_2)|, |(x_1-y_1) - (x_2-y_2)|)$$$

7) lets define 2 new variables $$$s=x+y$$$ , $$$t = x-y$$$, with these variables we get:

• $$$dist = max(|s_1-s_2|, |t_1-t_2|)$$$

8) One final thing we should understand is that this formula no longer uses $$$x$$$ or $$$y$$$. It means that we can calculate values $$$s$$$ and $$$t$$$ for each point and work only with them.

As you can see, the formula became a lot more pretty. And also we can look at it in an interesting way: the distance between 2 points can be caused by the difference in coordinate $$$s$$$ or $$$t$$$ (or it can be both). This property can be used to solve the problem above.

I suggest you try to think about this problem on your own for 10-15 minutes once again, you may see this problem in a different light.

Geometric form

1) In the picture below you can see a random point $$$\color{#A00}{P}$$$ I chose. All points that are at a Manhattan distance of $$$3$$$ from point $$$\color{#A00}{P}$$$ are located on the red square. Also $$$\color{#A00}{W}$$$ represents one of the sides of the red square.

Notice that the red square is not parallel to $$$OX$$$ and $$$OY$$$ axes. Because of it is a bit hard to visualize how it looks without drawing.

But it should not necessarily be like that. Let's make a new coordinate system with axes $$$OS$$$ and $$$OT$$$, where sides of the square are parallel (or perpendicular) to the new axes. We can achieve that by having $$$OS$$$ go in $$$\vec{(1, 1)}$$$ direction, and $$$OT$$$ in $$$\vec{(1, -1)}$$$ direction.

From this point I will use $$$black$$$ color to represent points in $$$XY$$$ system, and $$$\color{blue}{blue}$$$ color for $$$ST$$$ system.

2) Now let's think about the unit of measure, that we will use in our new $$$ST$$$ coordinate system. We will use $$$\color{blue}{(s, t)}$$$ notation to define points.

• Notice that side $$$\color{#A00}{W}$$$ has a distance to the point $$$(0, 0)$$$ equal to $$$3.5$$$ diagonals (of 1x1 squares). We don't want to deal with decimal numbers, so let's take as a unit of measure a half-diagonal.
• If we do that, point $$$(1, 1)$$$ in $$$XY$$$ system will be equal to $$$\color{blue}{(2, 0)}$$$ in $$$ST$$$ system
• And point $$$(1, -1)$$$ in $$$XY$$$ system will be equal to $$$\color{blue}{(0, 2)}$$$ in $$$ST$$$ system

Now we have everything ready to locate every corner of the red square and point $$$\color{#A00}{P}$$$ in our new $$$ST$$$ coordinate system.

3) I think it is a good moment to learn how to transform points from $$$XY$$$ system to $$$ST$$$ system. To do that let's think in terms of vectors, I think it would be easier to understand this way.

One of the corners of the red square has coordinates $$$(2, 3)$$$ in $$$XY$$$ and coordinates $$$\color{blue}{(5, -1)}$$$ in $$$ST$$$. Let's try to make this transition between coordinate systems through formulas.

a) At first, lets understand how basis vectors of $$$XY$$$

Unable to parse markup [type=CF_MATHJAX]

• $$$\vec{(1, 0)}$$$ in $$$XY$$$ looks like $$$\color{blue}{\vec{(1, 1)}}$$$ in $$$ST$$$
• $$$\vec{(0, 1)}$$$ in $$$XY$$$ looks like $$$\color{blue}{\vec{(1, -1)}}$$$ in $$$ST$$$

b) Then we should understand that any point can be described using basis vectors and origin point $$$(0, 0)$$$

So point $$$(2, 3)$$$ in $$$XY$$$ system can be described as

• $$$(0, 0) + 2 * \vec{(1, 0)} + 3 * \vec{(0, 1)} = (2, 3)$$$

c) And now the cool part: let's use the formula from b, but instead of using $$$XY$$$ coordinates for basis vectors, let's use their $$$ST$$$ coordinates that we got in a

• $$$\color{blue}{(0, 0)} + 2 * \color{blue}{\vec{(1, 1)}} + 3 * \color{blue}{\vec{(1, -1)}} = \color{blue}{(5, -1)}$$$

So the point $$$(2, 3)$$$ in $$$XY$$$ system converts to $$$\color{blue}{{(5, -1)}}$$$ in $$$ST$$$

It's a hustle to go though all of these operations every time we want to transfer a point from $$$XY$$$ to $$$ST$$$, so we should put all of the above into simple formula.

We can think about it like this:

• For every $$$1$$$ in $$$x$$$ coordinate, we add $$$1$$$ to $$$s$$$ and $$$1$$$ to $$$t$$$ (because basis vector $$$\vec{(1, 0)}$$$ in $$$XY$$$ translates to $$$\color{blue}{\vec{(1, 1)}}$$$ in $$$ST$$$
• For every $$$1$$$ in $$$y$$$ coordinate, we add $$$1$$$ to $$$s$$$ and $$$-1$$$ to $$$t$$$ (because basis vector $$$\vec{(0, 1)}$$$ in $$$XY$$$ translates to $$$\color{blue}{\vec{(1, -1)}}$$$ in $$$ST$$$

We can summarize it as

• $$$s = x + y$$$
• $$$t = x - y$$$

Notice that we had variables $$$s$$$ and $$$t$$$ in the algebra section that we defined exactly like that.

4) So now we know how to convert points from $$$XY$$$ to $$$ST$$$, but it does not help us yet. Let's redraw a picture, get rid of $$$XY$$$ coordinate system (we won't need it anymore) and make $$$OS$$$ go to the right, and $$$OT$$$ go up.

• Note that we can point the axes in any direction, I usually use $$$(s,t)$$$ notation, so I want the first coordinate to point to the right, and the second one — up, so it behaves just like regular $$$XY$$$ coordinate system with points written in $$$(x, y)$$$ notation

5) Now interesting things start to happen: remember that red square still represents the Manhattan distance from $$$P$$$ equal to $$$3$$$, but now it looks different. Manhattan distance formula should also look different, it should represent a square that is parallel to axes $$$S$$$ and $$$T$$$. We can try to deduce what formula it will be by analyzing the picture above.

a) At first, let's try to describe the square the most straightforward way

• $$$s = 5, -1 \leq t \leq 5$$$
• $$$s = -1, -1 \leq t \leq 5$$$
• $$$t = 5, -1 \leq s \leq 5$$$
• $$$t = -1, -1 \leq s \leq 5$$$

b) let's try to simplify equation

Unable to parse markup [type=CF_MATHJAX]

• $$$-1 \leq t \leq 5$$$ <=> $$$-3 \leq t-2 \leq 3$$$ <=> $$$|t-2| \leq 3$$$
• the same goes for $$$s$$$ : $$$|s-2| \leq 3$$$

Let's right down simplified formula

• $$$s = 5, \color{green}{|t-2| \leq 3}$$$
• $$$s = -1, \color{green}{|t-2| \leq 3}$$$
• $$$t = 5, \color{green}{|s-2| \leq 3}$$$
• $$$t = -1, \color{green}{|s-2| \leq 3}$$$

c) We should think about combining the statements together.

• $$$s = 5 \texttt{ or } s = -1$$$ <=> $$$|s-2| = 3$$$
• $$$t = 5 \texttt{ or } t = -1$$$ <=> $$$|t-2| = 3$$$

so we get this:

• $$$\color{green}{|s-2| = 3}$$$, $$$|t-2| \leq 3$$$
• $$$\color{green}{|t-2| = 3}$$$, $$$|s-2| \leq 3$$$

I think here it is clear that we can use $$$max$$$ function to combine these $$$2$$$ statements

• $$$max(|s-2|, |t-2|) = 3$$$

Values $$$(2, 2)$$$ represent coordinates of the point $$$P$$$ in $$$ST$$$ system.

• $$$max(|s-s_P|, |t-t_P|) = d$$$.

So the general formula will look like this:

• $$$d = max(|s_1-s_2|, |t_1-t_2|)$$$.

Notice that it is the exact same formula that we got in the algebra section of the blog.

From this point we can follow the editorial for the algebra approach. Or we can be more interesting: let's try to solve the problem above with visual approach (just like we did in the editorial without the trick), but this time it will be a bit different: because we don't have to deal with diagonals, the implementation will be much easier.

And also, but this is just my opinion, I find it a bit easier to come up with this approach while using the trick, I only thought of this solution after thinking in terms of $$$ST$$$ coordinates. I know that there is little difference, but I find it a lot easier to imagine it in my head.

Conclusion

I think that the approaches I provided for the problem above are not that difficult, but that task was marked as $$$\color{red}{2400}$$$ problem. When I saw that problem in the contest, I also had no idea how to solve it. But after learning this trick, it seemed pretty easy to me. I hope you also don't find this problem hard anymore after reading this blog.

Also I give online classes, $$${\$25}$$$ per hour for one on one lessons, $$${\$8}$$$ per hour for lessons in groups of 3, free trial lesson. Contact me on Codeforces if you are interested or for more info.

I am on Windows, I don't want to use WSL or Visual Studio. I want the compiler to tell me about stupid bugs. But I cannot figure out a way to do it.

The problem: I cannot figure out a way to catch both of the bugs below:

#include<iostream>
#include<vector>
#include<set>
using namespace std;
int main() {
	//case 1
	vector<int> V(5);
	cout << V[10] << endl;
	
	//case 2
	set<int> Set;
	cout << *Set.begin();
}

Using clang

Clang allows me to use sanitizers on windows. I was not able to find a way to make them work in mingw. Here are my flags:

I can successfully catch the case 1, in the error window I can clearly see what the mistake and the line where it happens.

==21988==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x115ace5203c8 at pc 0x7ff6fc6a11c4 bp 0x002fb417f8e0 sp 0x002fb417f928
READ of size 4 at 0x115ace5203c8 thread T0
    #0 0x7ff6fc6a11c3 in main C:\Users\rl\AppData\Local\Temp\CP Editor-KnCttI\sol.cpp:8

But I get no errors when I have the case2 bug.

Using mingw

I found 2 useful blogs on codeforces on this topic. There I found about the -D_GLIBCXX_DEBUG flag, but it does not work for me with clang, so I used mingw.

Case1 is worse than in clang case, because I don't see the specific line

C:/mingw64/lib/gcc/x86_64-w64-mingw32/13.2.0/include/c++/debug/vector:442:
In function:
    std::debug::vector<_Tp, _Allocator>::reference std::debug::vector<_Tp,
    _Allocator>::operator[](size_type) [with _Tp = int; _Allocator =
    std::allocator<int>; reference = int&; size_type = long long unsigned
    int]

Error: attempt to subscript container with out-of-bounds index 10, but
container only holds 5 elements.

Objects involved in the operation:
    sequence "this" @ 000000904FBFFAD0 {
      type = std::debug::vector<int, std::allocator<int> >;
    }

But the case2 is better than with clang, at least I know that something is wrong and what type of mistake I made, but sadly I don't see the specific line.

C:/mingw64/lib/gcc/x86_64-w64-mingw32/13.2.0/include/c++/debug/safe_iterator.h:298:
In function:
    gnu_debug::_Safe_iterator<_Iterator, _Sequence, _Category>::reference
    gnu_debug::_Safe_iterator<_Iterator, _Sequence, _Category>::operator*()
    const [with _Iterator = std::_Rb_tree_const_iterator<int>; _Sequence =
    std::debug::set<int>; _Category = std::forward_iterator_tag; reference =
    const int&]

Error: attempt to dereference a past-the-end iterator.

Object`s involved in the operation:
    iterator "this" @ 0000008C1CBFFAA0 {
      type = std::_Rb_tree_const_iterator<int> (constant iterator);
      state = past-the-end;
      references sequence with type 'std::debug::set<int, std::less<int>, std::allocator<int> >' @ 0000008C1CBFFA50
    }

Both cases seem bad

I feel like I am doing something very wrong.

If you have a setup on windows that allows you to easily identify both of the bugs, I would be very interested to see how you did that.

I think this info can be useful to a lot of people who use windows and avoid using IDEs like visual studio (like people with low end pcs). I have seen too many people, including me, who manually search for this kind of bugs, and I think it should not be done like that.

C:\cp>clang -v
clang version 18.1.3
Target: x86_64-pc-windows-msvc
Thread model: posix
InstalledDir: C:\Program Files\LLVM\bin

C:\cp>g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=C:/mingw64/bin/../libexec/gcc/x86_64-w64-mingw32/13.2.0/lto-wrapper.exe
Target: x86_64-w64-mingw32
Configured with: ../../../src/gcc-13.2.0/configure --host=x86_64-w64-mingw32 --build=x86_64-w64-mingw32 --target=x86_64-w64-mingw32 --prefix=/mingw64 --with-sysroot=/c/buildroot/x86_64-1320-posix-seh-msvcrt-rt_v11-rev1/mingw64 --enable-host-shared --disable-multilib --enable-languages=c,c++,fortran,lto --enable-libstdcxx-time=yes --enable-threads=posix --enable-libgomp --enable-libatomic --enable-lto --enable-graphite --enable-checking=release --enable-fully-dynamic-string --enable-version-specific-runtime-libs --enable-libstdcxx-filesystem-ts=yes --disable-libssp --disable-libstdcxx-pch --disable-libstdcxx-debug --enable-bootstrap --disable-rpath --disable-win32-registry --disable-nls --disable-werror --disable-symvers --with-gnu-as --with-gnu-ld --with-arch=nocona --with-tune=core2 --with-libiconv --with-system-zlib --with-gmp=/c/buildroot/prerequisites/x86_64-w64-mingw32-static --with-mpfr=/c/buildroot/prerequisites/x86_64-w64-mingw32-static --with-mpc=/c/buildroot/prerequisites/x86_64-w64-mingw32-static --with-isl=/c/buildroot/prerequisites/x86_64-w64-mingw32-static --with-pkgversion='x86_64-posix-seh-rev1, Built by MinGW-Builds project' --with-bugurl=https://github.com/niXman/mingw-builds CFLAGS='-O2 -pipe -fno-ident -I/c/buildroot/x86_64-1320-posix-seh-msvcrt-rt_v11-rev1/mingw64/opt/include -I/c/buildroot/prerequisites/x86_64-zlib-static/include -I/c/buildroot/prerequisites/x86_64-w64-mingw32-static/include' CXXFLAGS='-O2 -pipe -fno-ident -I/c/buildroot/x86_64-1320-posix-seh-msvcrt-rt_v11-rev1/mingw64/opt/include -I/c/buildroot/prerequisites/x86_64-zlib-static/include -I/c/buildroot/prerequisites/x86_64-w64-mingw32-static/include' CPPFLAGS=' -I/c/buildroot/x86_64-1320-posix-seh-msvcrt-rt_v11-rev1/mingw64/opt/include -I/c/buildroot/prerequisites/x86_64-zlib-static/include -I/c/buildroot/prerequisites/x86_64-w64-mingw32-static/include' LDFLAGS='-pipe -fno-ident -L/c/buildroot/x86_64-1320-posix-seh-msvcrt-rt_v11-rev1/mingw64/opt/lib -L/c/buildroot/prerequisites/x86_64-zlib-static/lib -L/c/buildroot/prerequisites/x86_64-w64-mingw32-static/lib ' LD_FOR_TARGET=/c/buildroot/x86_64-1320-posix-seh-msvcrt-rt_v11-rev1/mingw64/bin/ld.exe --with-boot-ldflags=' -Wl,--disable-dynamicbase -static-libstdc++ -static-libgcc'
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 13.2.0 (x86_64-posix-seh-rev1, Built by MinGW-Builds project)

Basically the title.

Why the problems seem so much easier if you go to sleep and return to it the next day? It happened to me numerous times. I struggle for hours with a problem, I give up and move on with my day, I return to it in a day or two, usually I don't remember the statement, but after reading it I solve it almost effortlessly. It is like my brain solves the tasks on its own throughout the day, but I find it hard to believe that it is able to do that if I don't even remember the statement. Sometimes I wonder why I bother thinking about a problem at all if I get stuck for more than 10 minutes. I know that almost certainly I will be able to solve it the next day (if I pick an appropriate difficulty for me obviously).

I have pretty much 0 knowledge on how the brain works, and I wonder why this weird thing happens. I know that it is a common knowledge to "sleep on the problem", I was told that in school for example, but I have not seen anyone talking on how MUCH it affects the results.

I also wonder, if it possible to master this "power" lol?
It sounds weird, but I have an "ultimate move" during the contest to go to the toilet, for some unholy reason I consistently was able to find creative ideas in a span of several minutes I spent there. It seams like forgetting about the problem, and then returning to it works just like turning a device off and on, seems to fix most of the problems. But it is so hard to do it during a contest, especially when there is almost no time left. I also know that skipping a problem and then returning to it might be effective when you are stuck, but the effect is so much weaker for me. It helps, but just a bit.

У меня 560 баллов из 600, но я не прошёл. Интересует, есть ли кто-то с меньшим/таким же количеством баллов, кто смог пройти? Хочу узнать, то ли тоталы у всех, то ли им не понравилось что я про себя написал.