CF1658F Juju and Binary String

The cuteness of a binary string is the number of $ \texttt{1} $ s divided by the length of the string. For example, the cuteness of $ \texttt{01101} $ is $ \frac{3}{5} $ . Juju has a binary string $ s $ of length $ n $ . She wants to choose some non-intersecting subsegments of $ s $ such that their concatenation has length $ m $ and it has the same cuteness as the string $ s $ . More specifically, she wants to find two arrays $ l $ and $ r $ of equal length $ k $ such that $ 1 \leq l_1 \leq r_1 < l_2 \leq r_2 < \ldots < l_k \leq r_k \leq n $ , and also: - $ \sum\limits_{i=1}^k (r_i - l_i + 1) = m $ ; - The cuteness of $ s[l_1,r_1]+s[l_2,r_2]+\ldots+s[l_k,r_k] $ is equal to the cuteness of $ s $ , where $ s[x, y] $ denotes the subsegment $ s_x s_{x+1} \ldots s_y $ , and $ + $ denotes string concatenation. Juju does not like splitting the string into many parts, so she also wants to minimize the value of $ k $ . Find the minimum value of $ k $ such that there exist $ l $ and $ r $ that satisfy the constraints above or determine that it is impossible to find such $ l $ and $ r $ for any $ k $ .

N/A

N/A

In the first example, the cuteness of $ \texttt{0011} $ is the same as the cuteness of $ \texttt{01} $ . In the second example, the cuteness of $ \texttt{11000011} $ is $ \frac{1}{2} $ and there is no subsegment of size $ 6 $ with the same cuteness. So we must use $ 2 $ disjoint subsegments $ \texttt{10} $ and $ \texttt{0011} $ . In the third example, there are $ 8 $ ways to split the string such that $ \sum\limits_{i=1}^k (r_i - l_i + 1) = 3 $ but none of them has the same cuteness as $ \texttt{0101} $ . In the last example, we don't have to split the string.