j=i-1 or (flagvalue,say:-1) I don’t think j can take any other value according to you.Am I correct?
If we take j as the smallest j such that [j,i] is valid, then sum of elements from j,i should be the answer and that can be calculated in O(1) by keeping prefix sums array.Is this solution Correct?
Used the exact same logic but got WA.
If I find a closing bracket which does not match with the top most bracket in the stack, do I need to push it in the stack? I don’t think it should make any difference.
And can I know for which test cases did my code fail?
Some test cases would be appreciated. I get ‘Wrong Answer’, but not sure for which cases.
Not even sure if I’m reading the data incorrectly or just algorithm is wrong.
Can somebody throw in a few ‘tricky’ test cases?
@Anurag92, You are declaring sum[100100] in each of the test case. While there can be 10^5 test cases. You should either keep it global or declare array of size N.
thnx 
. should have declared outside
Sorry for the confusion, please check now.
Actually i’m wondering why not for all j < i such that [j, i] is properly parenthesized?
correct me if i’m mistaken anywhere
according to the solution, you are trying to keep [j,i] segment length as minimum as possible
Didn’t get you, please elaborate.
will there be a unique j for each i? Actually i tried making a balanced parenthesis but observed that j is always unique. if i tried making j lesser ( close to index 0 ), the segment [j,i] was getting imbalanced. I’ll figure out my confusion. Thanks
Yes, I am talkign about largest j, such that segment [j,i] is balanced.
Just try to realize it using the fact which is written in penultimate line.
Counterexample: ()(), For last parenthesis, there are two j’s.
1 Like
Yes and segment [j,i] is balanced as well.
@saurv4u, take j as the largest value such that [j,i] is valid. In this way, you will be able to use dynamic programming approach.
I think you should note that \text{DP[i]} is initialized to 0 in the recurrence and the recurrence is only defined for \text{i} such that there is a balanced expression ending at \text{i}. Also, you never mention that \text{sum(hsh[i], i)} is the sum of the array from \text{hsh[i]} to \text{i}.
Anyway, thank you for the editorial! When I first saw this problem in the Cook-Off, I thought it was really hard, but now I see it wasn’t that bad after all!
I will read your code and will get back to you soon.
Found the algo problem. Wanted to have [O(1) + stack] extra memory, naive
If you want some test cases, I would recommend to write a function such as this to generate all combinations of input data of size N:
Btw, can only use one type of brackets for this.
char BA[] = { ‘{’, ‘(’, ‘[’, ‘<’, ‘>’, ‘]’, ‘)’, ‘}’ };
void GenSolve(int i)
{
if(i == N)
{
C[i] = ‘\0’;
solve();
return;
}
if(i == 0)
{
for(int k = 0; k < N; ++k)
A[k] = k + 1;
}
for(int b = 0; b < 8; ++b)
{
C[i] = BA[b];
GenSolve(i + 1);
}
}
Alternative approach to dp: represent the string as a list of trees.
The children of each tree are balanced substrings.
Use the maximum subarray sum across each node on its children.
Output the max each time.
You still need the stacks to find where the strings are balanced.
See the code: CodeChef: Practical coding for everyone