try lazy propogation On Tue, Feb 8, 2011 at 8:14 PM, Gaurav Saxena <grvsaxena...@gmail.com>wrote:
> Hey thanks for your help > I have written a code using range trees but I am still getting TLE [?][?][?] > Please suggest me something > > > Here is my code > > /* > * File: main1.c > * Author: gs > * > * Created on 8 February, 2011, 7:46 PM > */ > > #include <stdio.h> > #include <stdlib.h> > > > #define MAX 300000 > #define loop0(i,j) for(int i=0;i<j;i++) > #define loop1(i,j) for(int i=1;i<j;i++) > # define true 1 > # define false 0 > > > _Bool flag[MAX]; > int value[MAX]; > > /*void initialize(int node, int b, int e) > { > if (b == e) > { > flag[node] = false; > value[node] = 0; > } > else > { > initialize(2 * node, b, (b + e) / 2); > initialize(2 * node + 1, (b + e) / 2 + 1, e); > value[node] = 0; > flag[node] = false; > } > }*/ > > int update(int node, int b, int e, int i, int j) > { > int p1, p2; > if (i > e || j < b) > return 0; > if(b==e) > { > if(flag[node] == true) > return 1; > else > return 0; > } > if (b >= i && e <= j) > { > if(flag[node] == true) > { > flag[node] = false; > flag[2*node] = !flag[2*node]; > flag[2*node+1] = !flag[2*node+1]; > p1 = update(2 * node, b, (b + e) / 2, i, j); > p2 = update(2 * node + 1, (b + e) / 2 + 1, e, i, j); > return (value[node] = p1 + p2); > } > else > return value[node]; > } > else > { > if(flag[node]==true) > { > flag[node]=false; > flag[2*node]=!flag[2*node]; > flag[2*node+1]=!flag[2*node+1]; > } > p1 = update(2 * node, b, (b + e) / 2, i, j); > p2 = update(2 * node + 1, (b + e) / 2 + 1, e, i, j); > return value[node] = p1 + p2; > } > } > > int query(int node, int b, int e, int i, int j) > { > int p1, p2; > if (i > e || j < b) > return 0; > if (b >= i && e <= j) > { > flag[node] = !flag[node]; > return value[node] = e - b + 1 - value[node]; > } > else > { > if(flag[node]==true) > { > flag[node]=false; > flag[2*node]=!flag[2*node]; > flag[2*node+1]=!flag[2*node+1]; > } > p1 = query(2 * node, b, (b + e) / 2, i, j); > p2 = query(2 * node + 1, (b + e) / 2 + 1, e, i, j); > if(p1==-1) > p1=0; > if(p2==-1) > p2=0; > return (value[node] = p1 + p2); > } > } > > int main() > { > int i, n, q,ret; > int cmd, a, b, z; > scanf("%d %d",&n,&q); > // initialize(1, 0, tests-1); > for(i=0;i< q;i++) > { > scanf("%d %d %d",&cmd,&a,&b); > if(cmd==0) > value[1] = query(1,0,n-1,a,b); > else > printf("%d\n",update(1,0,n-1,a,b)); > } > return 0; > > } > > > > > On Tue, Feb 8, 2011 at 3:41 PM, sunny agrawal <sunny816.i...@gmail.com>wrote: > >> make a tree where each node have the following structure >> >> 1. rangeLow >> 2. rangeHigh >> 3. headCount of its complete subTree >> 4. boolean variable change, if true means all nodes of that subtree need >> to be flipped but we are not flipping in the hope if again a flip occur we >> can reset the flag and we can save some time >> 5.isHead >> >> initialise range tree as for root range 0->MAX >> leftSubTree 0->MAX/2 rightSubTree MAX/2+1 -> MAX >> all headCount initially 0 >> all changes to false >> >> as a query comes, if it matches with range of some node we can stop >> propagating at that level and making change true so no need to go till leaf >> nodes >> new head count at that node will be (total nodes in its range - prev >> headCount) >> >> >> if you are still not able to get it you should read a range tree tutorial, >> that will really help >> >> On Tue, Feb 8, 2011 at 2:28 PM, Gaurav Saxena <grvsaxena...@gmail.com>wrote: >> >>> Actually I could not figure out any good way of doing this . [?][?] >>> Could you please suggest me something or give some idea . >>> Thanks for helping >>> >>> On Tue, Feb 8, 2011 at 1:51 PM, sunny agrawal >>> <sunny816.i...@gmail.com>wrote: >>> >>>> i think time complexity of the O(nlgn) for an avg case will suffice >>>> >>>> no it will not be inefficient if we keep sufficient information at each >>>> node >>>> each node will keep information of all its childs(headCount) and using >>>> some optimizations such as if two flips on same range occur simultaneously, >>>> then after all there will be no effect at all so there was no need of doing >>>> anything. >>>> >>>> On Tue, Feb 8, 2011 at 1:27 PM, Gaurav Saxena >>>> <grvsaxena...@gmail.com>wrote: >>>> >>>>> If we make segments of the range of coins which are heads then in some >>>>> case the result will become alternate which could be more inefficient. Any >>>>> idea what time complexity will suffice ? >>>>> Could you please elaborate your reply . >>>>> >>>>> >>>>> On Tue, Feb 8, 2011 at 1:08 PM, sunny agrawal <sunny816.i...@gmail.com >>>>> > wrote: >>>>> >>>>>> i think your solution will be O(n) for each query >>>>>> so it will be O(Q*N), that will surely timeout >>>>>> read about Range Trees, segment trees from wiki or CLRS >>>>>> >>>>>> On Tue, Feb 8, 2011 at 1:01 PM, Gaurav Saxena <grvsaxena...@gmail.com >>>>>> > wrote: >>>>>> >>>>>>> I need help regarding the codechef flip coin problem . >>>>>>> I am trying a code with O(n) time and it is giving TLE . >>>>>>> Couldn't figure out a better solution. >>>>>>> http://www.codechef.com/problems/FLIPCOIN/ >>>>>>> >>>>>>> Thanks for help . >>>>>>> >>>>>>> -- >>>>>>> Thanks and Regards , >>>>>>> Gaurav Saxena >>>>>>> >>>>>>> -- >>>>>>> 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?hl=en. >>>>>>> >>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> Sunny Aggrawal >>>>>> B-Tech IV year,CSI >>>>>> Indian Institute Of Technology,Roorkee >>>>>> >>>>>> -- >>>>>> 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?hl=en. >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> Thanks and Regards , >>>>> Gaurav Saxena >>>>> >>>>> -- >>>>> 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?hl=en. >>>>> >>>> >>>> >>>> >>>> -- >>>> Sunny Aggrawal >>>> B-Tech IV year,CSI >>>> Indian Institute Of Technology,Roorkee >>>> >>>> -- >>>> 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?hl=en. >>>> >>> >>> >>> >>> -- >>> Thanks and Regards , >>> Gaurav Saxena >>> >>> -- >>> 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?hl=en. >>> >> >> >> >> -- >> Sunny Aggrawal >> B-Tech IV year,CSI >> Indian Institute Of Technology,Roorkee >> >> -- >> 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?hl=en. >> > > > > -- > Thanks and Regards , > Gaurav Saxena > > -- > 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?hl=en. > -- 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?hl=en.
<<344.gif>>
<<33F.gif>>