Official

B - Three Sequences Editorial by evima

Hints: https://atcoder.jp/contests/arc211/editorial/14696

When \(X=Y\)

\(\max(\max(S_1),\max(S_2),\max(S_3))=0\) is achievable.

  • \(S_1\): a sequence consisting of \(X\) \(0\)s
  • \(S_2\): a sequence consisting of \(Z\) \(0\)s
  • \(S_3\): a sequence consisting of \(Z\) \(0\)s

satisfies the conditions. Clearly, the length constraints are also satisfied.

When \(X\lt Y\)

If we observe by adjusting the lengths appropriately, we can see that \(\max(\max(S_1),\max(S_2),\max(S_3))=0\) is not achievable.

\(\max(\max(S_1),\max(S_2),\max(S_3))=1\) is always achievable. This can be constructed in multiple ways. We show two solutions, and in both cases, it is easy to verify that the length constraints are satisfied.

Writer’s solution

  • \(S_1\): a sequence concatenating \(X\) \(1\)s and \(Y\) \(0\)s in this order
  • \(S_2\): a sequence consisting of \(Z\) \(1\)s
  • \(S_3\): a sequence concatenating \(Y\) \(0\)s and \(Z\) \(1\)s in this order

satisfies the conditions.

Admin/Tester’s solution

  • \(S_1\): a sequence concatenating \(X\) \(0\)s and \(Y-X\) \(1\)s in this order
  • \(S_2\): a sequence consisting of \(Z\) \(0\)s
  • \(S_3\): a sequence concatenating \(Z\) \(0\)s and \(Y-X\) \(1\)s in this order

satisfies the conditions. (With this solution, you don’t need to case-split for \(X=Y\), so it might be easier. Though it’s a minor difference.)

Implementation Example (Python (Codon 0.19.3), 27ms)

X, Y, Z = [int(i) for i in input().split()]

if X == Y:
    print(X, " ".join(["0"] * X))
    print(Z, " ".join(["0"] * Z))
    print(Z, " ".join(["0"] * Z))

else:
    print(X + Y, " ".join(["1"] * X + ["0"] * Y))
    print(Z, " ".join(["1"] * Z))
    print(Y + Z, " ".join(["0"] * Y + ["1"] * Z))

Bonus!: Let \(X\) be the maximum value of the length of sequences that can be output. When the output format is correct, create an output validator that definitely returns the correct judgment result with computational complexity \(O(X^2)\).

Explanation of Bonus! Solve three times the problem of finding the maximum length of common contiguous subsequences when there are strings \(S\) and \(T\).

Let \(DP[i][j]\) be “the number of matching characters from the \(i\)-th character onward of \(S\) and the \(j\)-th character onward of \(T\)”. This can be updated in reverse order of \(j\), and in reverse order of \(i\) when \(j\) is the same. The maximum of these values is the value we seek. The space complexity is \(O(X^2)\).

Also, it can be proven that the same computational complexity can be achieved by enumerating all pairs of starting points and naively finding the maximum value only when the character one position before does not match. In this case, the space complexity is \(O(X)\).

In the actual output validator, (because I didn’t notice the above solution until it was pointed out for some reason) it uses Z Algorithm (link to paladin8’s blog) by enumerating one endpoint. Although the constant factor is slightly worse, this also achieves space complexity \(O(X)\). Z Algorithm is a very interesting algorithm.

posted:
last update: