Dynamic Programming Question:Hacker earth -October easy 2022

Q.You are given a binary string S of length N. A substring of a binary string is called positive if the number of 1′s present in the substring is strictly greater than the number of 0′s present. Find the number of positive substrings in the given string S

Code:

(Editorial Solution)

#include<bits/stdc++.h>
using namespace std;

int main() {
	int tt;
	cin >> tt;
	while (tt--) {
		int n; cin >> n;
		string s; cin >> s;
		s = ')' + s;
		vector<int> pre(n + 1), dp(n + 1), pos(2 * n + 1, -1);
		for (int i = 1; i <= n; i++) {
			pre[i] = pre[i - 1] + (s[i] == '1' ? 1 : -1);
		}
		pos[n] = 0;
		for (int i = 1; i <= n; i++) {
			int idx = pos[pre[i] + n];
			if (s[i] == '1') {
				if (idx == - 1) {
					dp[i] = i;
				} else {
					dp[i] = (i - idx - 1) + dp[idx];
				}
			} else {
				if (idx != -1)  dp[i] = dp[idx];
			}
			pos[pre[i] + n] = i;
		}
		cout << accumulate(dp.begin(), dp.end(), 0LL) << '\n';
	}
	return 0;
}

Explaination:

I decided to give a more detailed explaination for this problem as not much was given in the editorial

First what the pos vector does

pos is declared to be containing twice as many element as n
because negative unique prefix sum will be stored to
left of n and to right of n positive unique prefix sum will 
be stored and we know that
prefix sum can never be greater than n by 
property of input and we declare center position(n) to be 0

Consider

1 0 1 1 -Input string

1 0 1 2 -pre[] array

1 2 3 4 -i

-1 0 1 -1 - idx

1 0 2 4- dp[] array

Total ans=7

There if there is even a single -1 or 1 different than any
of previously repeating(or single) characters than it will refer already filled 
position in pos array(vector).

so pos contains at left side of n which positions have unique negative prefix sum at which index(position) of string and vice versa for right side

and when pre[i] repeats instead of giving unique value we update the corresponding prefix sum location in pos pointing to new position in string

Consider i-idx-1 +dp[idx]. this will only trigger when s[i]=='1' and when the prefix sum is duplicated and not unique ,to do that we need to have same no of 0s and same no of 1s after the

pervious position of same prefix sum and we check this condition when s[i]==1 because we want the string to end with 1 and we subtract 1 to remove one case of considering all the characters from idx to i then we consider only idx+1 to i and of course we also have to consider the no of positive sub

strings that can be formed from remaining characters so we add from dp table we created from that position because we have only equal no of 0s and 1s so adding those to previously formed subarrays won't make any difference so the definition of dp table is satisfied

(Note:

dp[i]=0 if its a unique negative prefix sum because if say for a general case there are p 0's and then q 1's(in any order) then there must be total of (p+q+1) 0s added to the end for them to create a unique negative string and it also means that the prefix sum will be the lowest compared previous i's and the definition of dp[i]=no of subarrays that end at index i so that means since s[i]==0 then dp[i]=0 obviously and for the case when negative prefix sum repeats the only its possible is same as in the positive case equal no of 0s and 1s so it will be equal to dp[idx] as the string till idx we don't know how many positive substrings it has)

Finally we add all the elements in the dp table because it contains the unique no of sub arrays that can be formed at length i by definition of dp table i.e. no of sub arrays forming which are ending at index i