@arpit : could you please tell me what is the problem with the update function ??
On Wed, Feb 9, 2011 at 3:32 PM, Arpit Sood <[email protected]> wrote: > there is problem with the update function... > > On Tue, Feb 8, 2011 at 8:14 PM, Gaurav Saxena <[email protected]>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 <[email protected]>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 <[email protected]>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 >>>> <[email protected]>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 >>>>> <[email protected]>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 < >>>>>> [email protected]> 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 < >>>>>>> [email protected]> 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 [email protected]. >>>>>>>> To unsubscribe from this group, send email to >>>>>>>> [email protected]. >>>>>>>> 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 [email protected]. >>>>>>> To unsubscribe from this group, send email to >>>>>>> [email protected]. >>>>>>> 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 [email protected]. >>>>>> To unsubscribe from this group, send email to >>>>>> [email protected]. >>>>>> 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 [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> 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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Arpit Sood > Some day you will see things my way. > http://arpit-sood.blogspot.com > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
<<344.gif>>
<<33F.gif>>
