A2: Perfectly Balanced — Chapter 2

Let me give it a try. I'll assume you have solved A1.

Let's say you want to check if A[l..r] is perfectly balanced. In A1 there were only different kinds of element, so we could just compare each element's frequency in A[l..m] and A[m+1..r]. But in A2 there are different kinds of element, so we can no longer use this method.

Instead of comparing each element's frequency, one might come up with this idea: "what about comparing the sum of elements in A[l..m] and A[m+1..r]?". For example, if A[l..r] was [1, 2, 3, 2, 1, 3], left sum is and right sum is . Both sums are equal, and [1, 2, 3, 2, 1, 3] is indeed perfectly balanced! But if you are given [1, 3, 2, 2], both sums are equal to , but it's not perfectly balanced. Here you can't distinguish between and .

This situation is very analogous to string hashing. If we have a string and use hash function as , same problem will arise. Instead we can use hash function like and lower chances of collisions.

We can apply this hashing method to our problem(obviously you can use different hash functions). If we have some subarray A[l..r] and number of occurrences of in this subarray is , number of occurrences of is , ..., number of occurrences of is , let's hash this subarray into .(You can choose and as you like, maybe two big prime numbers)

Here, basically we are compressing all frequency information in a subarray into one single number. So to check if a subarray is perfectly balanced, we can just compare left hash value and right hash value.

You might ask: "how to calculate the hash value fast?". Let's replace each s in with , s with , ..., s with . Let's call this new array . Then . Thus, if we use segment tree or fenwick tree, we can calculate the hash value in .

Now, to the main problem: how to check if A[l..r] is almost perfectly balanced? Let's say A[l..r] was almost perfectly balanced, and one extra element(say, ) belonged to the left half of the subarray. If we calculate and , we can see , and we get .

So, we can calculate and check if this value exists in . If it exists, then A[l..r] is almost perfectly balanced. If it doesn't, do the same check for .

Hope this helps!