|
|
вернуться в форум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). What do you mean when saying "point" ?? What is "point" here ? Could you please give a clear description of this method ? 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). |
|
|
