By long break I mean 3 months or more.

I recently experienced a great positive effect on my job-related performance after having a long break. It seemed weird, I expected an opposite effect.

So my question is, have you ever:

1. practice something (Competitive Programming or maybe some other non-physical activity) for a long time
2. then took a long break (3 months+ of not engaging with this activity at all)
3. then continued to actively practice something

Did your performance increase or decrease?

Recently I thought a lot about optimizing my setup. I don't think it is an important aspect of cp, as it barely affects the performance, but it is fun to think about nonetheless.

In this blog, you will be able to determine whether you have an optimal setup or not. I will list the criteria and points you get for satisfying each one of them. In the end, I do the breakdown for different point ranges.

I won't include things like having a monitor or having an internet connection, but I will be including basically everything else that comes to my mind. If you see something missing from the list, let me know in the comments, I will probably update my list then.

This blog is mainly made for laughs, but if you are new, you will probably learn something new, even though it won't help you to increase your rating.

You can compile and run your code.

• $$$0$$$ points: I don't know how to run my code before submitting
• $$$10$$$ points: I compile my code before submitting

I knew many school kids that never figured out how to run their code locally. I even saw some people like this in the university. Judging by 73 pages of Compilation Error submissions from the last Div 4 contest on problem A alone, I have seen nothing yet.

You have to be able to run your code locally. Even LGMs run their $$$A$$$ solutions on the sample tests.

Your text editor does not lag / crash

• $$$0$$$ points: My editor is laggy and crashes all the time
• $$$2$$$ points: My editor is a bit laggy and crushes sometimes
• $$$4$$$ points: My editor runs perfectly

When I was writing local contests during my school years, I constantly dealt with lags and crashes. Probably I should not have used Visual Studio on a machine that could barely run it. So if you have the same issues, I think you understand why you lose points.

You can compile and run your code with no internet

• $$$0$$$ points: I use an online editor and need internet access to run my code
• $$$2$$$ points: I don't need internet access to compile my code

Some people you online editors like this one. I think not being able to compile without having internet it is a pretty big deal.

You can benefit from syntax highlighting and you use it.

• $$$0$$$ points: I am not using syntax highlighting, but I would use it if I could
• $$$2$$$ points: I use syntax highlighting
• $$$2$$$ points: I don't use syntax highlighting because it is useless for me

If you are not colorblind, or you are not used to mono blue text on a blue screen like my dad, you will probably benefit from making you code more readable by automatically coloring it depending on the context.

You are able to see how many seconds your program took to run

• $$$0$$$ points: When I run my code I don't see how much time has passed
• $$$1$$$ point: When I run my code I see the number of seconds it took to run

Seeing the time your program took to run probably won't help you to $$$100$$$ % accurately predict whether you will get TLE or not. But being able to determine whether your solutions runs slower or faster on a max test after a fix is important.

You can see how much memory your program uses.

• $$$0$$$ points: I cannot check the amount of memory my program used
• $$$1$$$ points: I can check how many megabytes my program used

In certain implementations, it is hard to determine how many megabytes of memory your solution takes, so it is sometimes useful to see that info.

You can see syntax mistakes in your code without running it (in other words, you are using a Language Server)

• $$$0$$$ points: I have to compile my code to see mistakes in the syntax.
• $$$3$$$ points: When I make a typo, my editor tells me about it straight away

If you only can see that you have made a typo only after you compiled your code, then you have to fix the mistake and then compile the program again. It wastes time

You are using a programming language, that can solve all of the problems in the contest you attempt

• $$$0$$$ points: I attempted a problem in the past and failed because of my choice of programming language
• $$$3$$$ points: The programming language I use has never failed me.

Some tasks are impossible to solve using slower languages. Sometimes it is possible to solve a task, but you have to put in extra effort to do so. I am not an expert here, so I won't list "unviable languages". But if you run into this kind of issues, I think you also understand that what you are doing is suboptimal

You have a fast way to copy and paste algorithms/data structures

• $$$0$$$ points: I never copypaste anything / Usually I copy algorithms from the internet
• $$$2$$$ points: I have my own library of algorithms/data structures and when I need something, I search in it and copypaste to my code
• $$$3$$$ points: I have my own library and I have hotkeys (snippets-like) to easily paste needed algorithms into my code without leaving my editor

If you are finding yourself implementing the same Add on a segment, sun on a segment Segment tree algorithm 3 times in a row, you are probably becoming faster and faster at implementing it. In a certain sense, it is optimal in terms of learning. But it always be slower than just copying and pasting it.

You don't have to copy and paste your tests every time you run your program.

• $$$0$$$ points: When I run my program, I have to paste the text in the console every time I run the program
• $$$2$$$ point: I am able to paste 1 test once and run it multiple times
• $$$3$$$ points: I am able to paste several tests at once and run all of them with a push of 1 button

If you have to copy the same tests over and over again to test your solution, you are doing something very wrong: it wastes a lot of time. Also sometimes it is important to be able to input data line by line (when solving interactive problems for example), that is why there is a difference between $$$2$$$ and $$$3$$$ points

You have good warnings/error messages.

• $$$0$$$ points: My warning/error messages are confusing and they don't help me at all
• $$$1$$$ points: My warning/error messages are mostly useful, but sometimes I wish they were better
• $$$2$$$ points: My warning/error messages are always telling me what is wrong with my program, and I don't see a way how to make it better

I use C++ and I have spent some time on adding compilation flags that enable some new warnings. I was not able to get all of the sanitizers working properly, but even the warning messages became a lot more useful. There is a cool blog on this topic.

Auto-parcing contests to copy tests.

• $$$0$$$ points: I copy sample tests from the tasks manually
• $$$1$$$ point: I use tools to automatically copy tests from problems

There are tools like this one that allow you to copy tests from the tasks.

Your code is readable and hackable.

• $$$0$$$ points: I have a > 50 lines template that makes it harder to read my code
• $$$1$$$ point: I don't use a template / my template is <= 50 lines of code / it is > 50 but I am sure it does not prevent anyone from easily understanding my code

Hacks exist, it is always better to get hacked (unless it is some anti-hash hack) than to FST

You can run a debugger (in a form that is easy to use).

• $$$0$$$ points: I cannot run a debugger in a form that is easy to use for me
• $$$1$$$ point: I can run a debugger in a form that is easy to use for me, but I prefer not to use it
• $$$1$$$ point: I can run a debugger in a form that is easy to use for me and I use it

Even if you are not usually using a debugger, the option to be able to is definitely a plus. Printing is not always faster.

You have a good way to print() to debug

• $$$0$$$ points: I use plain cout or print to debug.
• $$$1$$$ points: I use advanced debug printing: like using macros to output the names of the variables with their values, being able to easily output the array.
• $$$3$$$ points: I have a complete debugging library, that is able to output graphs/data structures in an easily readable form

You have a stress testing setup.

• $$$0$$$ points: I don't use stress testing or I have no setup to use it.
• $$$2$$$ points: I have a template that helps me to stress test my solutions
• $$$4$$$ points: I have a script that is able to stress my solutions.

If you don't know about stress testing, you get 0 points and you should also check out this cool video that explains it.

You are using vim motions/ other advanced text editor key bindings.

• $$$0$$$ points: I don't use vim motions or any other advanced text editor key bindings
• $$$2$$$ points: I use vim motions or other advanced text editor key bindings.

Repeatedly grabbing your mouse to select text is definitely suboptimal. Using arrow keys to traverse through code is very slow. Using things like vim motions will speed things up a lot

WPM while typing.

• $$$0$$$ points: I have < 30 WPM while typing
• $$$1$$$ point: I have >= 30 WPM while typing
• $$$2$$$ point: I have >= 100 WPM while typing

You can check your typing speed here. I know typing steep is not really a setup, but it is close enough to include in this blog.

I don't think it really matters, except for the edge cases. Being too slow can hurt your performance, and also being very fast can get you a lot of rating in a speedforces situation.

You can easily use multiple files to code

• $$$0$$$ points: I use a single file to code, if I want to write something in parallel, I copy the old solution to the notepad
• $$$1$$$ point: My setup allows me to code in several windows.

Sometimes you want to jump to another problem while not finishing the current one. If you have to copy your code somewhere before you start coding a new problem, it is some extra time spent on managing something that can be made easier.

You are using a class for modular operations

• $$$0$$$ points: I don't use special classes for modular operations and my code looks like this d = ((a+b)%mod - c + mod)%mod * e % mod
• $$$1$$$ point: I use a special class for modular operations and my code looks like this d = (a+b-c)*e

You have a diff tool to compare the results of the tests

• $$$0$$$ points: When I run my tests, I manually check for the differences in the output
• $$$1$$$ point: When I run my tests, my diff tool tells me whether the is a difference in the test outputs or not, so I don't have to check it manually

Sometimes the output of the test is huge, and it is a hustle to check it manually. Let the computer check it for you and don't play the game of "find 5 differences" every time the output is big.

Counting points

Now it is time to sum up all of your points! In the list below you can see what kind of coder you are.

• 46-50) You are either $$$\color{orange}{2300}+$$$ and have a cool optimal setup, or you are ~ $$$\color{green}{1200}$$$ and wasting too much time on optimizing your setup instead of focusing on solving problems
• 36-45) You have a pretty good setup, old ladies who have no clue about how computers work think that you are a "hacker"
• 20-35) You are writing in a suboptimal environment, either because you are a bit too hardcore about "to be better at solving problems I have to solve problems", or because you are a punk $$$\color{black}{L}\color{red}{GM}$$$ that is too cool to care about what tools to use while destroying competitors.
• 13-19) You are a math enthusiast that decided to join codeforces because online math olympiads are not that fun.
• 0-12) You should be the happiest if you got this amount of points. It means you can improve your rating aside from just solving more problems, because it is almost like you are participating from your Nokia phone.

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 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$$$ $$$\vec{(1, 0)}$$$ and $$$\vec{(0, 1)}$$$ transfer to $$$ST$$$.

• $$$\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 $$$-1 \leq t \leq 5$$$

• $$$-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.