CF2144F Bracket Groups Solution

介绍一个随机化做法。

首先有 $\texttt{()}$ 的情况必然不合法。

接下来我们声称，其他情况必然有解，且 $m \leq 2$。证明如下，我们构造两个长度为 $k$ 的括号序列 $\texttt{(((\dots)))}$ 和 $\texttt{()()\dots()()}$，容易发现同时作为两者子串的只有 $\texttt{()}$，所以我们的猜想是正确的。

所以我们只需要考虑是否存在 $m=1$ 的解。我不太会串串，所以考虑直接随出来一些合法的括号序列，判定它们是否合法。若全部失败，我们直接构造 $m=2$ 的解。感性理解一下，在本题的数据范围下，该做法较难被卡掉。