ORDERS SPOJ

general
, , ,
1

How to solve this problem


I have seen some solution implementing tree to solve it but not able to understand it please help me out. @vineetpaliwal @darkshadows @prateekg603 @kachdog
Thanx in advance :slight_smile:
1 Like
2

@adjimmy
i am not among those who have you mentioned above.

This problem is also available on codechef hard section(last problem)

This problem can be solved using BIt and seg tree .
maintain a seg tree that contain only boolean values at leaves
1->present
0->absent

now propagate tree initially
so,root->node count=number of soldiers

now starting from right get the arr[i] soldier from the end this can be find in o(log(n)) using seg tree or O(log(n)*log(n)) using BIT using binary serach logic one you reach that node this node is the last soldier make this node in seg tree and propagate tree upwards. continue this technique for all the array elements from right to left .you will get the initial position of the soldier.
i think you can move a bit further .if still problem persists feel free to ask anything.

Feel free to cast votes if you like it. :stuck_out_tongue:

3 Likes
3

void buildst(int idx,int ss,int se)
{

if(ss==se)
{
	st[idx]=1;
	return ;
}
int  mid=(ss+se)>>1;
buildst(2*idx+1,ss,mid);
buildst(2*idx+2,mid+1,se);
st[idx]=st[2*idx+1]+st[2*idx+2];

}

void update(int idx,int ss,int se,int index)
{

   if(ss==se)
{

st[idx]=0;

	return ;

}
int  mid=(ss+se)>>1;

if(index<=mid)

update(2*idx+1,ss,mid,index);

else

update(2*idx+2,mid+1,se,index);

st[idx]=st[2*idx+1]+st[2*idx+2];

}

int query(int idx,int ss,int se,int count)

{

if(ss==se) return ss;

int mid=(ss+se)>>1;

if(st[2*idx+2]>=count)

 return query(2*idx+2,mid+1,se,count);

else 

 return query(2*idx+1,ss,mid,count-st[2*idx+2]);

}

4

have a look at the three function posted by me . i think they are enough to done this job.

1 Like
5

@ma5termind tell me how u thought of such a great solution it didnt even struck me though havent thought it for more than 1 hrs :frowning:

6

I once thought a lot over this problem too

7

you learned something new today about seg tree and BIt now try to solve ORDERSET on spoj

8

@ma5termind can u make me understand the approach taken by you or the logic am not getting it :frowning:

9

yes i can help you but tell me where are you not getting segtree logic or problem solving logic

10

problem solving logic … can u take an example nad show how the logic is working … it would be really helpful to me and others

11

@ma5termind please help me out with the problem solving logic

12

i am having an exam tomorrow i will explain you whole logic with an example after the exam so please wait till that…

13

@ma5termind but do remember to help me out :slight_smile:

14

@adjimmy no problem bro!!

15

hey @ma5termind now can u explain me your idea… ?? where are u man ?

16

@adjimmy sorry for being slow responsive these days :smiley: now tell mw on which input you want to test my algorithm mean(example)

17

@adjimmy here is the example based solution for you ::
Think of it like you need to implement a data structure that contains elements and you need to query it like

what is the 10 th element from the beginning ok now remove this and
again what is the kth element from the beginning right:D

lets operate it upon some test case suppose
i am having 5 elements

5 6 7 8 9

seg tree after building initially

      5
    3   2
  2  1 1  1
 1 1 1 1   1

clear upto here treat every number as a node of a seg tree::

now suppose i asked what is the second element from start::
how to apply this :
you know it is obvious that the element either lie in the left subtree or in right subtree::
now how to decide
check the left subtree node [3] if it is greater than or equal to the number for which you are looking forward then ignore right subtree and propagate downwards in the same manner. on the second you find again two nodes [2] [1] checked the same thing again proceeding in the left direction again
and the next level now contains [1] [1] right and in the left subtree you got one rather than two so it means the element you are finding is not under this node and proceed to the right subtree which is a leaf node you will get second [1] whose index is 2 (element which were you searching ) .

whenever you are heading towards the right subtree take care of this statement because::
return query(2idx+1,ss,mid,count-st[2idx+2]);

if you are having some elements in the left subtree(but less than that of requirement ) and looking for element in the right subtree count-st[2*idx+1] this to decrese the number of element found in the left subtree and proceed with the new count in the right subtree…

Now update the tree so that this element is deleted from the data structure

5 7 8 9

now how to do this just propage to the location which have you find just now in the tree and make it 0 (denoting absence of element ) and update it upwards your new tree will be ::

  4
2   2

1 1 1 1

1 0 1 1 1

now if you want to query for the next (any other) element. it will also goes in the same manner…

TRY YOUR HAND TO FIND THE 3 ELEMENT IN THE STRUTURE:: :smiley:

feel free to ask anything / doubts!!

if you like this answer then dont forget to cast votes!!

3 Likes
18

@adjimmy
something is waiting for you at the end of this page i hope you will like it.

19

@ma5termind great man :slight_smile: thanx

20

is this order valid for 2nd test case:
2 3 1 5 4