↵
↵
*It turns out that randomly guessing works in Div. 1 too...*↵
↵
I have reached GM thanks to **randomly guessing**. **Ask me anything!**↵
↵
Since I have already argued in theory [how randomly guessing helps CF rating](https://codeforces.net/blog/entry/12687), I figured that I might as well compile a list of problems I guessed on my way to GM, to give some empirical evidence to all esteemed grandmasters before my rating falls off. So let us get started!↵
↵
## [1975D — Paint the Tree](https://codeforces.net/contest/1975/problem/D)↵
↵
*Just solve the problem manually and claim it is the best solution.* Surely *it is.*↵
↵
<spoiler summary="Spoiler">↵
After playing a bit with the two pieces I found that I always make them collide.↵
↵
Fortunately, it suffices to randomly guess that the red piece and the blue piece will first travel to meet each other and then traverse the tree.↵
↵
I still have no idea why it is the optimal solution.↵
</spoiler>↵
↵
## [1967C — Fenwick Tree](https://codeforces.net/contest/1967/problem/C)↵
↵
*Have you ever played the game 'find next number in the sequence?'*↵
↵
<spoiler summary="Spoiler">↵
After writing out the expression for a few terms, just randomly guess that the coefficient is $\binom{k+i}{i}$.↵
↵
Even the [tutorial](https://codeforces.net/blog/entry/129027) skipped the proof!↵
</spoiler>↵
↵
## [1965C — Folding Strip](https://codeforces.net/contest/1965/problem/C)↵
↵
*- Just fold whenever you can!*↵
↵
*- Wait. What if I get stuck somewhere...*↵
↵
*- Well... You can always randomly guess that you will never get stuck! Surely that works. Source: Trust me bro*↵
↵
<spoiler summary="Spoiler">↵
Have you ever written code that you cannot explain?↵
↵
Well, I have:↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
int T;↵
int N;↵
char str[210000];↵
char fold[420000];↵
char *p_fold = fold + 210000;↵
↵
int main() {↵
scanf("%d", &T);↵
while (T--) {↵
scanf("%d", &N);↵
scanf(" %s", str);↵
std::fill(p_fold - N - 1, p_fold + N + 1, (char)0);↵
int cur = 0, cur_dir = 1;↵
int min = 0, max = 0;↵
for (int i = 0; i < N; ++i) {↵
p_fold[cur] = str[i];↵
min = std::min(min, cur);↵
max = std::max(max, cur);↵
if (i + 1 == N) break;↵
if (str[i + 1] == str[i]) {↵
cur_dir = -cur_dir;↵
} else {↵
cur += cur_dir;↵
}↵
}↵
printf("%d\n", max - min + 1);↵
}↵
}↵
```↵
↵
I still only vaguely know why it is correct... Good thing that Codeforces is not math but *Guessforces*.↵
</spoiler>↵
↵
### [1951](https://codeforces.net/contest/1951)↵
↵
*By now you have seen many problems that can be randomly guessed. But have you seen an entire contest that can be randomly guessed?*↵
↵
<spoiler summary="Spoiler">↵
Every problem from A to E is randomly guessing...↵
↵
Most notably:↵
↵
- D: Randomly guess that only $n$ and $[0, n/2]$ is 'Yes.'↵
↵
- E: Randomly guess that you only need to divide the string into two parts.↵
</spoiler>↵
↵
### I will probably add more to the list...↵
