All You Need is Randomly Guessing — How to Improve at Codeforces

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 Codeforces grandmaster

Therefore, in this blog I will explore an alternative technique — randomly guessing — that is looked down by everyone 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:

#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:

      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...

#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.

      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.