JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | 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 ?
Re: SPOJ:BRCKTS (response to post by NilayVaish) | Reply
use segment/interval tree.
Re: SPOJ:BRCKTS (response to post by NilayVaish) | Reply
I tried this problem and i m also facing the same difficulty of finding minimum cumulative frequency in O(logn). Is BIT different from segment/interval tree? I could not find helpful resources on segment trees, can someone give some good link on it.
Re: SPOJ:BRCKTS (response to post by NilayVaish) | Reply
I did this with a special kind of tree, described below. I don't know if it can be called Binary Indexed Tree, as I don't know what a BIT is. But its not a segment/interval tree.

Lets say you have an expression with N characters. Then make a tree with N nodes at the bottommost level. Each node represents a character. Then the level above it will have ceil(N/2) nodes. Each node in this level represents the concatenation of two nodes of the level below. Keep doing it. The topmost level will have 1 node that represents the whole string given to you.
             (())()((                   - Level 4 (1 node)
      (())              ()((            - Level 3 (2 nodes)
  ((       ))       ()       ((         - Level 2 (4 nodes)
(    (   )    )   (    )   (    (       - Level 1 (8 nodes)

Now each node stores two values, the no. of opening braces required to its left and the no. of closing braces required to its right to make the expression represented by it a valid expression. Its trivial for the bottommost nodes. Its (0,1) for and opening brace and (1,0) for a closing brace. Now figure out how will you use this values to find values at the levels above it! And then figure out how you can update this tree in O(log n). Check operation is trivial: The string is valid expression if the value at root node is (0,0).
Re: SPOJ:BRCKTS (response to post by skaterboy) | Reply
BIT is different from segment/interval trees. In this tutorial you can find something about segment trees. I've used segment trees to solve the problem.
Re: SPOJ:BRCKTS (response to post by dhoni) | Reply
please throw some light on how can we update in logn time..
Thanks in advance..

EDIT: got it..got AC..
Re: SPOJ:BRCKTS (response to post by dhoni) | Reply
@dhoni: your approach is nice , I got AC in first attempt with this approach.
Re: SPOJ:BRCKTS (response to post by ankit2601) | Reply
guys why tle?????????
#define X 30009
char arr[X];

struct node
{
int left;
int right;
};
struct node seg[4*X];
void init(int i,int j,int node){
if(i == j)
{
if(arr[i]=='(')
{
seg[node].left = 0;
seg[node].right = 1;
}
else if(arr[i]==')')
{
seg[node].left = 1;
seg[node].right = 0;
}
}
else
{
int mid = (i+j)>>1;
init(i,mid,2*node);
init(mid + 1,j,1+2*node);
int mint = min(seg[2*node].right,seg[2*node+1].left);

seg[node].left = seg[2*node].left - mint + seg[2*node+1].left;
seg[node].right = seg[2*node+1].right - mint + seg[2*node].right;

}
}
void update(int i,int j, int index,int node)
{
if(i == j)
{
if(arr[i] == '(')
{
arr[i] = ')';
seg[node].right--;
seg[node].left++;

}
else{
arr[i] = '(';
seg[node].left--;
seg[node].right++;
}
}
else
{
int mid = (i+j)>>1;
update(i,mid,index,2*node);
update(mid + 1,j,index,1+2*node);
int mint = min(seg[2*node].right,seg[2*node+1].left);

seg[node].left = seg[2*node].left - mint + seg[2*node+1].left;
seg[node].right = seg[2*node+1].right - mint + seg[2*node].right;
}
}
void build_tree(int sz)
{
init(0,sz-1,1);
}
int main()
{

int n =10;
int tt =1;
while(n--)
{
int x = 0;
printf("Test %d:\n", tt++);
scanf("%d", &x);
scanf("%s",arr);
build_tree(x);
int q =0;
scanf("%d", &q);
while(q--)
{
int a =0;
scanf("%d", &a);
if(a == 0)
{
int ans = !seg[1].left && !seg[1].right;
if (ans) puts("YES");
else puts("NO");
}
else
update(0,x-1,a-1,1);
}
}

return 0;
}
Re: SPOJ:BRCKTS (response to post by dhoni) | Reply
Hii Dhoni, I have implemented your approach and it seems right to me and giving correct answer on my test cases but getting wrong answer on http://www.spoj.com/problems/BRCKTS/

Code is in edit.
RSS