Official

B - L Partition Editorial by evima

Hints → https://atcoder.jp/contests/arc190/editorial/11918

[1] Restating the problem

There are at most four ways to place an L-shape of level \(N\), each occupying either the top or bottom row and the leftmost or rightmost column. In the order \(k = N, N-1, \ldots\), the set of cells covered by L-shapes of level \(k\) or lower form a \(k \times k\) square. Sorting out these facts, the partitioning into L-shapes can be restated as follows:

A partition into L-shapes corresponds to choosing chains of intervals \([1,N]=I_N\supsetneq \cdots \supsetneq I_1\) and \([1,N]=J_N\supsetneq \cdots \supsetneq J_1\) one by one (where \(I_i\) and \(J_i\) each consist of \(i\) consecutive integers). In this choice, \(I_k \times J_k\) is covered by L-shapes of level \(k\) or lower.

We want to count the partitions in which \((a,b)\) is contained in the level-\(k\) L-shape. Instead of counting that directly, we will count the partitions for which \((a,b)\) is contained in an L-shape of level at most \(k\), and then take the difference. Hence, the main problem becomes:

Find the number of pairs of chains of intervals \([1,N]=I_N\supsetneq \cdots \supsetneq I_1\) and \([1,N]=J_N\supsetneq \cdots \supsetneq J_1\) such that \((a,b) \in I_k \times J_k\) (here, \(I_i\) and \(J_i\) each consist of \(i\) consecutive integers).

Because the vertical direction and the horizontal direction factor out independently, it suffices to solve the following simpler problem:

Find the number of chains of intervals \([1,N]=I_N\supsetneq \cdots \supsetneq I_1\) and \([1,N]=J_N\supsetneq \cdots \supsetneq J_1\) such that \(a\in I_k\) (here, \(I_i\) consists of \(i\) consecutive integers).

[2] Counting

Let \(c_k\) be the number of chains such that \(I_N \supsetneq \cdots \supsetneq I_k \ni a\).

Such a chain also satisfies \(I_N \supsetneq \cdots \supsetneq I_{k+1} \ni a\), so \(c_k\) can be computed by subtracting from \(2 c_{k+1}\) those chains that satisfy the following:

  • \(I_N\supsetneq \cdots \supsetneq I_{k+1}\supsetneq I_k\), \(a\in I_{k+1}\), and \(a\notin I_k\).

Thus, \(c_k\) can be computed by subtracting from \(2 c_{k+1}\) an appropriate binomial coefficient. Hence, we can compute \(c_N, \ldots, c_1\) all together in \(O(N)\) time.

This computation can also be derived by reinterpreting it as the problem of calculating \(\sum_{a\leq i\leq b}\binom{k}{i}\) for \(k = 1,2,\ldots,N\).

posted:
last update: