Re: [algogeeks] CODECHEF FLIP COIN problem
there is problem with the update function...
On Tue, Feb 8, 2011 at 8:14 PM, Gaurav Saxena grvsaxena...@gmail.comwrote:
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 30
#define loop0(i,j) for(int i=0;ij;i++)
#define loop1(i,j) for(int i=1;ij;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.comwrote:
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.comwrote:
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.comwrote:
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.comwrote:
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
Re: [algogeeks] CODECHEF FLIP COIN problem
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.comwrote:
@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.comwrote:
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 30
#define loop0(i,j) for(int i=0;ij;i++)
#define loop1(i,j) for(int i=1;ij;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.comwrote:
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.comwrote:
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
Re: [algogeeks] CODECHEF FLIP COIN problem
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.comwrote:
@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.comwrote:
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 30
#define loop0(i,j) for(int i=0;ij;i++)
#define loop1(i,j) for(int i=1;ij;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.comwrote:
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.comwrote:
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
Re: [algogeeks] CODECHEF FLIP COIN problem
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.comwrote: 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.comwrote: 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.
Re: [algogeeks] CODECHEF FLIP COIN problem
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.comwrote: 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.comwrote: 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.comwrote: 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.
Re: [algogeeks] CODECHEF FLIP COIN problem
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.comwrote: 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.comwrote: 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.comwrote: 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.comwrote: 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. 344.gif33F.gif
Re: [algogeeks] CODECHEF FLIP COIN problem
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.comwrote: 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.comwrote: 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.comwrote: 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.comwrote: 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.comwrote: 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. 344.gif33F.gif
Re: [algogeeks] CODECHEF FLIP COIN problem
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 30
#define loop0(i,j) for(int i=0;ij;i++)
#define loop1(i,j) for(int i=1;ij;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.comwrote:
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.comwrote:
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.comwrote:
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.comwrote:
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.comwrote:
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.comwrote:
I need help regarding the codechef flip coin problem .
I am trying a code
Re: [algogeeks] CODECHEF FLIP COIN problem
try lazy propogation
On Tue, Feb 8, 2011 at 8:14 PM, Gaurav Saxena grvsaxena...@gmail.comwrote:
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 30
#define loop0(i,j) for(int i=0;ij;i++)
#define loop1(i,j) for(int i=1;ij;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.comwrote:
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.comwrote:
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.comwrote:
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.comwrote:
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
[algogeeks] CODECHEF FLIP COIN problem
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.
Re: [algogeeks] CODECHEF FLIP COIN problem
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.comwrote: 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.
