Communism
Contest: Codeforces Global Round 12
Difficulty rating: 3500
Tags: bitmasks, dp, trees

Please pay attention to the unusual memory limit in this problem.

In a parallel universe, Satan is called "Trygub". For that reason, the letters of his namesake were deleted from the alphabet in ancient times.

The government has $$$n$$$ workers standing in a row and numbered with integers from $$$1$$$ to $$$n$$$ from left to right. Their job categories can be represented as a string $$$s$$$ of length $$$n$$$, where the character $$$s_i$$$ represents the job category of the $$$i$$$-th worker.

A new law will be approved to increase the equality between the workers. The government decided to make everyone have the same job category by performing the following operation any number of times (possibly zero).

There is a fixed rational parameter $$$k=\frac ab$$$ describing how easy it is to convince the public, and it will be used to determine the success of an operation.

In an operation, the government first selects a job category $$$x$$$ with at least one worker at the current moment. Suppose $$$i_1,\ldots, i_m$$$ ($$$i_1<\ldots<i_m$$$) are the positions of all the workers with job category $$$x$$$. If $$$k\cdot (i_m-i_1+1)\le m$$$, the government is able to choose any job category $$$y$$$ with at least one worker at the current moment and change the job category of all workers with job category $$$x$$$ to job category $$$y$$$.

If it is possible to make all workers have job category $$$x$$$, we say that $$$x$$$ is obtainable. Can you tell the government the set of obtainable job categories?

Input format:
The first line contains three integers $$$n, a, b$$$ ($$$1 \le n \le 5000$$$, $$$1\le a\le b\le 10^5$$$) — the number of workers and the numerator and denominator of the parameter $$$k$$$, respectively.

The second line contains a string $$$s$$$ of length $$$n$$$, consisting of lowercase English characters — the job categories of each worker. The characters 't', 'r', 'y', 'g', 'u', and 'b' do not appear in the string $$$s$$$.

Output format:
Print an integer $$$c$$$ equal to the number of obtainable job categories followed by $$$c$$$ space-separated characters — the obtainable job categories sorted in the lexicographical order.

Constraints:
Time limit: 1.5 s
Memory limit: 32.0 MB

Note:
The first operation must select the job category 'i' because all other job categories cannot satisfy the condition, therefore 'i' is not obtainable.

Below is showed how to obtain 'c', 'm', and 'o'. The square brackets denote the segment containing all workers of the selected category, the red color denotes this category and the blue color denotes the new category after the change.

- Get 'c':   ($$$\texttt{com}\color{red}{\texttt{[i]}}\texttt{com} \rightarrow \texttt{com}\color{#1E90FF}{\texttt{[o]}}\texttt{com}$$$)  ($$$\texttt{c}\color{red}{\texttt{[o}}\texttt{m}\color{red}{\texttt{o}}\texttt{c}\color{red}{\texttt{o]}}\texttt{m} \rightarrow \texttt{c}\color{#1E90FF}{\texttt{[m}}\texttt{m}\color{#1E90FF}{\texttt{m}}\texttt{c}\color{#1E90FF}{\texttt{m]}}\texttt{m}$$$)  ($$$\texttt{c}\color{red}{\texttt{[mmm}}\texttt{c}\color{red}{\texttt{mm]}} \rightarrow \texttt{c}\color{#1E90FF}{\texttt{[ccc}}\texttt{c}\color{#1E90FF}{\texttt{cc]}}$$$)
- Get 'm':   ($$$\texttt{com}\color{red}{\texttt{[i]}}\texttt{com} \rightarrow \texttt{com}\color{#1E90FF}{\texttt{[o]}}\texttt{com}$$$)  ($$$\texttt{c}\color{red}{\texttt{[o}}\texttt{m}\color{red}{\texttt{o}}\texttt{c}\color{red}{\texttt{o]}}\texttt{m} \rightarrow \texttt{c}\color{#1E90FF}{\texttt{[c}}\texttt{m}\color{#1E90FF}{\texttt{c}}\texttt{c}\color{#1E90FF}{\texttt{c]}}\texttt{m}$$$)  ($$$\color{red}{\texttt{[cc}}\texttt{m}\color{red}{\texttt{ccc]}}\texttt{m} \rightarrow \color{#1E90FF}{\texttt{[mm}}\texttt{m}\color{#1E90FF}{\texttt{mmm]}}\texttt{m}$$$)
- Get 'o':   ($$$\texttt{com}\color{red}{\texttt{[i]}}\texttt{com} \rightarrow \texttt{com}\color{#1E90FF}{\texttt{[c]}}\texttt{com}$$$)  ($$$\color{red}{\texttt{[c}}\texttt{om}\color{red}{\texttt{cc]}}\texttt{om} \rightarrow \color{#1E90FF}{\texttt{[m}}\texttt{om}\color{#1E90FF}{\texttt{mm]}}\texttt{om}$$$)  ($$$\color{red}{\texttt{[m}}\texttt{o}\color{red}{\texttt{mmm}}\texttt{o}\color{red}{\texttt{m]}} \rightarrow \color{#1E90FF}{\texttt{[o}}\texttt{o}\color{#1E90FF}{\texttt{ooo}}\texttt{o}\color{#1E90FF}{\texttt{o]}}$$$)

Example input:
7 1 2
comicom

Example output:
3 c m o

Editorial:
Let $$$C$$$ denote the set of distinct characters in $$$s$$$.
Suppose there is a sequence of operations that transforms every character to $$$x$$$ in the end. For an operation where we transform all occurrences of $$$y$$$ to $$$z$$$, let's add a directed edge $$$(y\to z)$$$. The resulting structure is a directed tree rooted at $$$x$$$. This is because every character except $$$x$$$ is transformed exactly once.
For each character $$$y$$$, denote the index of its first occurrence by $$$l_y$$$ and its last occurrence by $$$r_y$$$. For any non-empty subset $$$S$$$ of characters, define $$$\mathrm{range}(S)=\left[\min\limits_{y\in S} l_y, \max\limits_{y\in S} r_y\right]$$$. That is, the smallest interval capturing all occurrences of characters belonging to $$$S$$$. Also define $$$\mathrm{cnt}(S)$$$ as the number of occurrences of characters in $$$S$$$.
Given a directed tree structure, we can decide its validity regardless of the order of operations. For a character $$$y$$$, let $$$S_y$$$ denotes the set of characters in the subtree of $$$y$$$. The condition is that for every character $$$y$$$,
$$$$$$ \mathrm{cnt}(S_y)\ge k \left|\mathrm{range}(S_y)\right|.\tag{1} $$$$$$
Now, we can devise a bitmask dp. For any subset $$$M$$$, let $$$\mathrm{dp}(M)$$$ be true if we can organize the characters of $$$M$$$ into a valid tree rooted at a character outside of $$$M$$$. Then the final answer will be the set of characters $$$x$$$ such that $$$\mathrm{dp}(C\setminus \{x\})$$$ is true.
To create the dp transitions, there are $$$2$$$ cases.
1. Choose a character $$$y\in M$$$ to be an ancestor of all of $$$M$$$. That is, if the condition $$$(1)$$$ holds for the set $$$M=S_y$$$ and $$$\mathrm{dp}(M\setminus \{y\})$$$ is true, then $$$\mathrm{dp}(M)$$$ is true.
2. The set $$$M$$$ should be split into at least two disjoint subtrees. That is, if there is a non-empty, proper subset $$$S\subset M$$$ such that $$$\mathrm{dp}(S)$$$ and $$$\mathrm{dp}(M\setminus S)$$$ are true, then $$$\mathrm{dp}(M)$$$ is also true.
These transitions give rise to an $$$O(n+3^{|C|})$$$ solution, since we iterate over all subsets of $$$M$$$ in case 2. We still need another observation to optimize this further. The key observation is that we may assume for the transitions of case 2 that $$$\mathrm{range}(S)\cap \mathrm{range}(M\setminus S)=\emptyset$$$. That is, the sets of characters in sibling subtrees occur on disjoint intervals.
To prove that this assumption is justified, we show that a valid tree can be transformed to a valid tree that does satisfy our assumption.
Suppose there are two siblings $$$y$$$ and $$$z$$$ whose subtrees have overlapping ranges. Then if we change $$$z$$$'s parent to $$$y$$$, we only need to check that the condition $$$(1)$$$ still holds for $$$y$$$. In fact,
$$$$$$ \mathrm{cnt}(A\cup \{y\}\cup B\cup \{z\})= \mathrm{cnt}(A\cup \{y\})+\mathrm{cnt}(B\cup\{z\})$$$$$$
$$$$$$\ge k \cdot \left|\mathrm{range}(A\cup \{y\})\right| + k\cdot \left|\mathrm{range}(B\cup \{z\})\right|\ge k\cdot \left|\mathrm{range}(A\cup \{y\}\cup B\cup \{z\})\right|.$$$$$$
Of course, after the transformation in the figure, maybe our assumption still does not hold. But observe that if we repeat this process, it will stop in finitely many steps. This is because the sum of depths of all nodes strictly increases with each transformation, and the depth of a node is bounded by $$$|C|$$$.
Now that the claim is proven, it is not hard to improve our solution to $$$O(n+|C|2^{|C|})$$$. If we sort the characters in $$$C$$$ by the index of their first occurrence, it is sufficient to try only $$$|C|-1$$$ splits according to this order for case 2. That is, if the characters in $$$M$$$ are ordered $$$c_1,\ldots, c_m$$$, then we should take $$$S=\{c_1,\ldots,c_i\}$$$ for some $$$i$$$.