EXPCH Video Solution - February Long Challenge 2020

editorial
,
1

Official editorial: EXPCH - Editorial

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

Video link: EXPCH Solution - CodeChef February Long Challenge 2020 - YouTube

Solution 1 Commented Code: CodeChef: Practical coding for everyone
Solution 2 Commented Code: CodeChef: Practical coding for everyone

20 Likes
2

wow! very nice explanation. Thank you.

1 Like
3

You’re welcome :slight_smile:

4

I liked the solution 1.

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

2 Likes
5

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

6

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

7

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
8

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

9

That looks like the same as my solution 1.

3 Likes
10

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

1 Like
11

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