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