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

Post Reply
Moshiur Rahman
New poster
Posts: 13
Joined: Mon Sep 08, 2008 6:57 pm
Location: State University of Bangladesh

SPOJ BRCKTS Using segment tree (help!)

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

I was working on
https://www.spoj.pl/problems/BRCKTS/

My half solution :

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

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

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'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...

Post Reply

Return to “Other words”