I used an O(n*n) method and got TLE#9. Does anyone know of any O(n) method. I actually checked every cyclic shift to see if it is a valid expression.

Of course there are exists O(n) algo. You just must to find 1 valid cyclic shift. And then check balance in it. Number of points with balance == 0 will be the answer to ploblem.

There is another method - check number of points where minimal disballance is nonnegative (after checking that overall ballance is zero).

I think,that your algo get TLE on new tests.
Because, it's not diffucult crate test,where your program will do o(N^2).
Exampel - 49999 times '(', 50000 times ')', 1 time ')'.

My AC program find shift, not finding right bracket expression (it's O(N^2)), but by an other method ( n steps).

Good luck =)

Edited by author 21.04.2009 21:12

There is exist  O(n*log(n)) solution.

If the sequence s is of length n, consider the sequence ss, which will have length 2n. Now define l_i as the number of '(' in the first i characters of ss and r_i as the number of ')' in the first i characters of ss. Let d_i=l_i-r_i. We want to know if there are any  numbers smaller than d_i in d_i, ... , d_{n+i}. Interval trees will give you O(n log n) algorithm, but there are even simpler algorithms that will give you an O(n) algorithm (Hint: d_i is continuous).

What do you mean when saying "point" ?? What is "point" here ? Could you please give a clear description of this method ?