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.
<<344.gif>>
<<33F.gif>>
