1
$\begingroup$

A binary string is given to us and we need to find number of awesome substring of that string .Definition of awesome string : A string is awesome if its length is divisible by number of 1's in it.

For example :111 has 6 awesome substrings.01010 has 10 awesome substrings .In "01010" one such awesome substring is "1010" because "1010" is substring of "01010" and 4(length of substring) is divisible by 2(number of 1's).

source : codeforces

My attempt : I was not able to come with solution better than O($n^2$) , however when i read the editorial they have did some optimization and solved it in O($n*n^{1/2}$) but i didn't understood it completely.

What and why i want to ask : I want some simpler explanation of same solution , maybe illustrating it by taking few example(s) . I love these type of questions and i really want to improve myself.

source of solution/editorial : solution (scroll down a little) .

I am open to any suggestions and comments .

$\endgroup$
0
$\begingroup$

Could you please explain exactly where you were stuck? Anyway, I'll choose some parts of the solution which were not described by author and shed light on them.

You can assume that $T=\sqrt{n}$ in the solution. The main idea can be formulated as follows:

For any positive integers $m, n$ such that $m \le n$ either $m \le \sqrt{n}$ or $\frac{n}{m} < \sqrt{n}$.

This is applied to all substrings where $m$ is the number of ones. It means that we can divide all substrings into two disjoint sets: where the length divided by number of ones is small (set $k= \frac{len}{m}$, then $k \leq \frac{n}{m} < \sqrt{n}$), or the number of ones is small ($m \leq \sqrt{n}$). Then we compute sizes of each set separately. When we apply such idea, we hope that each of these subtasks can be solved faster than a big one.

For the first set, I find the idea of computing $t[i]=i-k\cdot{}pref[i]$ well-explained.

For the second set, if we fix $l$, we can break segments of $r$'s into segments $[r_m, r_{m+1})$ for which the number of ones in substring $s_l \ldots{} s_r$ equals $m$. We consider only $m\leq \sqrt{n}$, and for each $m$ the number of suitable $r$'s can be found in $O(1)$. Note: the set of such $r$'s forms an arithmetic progression with a common difference $m$.

And, if we iterate over $l$ in descending order, we can also make a "structure" for recomputing these segments in $O(1)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy