Guessforces Bestforces --- How I Guessed My Way to GM
Разница между en1 и en2, 67 символ(ов) изменены
# Guessforces Bestforces — How I Guessed My Way to GM↵

![Screenshot](https://zhtluo.com/cp/img/guessforces-bestforces/screenshot.png)↵

*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.me/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.me/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 &mdash; Fenwick Tree](https://codeforces.me/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.me/blog/entry/129027) skipped the proof!↵
</spoiler>↵

## [1965C &mdash; Folding Strip](https://codeforces.me/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.me/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...↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Zhtluo 2024-05-26 03:48:13 67
en1 Английский Zhtluo 2024-05-26 03:36:08 3301 Initial revision (published)