↵
_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
↵
## Example 1↵
↵
I will start by using an example to demonstrate my thought process. This problem [1923C](https://codeforces.net/contest/1923/problem/C) 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**:
↵
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](https://codeforces.net/blog/entry/126310), 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:↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
int main() {↵
int T;↵
scanf("%d", &T);↵
while (T--) {↵
int N, Q;↵
static int C[310000];↵
static long long cnt[310000], sum[310000];↵
scanf("%d%d", &N, &Q);↵
for (int i = 0; i < N; ++i)↵
scanf("%d", &C[i]);↵
for (int i = 0; i < N; ++i)↵
cnt[i + 1] = cnt[i] + (C[i] == 1);↵
for (int i = 0; i < N; ++i)↵
sum[i + 1] = sum[i] + C[i];↵
for (int i = 0; i < Q; ++i) {↵
int l, r;↵
scanf("%d%d", &l, &r), --l, --r;↵
long long c = cnt[r + 1] - cnt[l];↵
long long s = sum[r + 1] - sum[l];↵
if (s - (r - l + 1) >= c)↵
puts("YES");↵
else↵
puts("NO");↵
}↵
}↵
}↵
```↵
↵
Then it WAs on the sample... Fortunately by looking at the sample I see that I missed a trivial edge case where the length os the subarray is $1$ . This is quickly fixable:↵
↵
```cpp↵
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,↵
↵
**
↵
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](https://codeforces.net/contest/1923/problem/D), 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...↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
int main() {↵
int T;↵
scanf("%d", &T);↵
while (T--) {↵
int N;↵
static int A[310000];↵
static long long sum[310000], eq[310000];↵
scanf("%d", &N);↵
for (int i = 0; i < N; ++i)↵
scanf("%d", &A[i]);↵
for (int i = 0; i < N; ++i)↵
sum[i + 1] = sum[i] + A[i];↵
for (int i = 0; i < N; ++i)↵
eq[i + 1] = eq[i] + (A[i] != A[i + 1]);↵
for (int i = 0; i < N; ++i) {↵
int ans1 = N + 1, ans2 = N + 1;↵
{↵
int l = 0, r = i - 1;↵
while (l <= r) {↵
int m = l + r >> 1;↵
if (sum[i] - sum[m] > A[i] &&↵
(i - 1 == m || eq[i - 1] - eq[m] != 0)) {↵
ans1 = i - m;↵
l = m + 1;↵
} else {↵
r = m - 1;↵
}↵
}↵
}↵
{↵
int l = i + 1, r = N - 1;↵
while (l <= r) {↵
int m = l + r >> 1;↵
if (sum[m + 1] - sum[i + 1] > A[i] &&↵
(m == i + 1 || eq[m] - eq[i + 1] != 0)) {↵
ans2 = m - i;↵
r = m - 1;↵
} else {↵
l = m + 1;↵
}↵
}↵
}↵
int ans = std::min(ans1, ans2);↵
if (ans == N + 1) {↵
printf("-1%c", " \n"[i + 1 == N]);↵
} else {↵
printf("%d%c", ans, " \n"[i + 1 == N]);↵
}↵
}↵
}↵
}↵
```↵
↵
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.↵
↵
```cpp↵
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.↵
↵
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](https://en.wikipedia.org/wiki/Deductive_reasoning).** This is the most rigorous form of logic, the one you will encounter the most in modal solutions.↵
↵
2. **[Induction](https://en.wikipedia.org/wiki/Inductive_reasoning).** 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.](https://codeforces.net/blog/entry/124045).↵
↵
3. **[Abduction](https://en.wikipedia.org/wiki/Abductive_reasoning), 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](https://en.wikipedia.org/wiki/Probably_approximately_correct_learning):↵
↵
**(Claim of PAC Learning, from [UPenn](https://www.cis.upenn.edu/~danroth/Teaching/CS446-17/LectureNotesNew/colt/main.pdf)): The probability that there exists a hypothesis $h \in H$ that is consistent with $m$ examples and satisfies $\textrm{Error}(h) > \epsilon$ is less then $|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](https://codeforces.net/contest/1930/problem/C), 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:↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
const int INF = 2E9;↵
int A[310000];↵
↵
int main() {↵
int T;↵
scanf("%d", &T);↵
while (T--) {↵
int N;↵
scanf("%d", &N);↵
for (int i = 0; i < N; ++i)↵
scanf("%d", &A[i]), A[i] += i + 1;↵
std::sort(A, A + N);↵
int upp = INF;↵
std::vector<int> ans;↵
for (int i = N - 1; i >= 0; --i) {↵
if (A[i] < upp) {↵
ans.push_back(A[i]);↵
upp = A[i];↵
} else {↵
ans.push_back(upp - 1);↵
upp = upp - 1;↵
}↵
}↵
for (int i = 0; i < (int)ans.size(); ++i) {↵
printf("%d%c", ans[i], " \n"[i + 1 == ans.size()]);↵
}↵
}↵
}↵
```↵
↵
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.*↵
↵
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!↵
