### Zhtluo's blog

By Zhtluo, history, 2 months ago,

I hope my previous blog has convinced you that the best way to improve at Codeforces is to be more Russian, i.e. to improve your math capability. Unfortunately, humble mortals such as you and I are not gifted with the talent that esteemed Russian grandmasters such as 74TrAkToR had:

Surely, it is beneficial to have a code reference for many algorithms and data structures, but I also think that just superficially knowing the algorithm and maybe having implemented it once or twice before is sufficient to use it without a reference?

— Some other Codeforces grandmaster

Therefore, in this blog I will explore the dark side of Russian-ness — randomly guessing — that is forsaken by every Russian grandmaster of the light side I know. However, it has been very helpful to me, and I hope that it serves you well, too.

## Example 1

I will start by using an example to demonstrate my thought process. This problem 1923C was from a recent Educational Round.

### Intuition

To solve the problem, I first read the statement. My first impression is that the statement kind of asks if you can fudge a subarray a little bit. So it's intuitive that I first imagine some sort of subarray (represented by a plot) in my head.

I then check the conditions — I have to change every element a little bit while leaving the sum intact. Intuitively it is pretty easy to change every element a little bit (up 1 or down 1) without affecting the sum too much.

Then it seems very hard to reason from here, so I make a guess: Every subarray is fudgeable.

Now I try to find a counterexample to my guess. There are plenty of them, but intuitively bad things happen when you have a bunch of $1$ s since you cannot lower them down.

It would then seem that we need to consider the potential other elements can be lowered down and the necessity of $1$ s being raised up.

Now I make another guess: As long as there is enough potential to lower down things than the number of $1$ s, the answer is yes.

I then try to find another counterexample. I am not able to find any, so I believe that this is correct (which as you will see is actually not).

Now I need to figure out how to compute the number of $1$ s and the potential of every subarray. I am Chinese enough, so I dismiss both as trivially doable by some technique.

Now the problem looks solved, so I move to formalization.

### Formalization

In this step I have to actually write down math. Obviously the necessity of raising is dictated by the number of $1$ s, and trivially maintained by some prefix sum cnt[] on counting $1$ s. The potential seems to be the sum minus the length, and also trivially maintained by prefix sum sum[].

Now the problem seems to be codeable, so I move to implementation.

### Implementation

This step is mostly just coding and debugging. I first code this:

Code

Then it WAs on the sample... Fortunately by looking at the sample I see that I missed a trivial edge case where the length of the subarray is $1$ . This is quickly fixable:

      if (s - (r - l + 1) >= c && (r - l + 1) > 1)


Then it ACs. The whole process takes no more than 15 minutes.

## Review

So what happened in the example? In this blog I will mainly talk about the intuition process. As you can see from the example above, I start my intuition by imagining the problem in my head with something I am familiar with (a plot). Because this all happened in my head, you will see that there is almost no formula in my head. Or, as I would like to put it,

Formalization is the death of intuition; don't use formula in the intuition part if you can.

Then, there are roughly three methods I can use to solve the problem.

1. Dismiss. I can say I know how to do this with some technique (i.e. Chinese-ness) and throw it out.

2. Reason. I can take a logical step forward, relatively confident that I am correct.

3. Guess. I can randomly guess the most convenient thing that helps solve the problem. This is followed by trying to find a counterexample in some amount of time. If none is found, I believe it is correct.

Now I will demonstrate this process on another problem: 1923D, this time without pictures.

## Example 2

Now this problem is about slimes, so it makes sense to imagine a column of balls in my head.

### Intuition

Now I first reason that if some slime is eaten, it must be eaten either by a left giant ball or a right giant ball. Since it is symmetric I will consider the left case.

Now I reason that the left giant ball surely is made by some interval of slimes, whose sum is larger than this slime.

Then I get stuck, so I guess that any interval greater than this slime is plausible.

I try to find a counterexample. I end up finding one, which happens when everyone is the same size so no one can eat anyone else.

I then guess that that any interval greater than this slime and not all the same is plausible.

I try to find a counterexample. I cannot find anyone, so I believe it is true.

Now for some slime I need to know the shortest left interval that is not all the same and has sum greater than this slime. I dismiss that both are trivially binary-searchable. Now the problem looks solved to me.

### Formalization

I mainly need to figure out how to test if an interval is of the same number. There are multiple ways to do it, but intuitively we can run a prefix sum on A[i] == A[i - 1]. Now the problem looks codeable to me.

### Implementation

Now just start coding...

Code

Apparently this code got WA on test 2. Debugging this is a pretty interesting American task, but I will skip this part (as it is unrelated to intuition) and just say that the issue is that in binary search does not adequately cover the case where the neighboring one is directly larger.

      if ((i - 1 >= 0 && A[i - 1] > A[i]) || (i + 1 < N && A[i + 1] > A[i])) {
ans1 = ans2 = 1;
}


Fixing this is enough to AC.

## The Elephant in the Room — Why You Should Guess without Proving

Now that all esteemed Russian grandmasters should have already got very angry, claimed that this is 'too young, too simple,' downvoted this blog, and left, I am going to address the most important issue: why you should learn to guess without proving anything.

### A Counterexample: Why Proving is Bad

Let us use the previous slime example. Say we want to actually prove the guess. How should we start?

We can try to construct a eating sequence on the interval. To do that, we need to guess that the some maximum slime with size $m$ in the interval can eat everyone else. But if two neighbouring slimes are both maximum, then they cannot eat each other. So we need to guess that:

If the slime interval with $m$ as the maximum element has at least two distinct elements, then there exists some neighbouring slime pairs $(a_i,a_{i+1})$, such that one of the slime is $m$ and the other is not $m$.

It is not very obvious how to prove this. So we need to flip the statement to its contrapositive:

If for the slime interval with $m$ as the maximum element, there does not exist any neighbouring slime pairs $(a_i,a_{i+1})$ such that one of the slime is $m$ and the other is not $m$, then the interval has only one distinct element.

We can then use induction to prove this statement.

For an interval of length $1$, this is obviously true.

Assume the statement is true for any interval of length $n$. For an interval of length $n+1$, observe that for the prefix of $n$ elements, there is only one distinct element $m$. Therefore, since there does not exist any special slime pair, the last element must also be $m$.

This concludes the induction proof.

If you followed the proof, you should notice that:

• We spent a lot of effort on guessing things not related to implementation at all.
• We used proof techniques such as induction which is totally unnecessary if we just want to solve this problem.

I would also assert that it probably takes more effort to think and write this proof than to just code the solution out, which motivates me to develop a theory on guessing.

### Theory on Guessing

I begin by claiming that proving is very inefficient:

(Thesis of Proof-by-AC) Consider that for some problem you have a solution that takes $a$ time to code with probability $p$ of being correct. Assume you can find a proof for this solution in $b$ time, you should only do so if $b<\frac{1-p}{p}a$.

Unfortunately, I cannot say I guessed this thesis and actually have to prove it. So here is the proof.

Let us consider the expected efficiency of problem solving, defined as (expected problems solved) / (time taken). Observe that we want to maximize this efficiency.

If we code this problem, then our expected efficiency is $\frac{p}{a}$.

If we try to prove it, the best case is that after $b$ time we have an absolutely correct solution (since finding out our solution is wrong only lowers the efficiency). In this case, our expected efficiency is $\frac{1}{a+b}$.

A trivial computation gives the thesis, which is left for the Russian grandmasters who have not left yet as a practice.

We can plug in some number to demonstrate the inefficiency of proving. If you have some solution that works 50% of the time, according to the thesis you should only prove it if proving it takes less time than coding it. Now since you have to guess it rather than reason it, chances are you are not going to figure out the proof in $a$ time, so you probably should just go coding.

I think the main takeaway for the thesis of Proof-by-AC is that we don't need our solution to be correct; we only need a probabilistically correct solution to increase our efficiency (and subsequently rating). We will see in the following sections that we can loosen this statement even further.

#### Some Theory on Reasoning

Apparently in philosophy some people have already discussed about reasoning vs. guessing. In their theory, logic is categorized into three parts.

1. Deduction. This is the most rigorous form of logic, the one you will encounter the most in model solutions.

2. Induction. This means to make a conclusion based on a body of observations. In CP this means to brute-force small cases and do some pattern recognition. Fortunately, esteemed Russian grandmasters (maybe with the exception of 74TrAkToR) does not like this line of reasoning too much, so you will not face a lot of brute-force pattern-finding problems. Just so you know, ChatGPT is also pretty good at writing a brute-force.

3. Abduction, a.k.a. randomly guessing. This is the randomly guessing we are looking at. It means to seek the simplest and most likely conclusion from a set of observations.

So what I am going to show you next is that abduction is not that bad, especially in a Codeforces setting.

#### Some Learning Theory

Fortunately, in machine learning people are already dealing with estimating the correctness of a model in real life when it is correct on all training data, which is exactly the same as we are trying to estimate the correctness of a guess in system tests when it is correct on all examples we can think of. Allow me to introduce the concept of PAC learning:

(Claim of PAC Learning, from UPenn): The probability that there exists a hypothesis $h \in H$ that is consistent with $m$ examples and satisfies $\textrm{Error}(h) > \epsilon$ is less than $|H|(1 − \epsilon)^m$.

Or, in layman's words:

(Thesis of PAC Abduction): The simpler the hypothesis, the more examples we find, the more likely the hypothesis is correct on most tests.

Now we can assume that we draw examples from a somewhat similar distribution as test cases are generated. We can also assume that any problem on Codeforces has no more than 1000 test cases. This seems to imply that as long as we make sure that $\textrm{Error}(h) < \frac{1}{1000}$ we have a pretty good chance of passing all test cases (in fact, more than $\frac{1}{e}$). In other words, we only need to make sure that our guess is probabilistically approximately correct (i.e. PAC).

## Example 3

I want to add a final example on 1930C, a funny problem I did recently, to demonstrate the full might of PAC abduction, a.k.a. randomly guessing.

Naively if we never take out the same number, we should just greedily take numbers on a right-to-left order, but what happens when we take out numbers that are the same?

Me, after looking through the samples, guessed: Surely we can just get that number minus 1.

My code:

Code

The funny part comes after the contest.

Another Russian Master: I don't understand why your C works.
Me: IDK too.
Another Russian Master: What?
Me: What?

## Common Pitfalls

There are some common pitfalls when using the way of thinking. I will list a few that I encountered.

• Dismissing too quickly. When you dismiss a thing, you have to actually figure out how to do it when you start formalizing. Sometimes I dismiss things too fast and find that I don't actually know how to do it. Fortunately this usually just results in more thinking, but it is important to be aware of your Chinese skill level.

• Not knowing what to guess. This happens usually because you are not familiar with common things that you can guess. One way to deal with it is to always guess the most convenient thing (like the three examples above). The other way is that when you are reading the tutorial, ask yourself: what guess can I come up with that solves the problem? Or rather, as I would put it: In an upsolve, ask yourself how you could have solve the problem in the contest. If you cannot see a plausible way to solve the problem in contest then you cannot solve it in contest.

• Guessed a wrong thing and didn't find the counterexample. This is the price we pay for guessing, though you should ask yourself if the counterexample is trivial to find. If it is something easy (e.g. all elements being the same), then you should try to think of more examples in the upcoming contests.

## FAQ

• I guessed the solution and everyone around me called me a cheater!
The dark side of the Russian-ness is a pathway to many abilities some consider to be unnatural.

• But guessing randomly is not fun!
I don't think it's fun, either. Unfortunately, given that Codeforces only consists of problems with high Russian-ness, guessing is the fastest way to improve in my opinion. Maybe go ask Mike to host problems of more Chinese-ness or American-ness so that we aren't forced to guess through the contest.

I will end the blog with the code of randomly guessing:

Proof is a lie; there is only AC.
Through guessing, I gain code.
Through code, I gain AC.
Through AC, my ratings are broken.
The Russian-ness shall free me.

— Darth Luo, probably

## Experiment

Question: Is communism science or art?
Answer: Of course it is art. If it was science, they would have experimented on rats first!

— Some Soviet grandmaster, probably

I am actually curious how much randomly guessing can help people in Div. 3 and Div. 2. If you are convinced by me, maybe you can try it out on some problems around your rating and tell me your experience in the comments! This will help me to understand its efficacy. Thanks!

• +431

 » 2 months ago, # |   +3 Auto comment: topic has been updated by Zhtluo (previous revision, new revision, compare).
 » 2 months ago, # |   -75 Hi, I am learning CP and i kind of got stuck at one of the problems in CSES. https://mirror.codeforces.com/blog/entry/126821. Any help will be greatly appreciated. Also greatly helpful blog Zhtluo.
•  » » 2 months ago, # ^ | ← Rev. 2 →   -65 Why am i getting downvoted so much? (┬┬﹏┬┬). My blog asking the question went unnoticed so I thought if people somehow missed it, maybe I should ask some one better rated than me to answer it. Am i violating any policy here? My intention was totally not to hijack someone else's blog.
•  » » 2 months ago, # ^ |   -8 the link is not working
 » 2 months ago, # |   +8 As an expert who is neither Russian, nor Chinese, nor American, I endorse this blog.In all seriousness though, great blog! I solved the Educational Round C the same way :clown:
 » 2 months ago, # |   +72 Great blog!I'd like to add that for team contests proving stuff is good because you have only 1 computer to code, so there's more time available that's not coding. Perhaps you can come up with some thesis for teams of 3 people :)Also my experience at Petrozavodsk camps tells me that russians actually do stuff like brutefoce, staring at small cases and pooping a guess and they're quite good at it.
 » 2 months ago, # | ← Rev. 3 →   -11 Interesting blog i upvoted
 » 2 months ago, # | ← Rev. 2 →   +15 As a Guesser i upvoted.
 » 2 months ago, # |   0 lol didn't expect to see PAC learning in a blog post on Codeforces
 » 2 months ago, # |   +107 Amazing level of shitposting!Or... at least I hope it's shitposting...
•  » » 2 months ago, # ^ |   +37 The author added their previous blog to the catalog. It appears they are serious about it...
•  » » » 2 months ago, # ^ |   +99 There are 5 of my blogs in the catalog. It proves nothing :)
•  » » 2 months ago, # ^ |   +38 Nooooo the legendary grandmaster of the light side has appeared...I think we both agree on half of this blog being trolling. I don't think we agree on which half. :)
 » 2 months ago, # |   0 Why you kicked 74TrAkToR,
•  » » 2 months ago, # ^ |   0 I didn't. He is an esteemed Grandmaster who inspired me on how to set Div. 1C in 5 minutes. :)
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 I think he most popular guy in cf after tourist and rainboy
 » 2 months ago, # |   0 Auto comment: topic has been updated by Zhtluo (previous revision, new revision, compare).
 » 2 months ago, # | ← Rev. 2 →   +25 Me and my friends call the following advanced technique R.B.S.Random Bullshit Submit
•  » » 2 months ago, # ^ |   0 Is it better than DP?
 » 2 months ago, # |   +77 What are you doing, just skip all problems without queries, they are all trash.
 » 2 months ago, # |   +37 why prove by AC when you can randomly guess the proof
 » 2 months ago, # |   0 no hate to the "go practice more problems" guys, but this is the sort of response id love to get to the question of "how to improve in cp". top cp guys sharing some of their general "heuristics" when it comes to thinking about a problem would be really helpful, while i also realize that these "heuristics" would also depend on the type of problem.
 » 2 months ago, # |   +21 Please prove what you've guessed. This is especially important for greedy problems where there are 5 plausible solutions, and only one of them is actually correct.
•  » » 2 months ago, # ^ |   +20 First I never really saw a problem that has 5 plausible greedy solutions...You don't need to prove the correct one. You just need to refute the incorrect ones with counter examples.Then you will get something which is probably correct, which imo is faster.
•  » » » 2 months ago, # ^ |   +11 As someone who is american but lacks the american implementation skill T_T proving can be helpful for me to avoid some paranoia that comes from getting wrong answer and not knowing if it is your code that is wrong or the solution that is wrong (or both)
•  » » » 2 months ago, # ^ |   +36 Proving makes you know how to come up with stuff. Proving in math is important not by accident.
•  » » » » 2 months ago, # ^ |   +4 Proving in math is important not by accident.Proving is important in a lot of areas. That has nothing to do with CP, though.Proving makes you know how to come up with stuff.I am not entirely convinced. Maybe you can write a blog on how to increase intuition by proving. I am sure I can benefit from it. :)
•  » » » » » 2 months ago, # ^ |   +6 Also added a counterexample in the blog to showcase that proving is inefficient and unrelated to implementation...
•  » » » » » » 2 months ago, # ^ |   +14 I don't really think the counterexample is good. Isn't the claim obviously true?
•  » » » » » » » 2 months ago, # ^ |   +5 I would also say what I guessed is obviously true :)But apparently saying obviously true is not proving...
•  » » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 the difference is that if you prove something, it is right, and if something feels obviously true, it is actually false 30% of the time :)
•  » » » » » » » » » 2 months ago, # ^ |   0 Indeed.That's when I apply thesis of Proof-by-AC and say unless the proof is short (1/2 of the coding time) we should just guess :)
•  » » » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   +28 For me, proving time is usually extremely short so I should prove it instead of guessing :)
•  » » » » » » » » » 2 months ago, # ^ |   0 That is why you are an esteemed grandmaster, presumably. :)Unfortunately, not everyone spends less time proving than coding..
•  » » » » » » » » » 2 months ago, # ^ |   0 If the original question is "how do we improve in CP" then guessing during practice is definitely less helpful than thinking through proofs. Surely we agree in this?
•  » » » » » » » » » 2 months ago, # ^ |   0 No. Why does knowing how to prove stuff help?
•  » » » » » » » » » 2 months ago, # ^ |   +18 Knowing how to prove stuff helps because you know what to guess and why it's true instead of randomly guessing something and hoping it works.
•  » » » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Sure. But on the other hand you can also practice 100 guesses and see where the counterexamples lie when you cannot find them to a wrong guess.Given that you are not really going to prove things in contests anyway, surely this is not a worse method?
•  » » » » » » » » » 2 months ago, # ^ |   -9 Nice. I guess you figured out what to do to become a grandmaster :)
•  » » » » » » » » » 2 months ago, # ^ |   0 I think that's more Div.2 advice though...I am bad at counting and yet to figure out how to count properly. Help me :/
•  » » » » » » » » » 6 weeks ago, # ^ |   0 cool , the tell me how to come up with a proof for this problem during contest.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   -8 Now I think you are right though , both are quite important
•  » » » » 2 months ago, # ^ |   0 I thought I made it pretty clear in the blog... :)
•  » » 2 months ago, # ^ |   -20 Better strategy for OI contests: Just implement all the 5 solutions, and whichever one gets AC is the correct one.
•  » » » 2 months ago, # ^ |   +21 Nice. You wasted 4/5 or 5/5 of your time implementing the wrong solutions. No time left!
•  » » » » 2 months ago, # ^ |   -10 Well, if you're skill issued like me, it's better than wasting a lot of time trying to find a proof, and then trying a Hail Mary submission at the end of the contest which gets AC.Also, sometimes the edit distance between greedy solutions is very small (e.g. sorting by second element vs sorting by first element, or iterating from left to right instead of right to left and so on), so it's pretty fast to implement all of them and check.
•  » » » » » 2 months ago, # ^ |   -10 I do agree with you though, if the two greedy solutions are something like "really bashy stuff with sets" vs "doing some cancer stuff with lazy segtree", then you should probably spend some time trying to distinguish which is the correct one, because if you get a WA, you might not understand what is incorrect, the idea or the implementation (as pointed out by omeganot above). But even in that case, you can try some obvious counterexamples by hand, and avoid proving (because I'm really skill issued, and I can't prove stuff).
•  » » » » 2 months ago, # ^ |   -15 Isn't skill more important then rating?
 » 2 months ago, # |   0 Auto comment: topic has been updated by Zhtluo (previous revision, new revision, compare).
 » 2 months ago, # |   +7 "It is not very obvious how to prove this."Maybe for you.....clearly i = (first occurence of m) — 1 works [except when m is also the first element, in which case i = (first occurence of something other than m) — 1 works]There are problems where proving is hard, i have also guessed solutions to some problems, 2 examples you gave are quite easy (1923C and the slimes problems). The only thing you needed further in 1923C is just make any 1 (no 1s is a trivial case) large enough to make the sum remain same.
•  » » 2 months ago, # ^ |   0 So true.But then you need another guess that taking the first m or non m works...I probably worked too much with Coq recently that my mind just jumped to induction orz.
•  » » » 2 months ago, # ^ |   0 how is it guess.....youre literallty calling everything guess now. the way i wrote it makes it clear the thought process as well.You notice that the first occurence of m nearly always works, except for one edge case, and there you get a similiar construction....
•  » » » » 2 months ago, # ^ | ← Rev. 4 →   0 Maybe you are red so you are not aware of this. But the issue is when you try to explain something to people in Div. 2, they will say it's not obvious at all. Like why should you, out of all things, start by looking at the first element that is m? To be honest, I didn't even start by seeing that, hence I didn't prove it that way.Also, the blog is not for red people, or Div.1 people, as far as I was writing (since I am not even red). I am explaining it in a way that Div.2 people can start guessing without taking care of these minutiae details, not that the particular proof is easy or not in some grandmaster's eyes which is irrelevant to them at all.P.S. I just found that your proof also thinking in a way that takes a logic leap first, and then fix the counterexample, which is exactly what I mean by guessing in my blog :)
•  » » » » » 2 months ago, # ^ |   +12 I'm a specialist and I can confirm that the proof is obvious.
•  » » » » » » 2 months ago, # ^ |   0 Given that if you can do ABCD you should be blue somehow I don't believe it's true...
•  » » » » » » » 2 months ago, # ^ |   +39 I also asked my mom and she agreed it was obvious.
•  » » » » » » » » 2 months ago, # ^ |   0 Do you mean 'it's obviously true' or do you mean 'it's obvious that we should consider the first m in the sequence to prove the statement'?I think we all agree on the first one. I am not so sure about the second one..
•  » » » » » » » » » 2 months ago, # ^ |   +8 He is trolling. He has been rank 2 in div3 round.
•  » » » » » » 2 months ago, # ^ |   0 You are also an IMO team member.
•  » » » » » » » 2 months ago, # ^ |   0 Wait this guy really has a math contest background.Noooo are we seeing another future esteemed grandmaster in making...The Russian-ness is strong with this one.
•  » » » » » » » » 2 months ago, # ^ |   0 He's probably around CM/Master skill already lol, but just trolling on contests
 » 2 months ago, # |   +70 I'd be cautious about applying this advice, especially if you're lower-level.Guessing works well if you have lots of experience and a strong intuition. Strong intuition is gained by working through things without taking shortcuts. If you try exploring some branch of CS or math that is unknown to you, I'm willing to bet that your intuition will mislead you a lot.
•  » » 2 months ago, # ^ |   +8 Strong intuition is gained by working through things without taking shortcuts.But why? I feel it's the contrary: learn how to guess helps with learning how to prove.I will put it this way: proof is a trial-and-error process from time to time. Guessing the right thing is like the trial/intuition part. Surely practicing one part isn't detrimental to the other part?
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by Zhtluo (previous revision, new revision, compare).
 » 6 weeks ago, # |   +24 On this person defense, todays contest Codeforces Global Round 25 problems A-E could've been solved just by pure guessing.
•  » » 6 weeks ago, # ^ |   +3 So true. I even gained rating :)To do F you also need to guess that you can greedily arrange things...
 » 3 weeks ago, # |   +8 I liked the blog, and I say as an expert that it helps me a lot, especially because I tend to get stuck in problems.But most of the time it's not a random guess (only when I'm out of ideas), but something that comes naturally by imagining the problem and making examples on paper, something related to intuition.And there's a skill that helps me a lot: knowing how to create good test cases. You can observe many things by simulating a good test case (in addition to avoiding WAs due to edge cases haha).