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