Aargh, silly me :D
I think we can assign a prime number, Prime_i > 1 to all the nodes i
in the tree.
Preprocessing : Each node i must maintain a product Pi of all the
prime numbers corresponding to to each of its nodes in the subtree
rooted at node i (including node i). This can be done in O(n) time.
Locking:-
Whenever we lock a particular node i we communicate Pi to the root
node. The root node would keep product (lets call it P, which has
initial value 1) which would be basically product of Pi of all the
nodes i which have been locked. O(1) time.
We also tag each of the ancestor node j of i with value Vj = 2 (a code
which would indicate that a node cannot be locked because one of its
descendent has been locked)...and increment the value lock_count, LCj
(which is initially 0) to indicate how many of its descendent have
been locked........ O(logn) time.
Tag the node i with value Vi = 1 ( a code which would indicate that
node i has been explicitly locked).
Unlocking:-
Whenever we unlock a particular node i we set the root node's P = P/
Pi. O(1) time.
And decrement lock_count for all of the ancestor nodes j of node i
(LCj--)
If LCj == 0 reset Vj = 0 indicating that no descendent of node j is
currently locked.
Querying:-
To check if node i is currently in a locked set.
Check Vj.
If Vj != 0
{
j is locked.
}
Else
Divide P by Prime_i.
{
If remainder == 0 then node i is in a locked state (basically node
i has one of its ancestor/parent explicitly locked).
otherwise node i is in a unlocked state
}
Phew....that was one long post.
I hope I made myself clear.
_dufus
On Aug 30, 4:21 pm, Nagendra Kumar <nagendra....@gmail.com> wrote:
> @Dufus.
> if d is locked then only b,a,g,h cannot be locked .But
> c,f,e,i,j can be locked.
>
>
>
> On Sun, Aug 30, 2009 at 1:41 PM, Dufus<rahul.dev.si...@gmail.com> wrote:
>
> > Before I propose my solution I have a query.
> > Consider the following tree:-
>
> > a
> > / \
> > b c
> > / \ /
> > d e f
> > / \ /\
> > g h i j
>
> > Initially all the nodes are in unlocked state.
> > Say user choses to lock node d.
> > Now by the given condition:-
> > i) none of its children {g,h} can be locked.
> > ii) none of the nodes which have d as child (ie. ancestors of d) can
> > be locked which are {b,a} // Since a node i cannot be locked if any of
> > its descendant is already locked.
>
> > Also note that a is ancestor of all the nodes in the tree, we end up
> > locking the WHOLE TREE (i.e. once d is locked no other node in the
> > tree can be locked)!!!
>
> > I think something is wrong here.
>
> > Nagendra/Priya any comments?
>
> > _dufus
>
> > On Aug 30, 11:10 am, priya k <priya.annau...@gmail.com> wrote:
> >> @Dufus: You mean to say do preprocessing and hash all the nodes that cannot
> >> be locked, if am not wrong. And again, Everytime we lock a node, we need to
> >> update the hash and that would be O(n) worst case. Can we do anything
> >> better
> >> ?
>
> >> --Priya
>
> >> On Sun, Aug 30, 2009 at 10:26 AM, Dufus <rahul.dev.si...@gmail.com> wrote:
>
> >> > Priya, as mentioned by you your isLock() takes O(logn) time.
> >> > We need to use Hash table as auxillary DS for O(1) query time.
>
> >> > _dufus
>
> >> > On Aug 30, 8:35 am, priya k <priya.annau...@gmail.com> wrote:
> >> > > // Data Structure for the n-ary tree
>
> >> > > struct node
> >> > > {
> >> > > int data;
> >> > > node * child[m];
> >> > > bool lockFlag; // Indicates if a node is locked or not
> >> > > node *parent; //Holds the immediate parent of the node
> >> > > int LockCount; //Holds how many nodes arrested this node
>
> >> > > };
>
> >> > > // Takes logm(N) in the worst case
>
> >> > > bool check(node *NodeToBeLocked)
> >> > > {
> >> > > node *m=NodeToBeLocked;
>
> >> > > if(m->flag==true || m->LockCount>0)
> >> > > return false; // since the node is already locked or any of its
> >> > > subtrees already locked, return false
>
> >> > > while(m && !m->lockFlag)
> >> > > m=m->parent;
>
> >> > > if(m && m->lockFlag)
> >> > > return false; // if any of its ancestors have been already locked
>
> >> > > return true;
>
> >> > > }
>
> >> > > // Takes logm(N) in the worst case
>
> >> > > bool lock(node *NodeToBeLocked)
> >> > > {
> >> > > if(check(NodeToBeLocked)) // If true, Node is free to be locked
> >> > > {
> >> > > node *m=NodeToBeLocked;
> >> > > m->lock=true;
> >> > > node *prevChild=m;
> >> > > m=m->parent;
> >> > > while(m)
> >> > > {
> >> > > m->LockCount++;
> >> > > prevChild=m;
> >> > > m=m->parent;
> >> > > }
> >> > > return true;
> >> > > }
> >> > > return false; //err.. cannot be locked
>
> >> > > }
>
> >> > > // Takes logm(N) in the worst case
>
> >> > > bool unlock(node *NodeToBeUnLocked)
> >> > > {
> >> > > node *m=NodeToUnBeLocked;
> >> > > m->lock=false; // Unlock the Node
> >> > > node *prevChild=m;
> >> > > m=m->parent;
> >> > > while(m)
> >> > > {
> >> > > m->LockCount--;
> >> > > prevChild=m;
> >> > > m=m->parent;
> >> > > }
>
> >> > > }
>
> >> > > Thanks,
> >> > > Priya
>
> >> > > On Sat, Aug 29, 2009 at 11:35 PM, nagendra kumar
> >> > > <nagendra....@gmail.com
> >> > >wrote:
>
> >> > > > Given a n-ary tree of resources arranged hierarchically. A process
> >> > > > needs to lock a resource node in order to use it. But,
> >> > > > A node cannot be locked if any of its descendant or ancestor is
> >> > > > locked.
> >> > > > I was supposed to
> >> > > > -> write the structure of node
> >> > > > -> write codes for
> >> > > > -> islock()- returns true if a given node is locked and false if it
> >> > > > is
> >> > > > not
> >> > > > -> lock()- locks the given node if possible and updates lock
> >> > > > information
> >> > > > -> unlock()- unlocks the node and updates information.
> >> > > > Codes should be :
> >> > > > Islock –O(1)
> >> > > > Lock()- O(log n)
> >> > > > unLock()- O(log n)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
