SPOJ BRCKTS Using segment tree (help!)

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

SPOJ BRCKTS Using segment tree (help!)

by Moshiur Rahman » Sat Feb 21, 2009 12:32 pm

I was working on

My half solution :

Replace all the '(' with 1 and ')' with -1 and construct a new array A[ ]. ( A[i] = 1 or -1 )

calculate C[ ]. ( C[i] is the sum of the values A[0]...A[i] )

Now, for determining whether the word is correct or not you need to check if A[ ] sums up to zero and if any of the C[i]'s are negative.

The first check can be done easily.

To do the second check, build a segment tree from C[ ], where each node is a pair<int,int>. Here, pair.first is the index of the minimum in the corresponding range and pair.second is the total value added in that range without considering the parents. For the replacement operations add 2 [ for ')' to '(' ] or -2 [ for '(' to ')' ] with all the values in C[i...n]. The replacement is performed in the i-th position. This can be done in log(n) with the segment tree.

But, how can I find the minimum in C[ ], in less than O(n), using this segment tree? Do I need to add any extra information or perform any special operation?

I am new to the concept of segment trees.

Thanks in advance and sorry for the long description.
Never think too hard, let ideas come to you...
Moshiur Rahman
New poster
Posts: 13
Joined: Mon Sep 08, 2008 6:57 pm
Location: State University of Bangladesh

Return to Other words

Who is online

Users browsing this forum: No registered users and 1 guest