SUBARRAY - Editorial

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

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?

http://www.codechef.com/viewsolution/6329799

I will read your code and will get back to you soon. :slight_smile:

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?

Found the algo problem. Wanted to have [O(1) + stack] extra memory, naive :slight_smile:
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);
}
}