JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
SPOJ:BRCKTS | Reply
I tried solving BRCKTS using Binary Indexed Tree. The approach as highlighted in some forums -
1. The frequency at an index is +1 or -1 for an opening or a closing bracket respectively.
2. Level of imbrication at an index is the cumulative frequency.
3. For checking, find the minimum level of imbrication. And the level of imbrication for the final index. If both 0, then the present expression is correct, else it is incorrect.

I am unable to figure out a way for maintain the minimum level of imbrication in O(log n). Can someone suggest a way for finding the minimum ?
Subject Author Date
SPOJ:BRCKTS NilayVaish Jul 10, 2007 at 10:08 PM EDT
Re: SPOJ:BRCKTS Relja Jul 11, 2007 at 8:08 AM EDT
Re: SPOJ:BRCKTS skaterboy Jan 7, 2008 at 8:19 PM EST
Re: SPOJ:BRCKTS boba5551 Jan 8, 2008 at 1:53 PM EST
Re: SPOJ:BRCKTS dhoni Jan 8, 2008 at 2:43 AM EST
Re: SPOJ:BRCKTS nikunj165 Oct 20, 2011 at 2:34 PM EDT
Re: SPOJ:BRCKTS ankit2601 Jan 20, 2014 at 11:36 AM EST
Re: SPOJ:BRCKTS var88 Sep 4, 2014 at 12:20 AM EDT
Re: SPOJ:BRCKTS upen Oct 1, 2014 at 1:11 AM EDT
RSS