Virtual_Contestant's blog

By Virtual_Contestant, history, 4 years ago, In English

Can anyone please explain the solution for this problem? I have looked at multiple solutions and editorial but unable to understand from them. Thanks a lot. https://codeforces.com/problemset/problem/804/B

| Write comment?
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

e.g Let's consider aabb. shifting the rightmost 'a' to the end of the string will take two operations but it will double the number of b's (abbbba) then shifting the leftmost 'a' past the b's will cost the new number of b's but also increase the new number of b's by two (bbbbbbbbaa). from this we can see that it's a geometric progression with common ratio of 2, geometric sum formular is $$$\frac{a(r^2-1)}{(r-1)}$$$ where a is the first term and r is the common ratio. so we can just apply this : $$$\frac{b_{c}(a_{c}^2-1)}{(2-1)}$$$ == $$$b_{c}(a_{c}^2-1)$$$ to find answer of a substring of form aaaa.....aabbbb....bb. where $$$a_{c}$$$ and $$$b_{c}$$$ are the count of a's and b's respectively.

Code