2
$\begingroup$

Given sequence (length $N$) of brackets like $($ and $)$. The task is to implement data structure which supports following operations:

  • Check whether the sequence is correctly bracketed
  • Rotate bracket at position $i$

I dont want a solution, but some feedback if I am on a good way.

There is no time complexity constraint in the instructions. So I suppose, it should be better than $O(N)$. Because trivial solution with stack leads to $O(N)$.

The only options are:

  • It can be done in logarithmic time by use of some smart tree data structure.
  • Or it can be done in amortized constant time which I actually believe to.

I have following ideas:

  • Define function $w(i)$ for each position $i$ by $w(0)=0$ and $w(i)=w(i-1)+d_i$ where $d_i=+1$ if the bracket is $($ and $d_i=-1$ otherwise. First bracket have index $1$.
  • Fact: The sequence is not correctly bracketed if and only if $w(N) > 0$ or there exists such $j$ for that: $w(j) < 0$.
  • So I want to keep tracking mimum $m$ of those $w(i)$. And for the first query I able to answer in constant time just by checking that $m < 0$ and $w(N) > 0$.
  • The problem is how to track the value of $m$ to achieve the best time.
  • If I rotate bracket on position $i$, all $w(i)$ from $i$ to $N$ are changed by constant $\pm2$. It implies the change of $m$. If I would update those $w(i)$ directly it would lead to again to linear time.
  • So I was wondering how to enclose this behaviour to another datastructure (post is here) in some smart way. But I just cant get over that. Everything I was thinking about is just linear. So is it possible at all?
Improve this question
$\endgroup$
7
  • $\begingroup$ If your sequence has length N you have to perform N read operations to know what is the input. So you have to get it packed into some structure as input because otherwise it is not possible. Even though it gets fancy DS - you can rotate bracket in log or constant time, but checking from scratch N elements in constant time - unless there is some fancy representation, numbers etc. (that I am not aware of) - it does not seem possible. $\endgroup$ – Evil Sep 28 '16 at 21:39
  • $\begingroup$ You might be interested in the Dyck language. $\endgroup$ – Evil Sep 28 '16 at 21:53
  • $\begingroup$ You are right I am assuming that the input is already read and structure is initialized it is written here: cs.stackexchange.com/questions/64008/…. So I just want to keep tracking changes after init. Then I have an idea how to implement rotate in O(1), but then check is O(N). I also have an idea how to implement check in O(1), but then the rotate is O(N)... $\endgroup$ – Ondra Hrubý Sep 28 '16 at 21:55
  • $\begingroup$ "better than O(N)" -- that doesn't make any sense. I suspect you want to use some $\Theta$s. $\endgroup$ – Raphael♦ Sep 28 '16 at 22:27
  • 1
    $\begingroup$ Hm. You want a self-adjusting parser for context-free languages. $\endgroup$ – Raphael♦ Sep 28 '16 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.