EXPCH Video Solution - February Long Challenge 2020

Official editorial: EXPCH - Editorial

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

Video link: https://youtu.be/7u58GaN2Gns

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


wow! very nice explanation. Thank you.

1 Like

You’re welcome :slight_smile:

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.

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

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;
    dp[0] = 0;

  • for i = 1 to n-1
    if(s[i] == '(' || s[i] == '*')
    dp[i] = dp[i-1];
    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;
    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.


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