Official

A - Antichain of Integer Strings Editorial by evima

For a positive integer \(x\), let \(f(x)\) defined as follows:

  • \(f(x)\) is the smallest \(y>x\) such that \(x\) is a substring of \(y\) in decimal representation.

[1] Computing \(f(x)\) and its increasingness

When \(x\) has \(n\) digits, \(f(x)\) has \(n + 1\). By considering the cases in which \(x\) is a prefix of \(f(x)\) and a suffix of \(f(x)\), we see that \(f(x) = \min\{10^n+x,10x\}\).

Additionally, since both \(10^n+x\) and \(10x\) are strictly increasing on \(x\), we see that \(f\) is also strictly increasing.

[2] Constructing a solution and proving its optimality

Let \(A = \{L\leq x\leq R\mid f(x) > R\}\) and let us show that it is a good set with the maximum number of elements. From the definition of \(f(x)\), we see that \(A\) is a good set.

Now, let us show that \(A\) has the maximum number of elements among the good sets. Consider the directed graph defined as follows.

  • The vertex set is the integers between \(L\) and \(R\).
  • There is a directed edge from \(x\) to \(f(x)\) when \(L\leq x\leq R\) and \(f(x) \leq R\).

This graph is a DAG (Directed Acyclic Graph). Additionally, the in-degree and out-degree of any vertex are at most \(1\) (the out-degree being at most \(1\) follows from the strict increasingness of \(f\)).

Thus, this directed graph decomposes into some vertex-disjoint paths. For any two vertices on the same path, one is a substring of the other, so a good set contains at most one vertex on the same path. Therefore, the number of paths gives an upper bound for the number of elements in a good set.

On the other hand, the good set \(A\) defined above is the set of the last vertices of the paths in this graph. Thus, it achieves the upper bound ― the number of paths ― and is optimal.

[3] Computing the answer

Eventually, we have seen that finding the number of elements in \(A = \{L\leq x\leq R\mid f(x) > R\}\) solves the problem. Since \(f\) is strictly increasing, we can find the answer by binary search (or compute it more directly).

By summarizing the above, the problem can be solved in \(O(\log^2 R)\) time (for example) per test case.

[4] Reference: Connection between chains and antichains (Dilworth’s theorem)

For a finite ordered set \(S\), consider the following:

  • \(A\subset S\) is an antichain when no two distinct elements in \(A\) are comparable.
  • \(A\subset S\) is a chain when every two distinct elements in \(A\) are comparable.

When defining an order in \(\{L, \ldots, R\}\) by the substring relation, we can see the problem as finding the maximum number of elements in an antichain.

In our proof in [2], we proved the optimality of an antichain \(A\) by constructing a cover of \(S\) consisting of \(|A|\) chains. It is known that such a pair of an antichain and a cover by chains always exists, which is a fundamental method in finding the largest antichain or proving it to be the largest.

Dilworth’s theorem: The maximum number of elements in an antichain in \(S\) equals the minimum number of chains required to cover \(S\).

posted:
last update: