Yes actually I could not figure out how to implement that lazy propagation in the array . Yes please help me in doing that.
On Wed, Feb 9, 2011 at 10:56 PM, Arpit Sood <soodfi...@gmail.com> wrote:
> you are not actually using the concept of lazy propagation in the code, you
> are doing update in O(n). if you want the solution then reply back.
>
>
> On Wed, Feb 9, 2011 at 6:22 PM, Gaurav Saxena <grvsaxena...@gmail.com>wrote:
>
>> @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 <soodfi...@gmail.com> wrote:
>>
>>> there is problem with the update function...
>>>
>>> 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.
>>>>
>>>
>>>
>>>
>>> --
>>> 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 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.
>>
>
>
>
> --
> 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 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.
<<344.gif>>
<<33F.gif>>
