wow! very nice explanation. Thank you.
1 Like
I liked the solution 1.
I initially solved it using Trees, then realised that it wasn’t really necessary XD
2 Likes
@tmwilliamlin Can you please give the solution in python code, please. I tried to solve this with python 3.6 and I got wrong answer.
I came with some utter nonsense but hear me out. I declared an array of size 2\times10^7 +14 .initially set 10^7 +7 as 1 and rest as 0. I declared a variable shift=10^7 +7. when the ith character was ‘(’ I decreased shift and for ‘)’ I increased shift and added the ones that would go to -1 from 0 to 1 because a flip increments the sum by 2. Obviously added one 0 at each character. Doing this we would get the number of subarrays whose sum would be k by arr[shift + k].So at every ‘)’ i just added (n-i)*arr[shift] which is the number of 0 sum states and put the together with 2 because both will become 1 after the character.
https://www.codechef.com/viewsolution/29490473
Nice explanation. Adding 1 to dp[o] at every i can also be understood in this manner that ‘(’ adds 1 to dp[o+1], ‘)’ adds 1 to dp[o-1] and ‘*’ adds 1 to dp[o]. So this is equivalent to dp[o]++ in general case as ‘(’ and ‘)’ will shift the o to o-1 and o+1 respectively. I thought it this way.
1 Like
@tmwilliamlin
Here’s my approach
-
dp[i]
is the contributed changes by the number of substrings ending at index i
-
So the base case is
if(s[0] == ')')
dp[0] = 1;
else
dp[0] = 0;
-
for i = 1
to n-1
if(s[i] == '(' || s[i] == '*')
dp[i] = dp[i-1];
else
dp[i] = (1 + dp[i-1] + balanced[i-1]);
-
balanced[i-1]
adds up for finding number times the current character ')'
is changed, it changes only if the previous part is balanced.
-
balanced[i]
is the number of substrings ending at i
and are virtually balanced
-
According to the question, the virtually balanced string is a string that is balanced after the transition/process.
-
Here balanced refers that #(')') == #('(')
-
For example )())
, ()
, (())
, ()()
, ))()
, **
...
are all virtually balanced.
-
I have tried to form a recurrence for balanced[i]
if(s[i] == '(')
balanced[i] = 0;
else if(s[i] == '*')
{
if(i > 0)
balanced[i] = balanced[i-1] + 1;
else
balanced[i] = 1;
}
else
//s[i] == ')'
{
//?? stuck here
}
-
I was unable to figure out how to form the cases for balanced[i]
if the string ends with')'
someone please help me in completing this (this approach)
That looks like the same as my solution 1.
3 Likes
Unfortunately I’m not familiar with python. Sorry about that.
1 Like
I’ve thought about it for a bit, and it seems like the only way to find balanced[i] is to use the DP in my solution 1. Basically, balanced[i] = dp[i][0] in my solution.
2 Likes