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 (｡◕‿‿◕｡)