# EXPCH Video Solution - February Long Challenge 2020

Official editorial: EXPCH - Editorial

I explain the sample test case, along with 2 interesting solutions.

Solution 1 Commented Code: https://www.codechef.com/viewsolution/29774714
Solution 2 Commented Code: https://www.codechef.com/viewsolution/29774729

20 Likes

wow! very nice explanation. Thank you.

1 Like

You’re welcome

I liked the solution 1.

I initially solved it using Trees, then realised that it wasn’t really necessary XD

1 Like

@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.

2 Likes

Unfortunately I’m not familiar with python. Sorry about that.

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.

1 Like