Balanced String
Contest: Educational Codeforces Round 153 (Rated for Div. 2)
Difficulty rating: 2200
Tags: dp

You are given a binary string $$$s$$$ (a binary string is a string consisting of characters 0 and/or 1).

Let's call a binary string balanced if the number of subsequences 01 (the number of indices $$$i$$$ and $$$j$$$ such that $$$1 \le i < j \le n$$$, $$$s_i=0$$$ and $$$s_j=1$$$) equals to the number of subsequences 10 (the number of indices $$$k$$$ and $$$l$$$ such that $$$1 \le k < l \le n$$$, $$$s_k=1$$$ and $$$s_l=0$$$) in it.

For example, the string 1000110 is balanced, because both the number of subsequences 01 and the number of subsequences 10 are equal to $$$6$$$. On the other hand, 11010 is not balanced, because the number of subsequences 01 is $$$1$$$, but the number of subsequences 10 is $$$5$$$.

You can perform the following operation any number of times: choose two characters in $$$s$$$ and swap them. Your task is to calculate the minimum number of operations to make the string $$$s$$$ balanced.

Input format:
The only line contains the string $$$s$$$ ($$$3 \le |s| \le 100$$$) consisting of characters 0 and/or 1.

Additional constraint on the input: the string $$$s$$$ can be made balanced.

Output format:
Print a single integer — the minimum number of swap operations to make the string $$$s$$$ balanced.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, the string is already balanced, the number of both 01 and 10 is equal to $$$1$$$.

In the second example, the string is already balanced, the number of both 01 and 10 is equal to $$$6$$$.

In the third example, one of the possible answers is the following one: 11010 $$$\rightarrow$$$ 01110. After that, the number of both 01 and 10 is equal to $$$3$$$.

In the fourth example, one of the possible answers is the following one: 11001100 $$$\rightarrow$$$ 11001010 $$$\rightarrow$$$ 11000011. After that, the number of both 01 and 10 is equal to $$$8$$$.

Example input:
101

Example output:
0

Example input:
1000110

Example output:
0

Editorial:
Let's calculate the following dynamic programming: $$$dp_{i, cnt0, cnt01}$$$ — the minimum number of changes in string $$$s$$$ if we consider only $$$i$$$ first characters of it, the number of characters 0 on that prefix is $$$cnt0$$$, and the number of subsequences 01 on that prefix is equal to $$$cnt01$$$.
The transitions are pretty simple. Let's look at the transitions according to the character we are trying to place at the next position:
• if it is 0, then there is transition from the state $$$(i, cnt0, cnt01)$$$ to the state $$$(i + 1, cnt0 + 1, cnt01)$$$ and the value of $$$dp$$$ depends on $$$s_i$$$ (the value stays the same if $$$s_i=0$$$, and increases by $$$1$$$ otherwise);
• if it is 1, then there is transition from the state $$$(i, cnt0, cnt01)$$$ to the state $$$(i + 1, cnt0, cnt01 + cnt0)$$$, and the value of $$$dp$$$ depends on $$$s_i$$$ (the value stays the same if $$$s_i=1$$$ and increases by $$$1$$$ otherwise).
So, this dynamic programming works in $$$O(n^4)$$$.
It remains us to get the answer to the problem from that dynamic programming. It is stored in $$$dp_{n, cnt0, need}$$$, where $$$cnt0$$$ is equal to the number of characters 0 in the string $$$s$$$, and $$$need=\frac{cnt0 \cdot cnt1}{2}$$$ (because the number of subsequences 01 should be equal to the number of subsequences 10). But our dynamic programming stores the number of changes in the string, and the problems asks for the minimum number of swaps. However, we can easily get it from the $$$dp$$$ value. Since the amounts of zeroes and ones are fixed in the string, then the number of changes from 0 to 1 equals to the number of changes from 1 to 0 and we can pair them up. So, the answer to the problem is the half of the $$$dp$$$ value.