Re: [algogeeks] CodeChef Problem
the example given in the link , tried 2-3 other example ..it seems to work for them.Maybe problem is not that simple and may fail for some tricky test case.So please correct me if i am wrong:- input : 2 3 4 1 1 sort(input) : 1 1 2 3 4 k=3 from end keep on adding till k-1 add position 4 become : 4+3+2 (cost 5 : 3 + 2) add position 2 : 1+1 (cost 1 :1) add position 2 to 4 : 4+3+2+1+1(cost 2 ) total cost : 5+1+2 = 8 On Tue, Sep 25, 2012 at 1:23 AM, Krishnan aariyankrish...@gmail.com wrote: http://codeforces.com/contest/227/problem/D How to approach this problem can anybody help? -- 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. -- 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.
[algogeeks] codechef mixtures problem
Hi All, Can someone explain the below problem's solution : http://www.codechef.com/problems/MIXTURES I have been struggling to solve DP problems and am not able to think clearly in problems like the one mentioned. Kindly help me to understand DP by providing some useful links. -- Regards, Shachindra A C -- 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 mixtures problem
the above question is similar to matrix-chain multiplication on page number -370,dynamic programming chapter,Introduction to Algorithms,t h cormen,leiserson,rivest,stein -- 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
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.
[algogeeks] codechef problem
In a plane given n points (x1,y1) (x2,y2)(xn,yn), find the the maximum number of collinear points. plz tell me the best way to do that. -- 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.
[algogeeks] codechef jan challenge
http://www.codechef.com/JAN11/problems/FLUSHOT/
*m getting wrong answer*
*if there is any problem wid my algorythm do let me know*
#includestdio.h
int main()
{
int t,D,N,j,i;
float T,*x,*y,*z,maxNo,minNo;
scanf(%d,t);
while(t--)
{
scanf(%d %f,N,T);
x=(float*)malloc(sizeof(float)*(N+1));
y=(float*)malloc(sizeof(float)*(N+1));
z=(float*)malloc(sizeof(float)*(N+1));
for(i=0;iN;i++)
{
scanf(%f,x[i]);
}
if((x[1]+x[0])=T || x[0]==0)
{
maxNo=x[0];
for(i=1;iN;i++)
{ x[i]-=i*T;
if(x[i]0)
x[i]=-x[i];
if(x[i]maxNo)
maxNo=x[i];
}
}
else
{maxNo=0.0;
j=0;
for(i=0;iN;i++)
{
y[i]=x[i]-(x[0]+i*T);
if(y[i]0)
{ z[j]=-y[i];}
if(y[i]maxNo)
{ maxNo=y[i];}
if(z[j]minNo j!=0 y[i]0)
{ minNo=z[j];}
if(y[i]0)
{j++;}
if(j==1 y[i]0)
{minNo=z[0];}
}
if(N==2)
maxNo=maxNo/2;
else maxNo=(maxNo+minNo)/2;
}
printf(%.4f\n,maxNo);
}
return 0;
}
--
Sanchit Mittal
Second Year Undergraduate
Department of Computer Engineering
Delhi College of Engineering
ph- +919582414494
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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 jan challenge
Wow: Its a Running Contest :)
On Sun, Jan 2, 2011 at 11:07 PM, sanchit mittal sm14it...@gmail.com wrote:
http://www.codechef.com/JAN11/problems/FLUSHOT/
m getting wrong answer
if there is any problem wid my algorythm do let me know
#includestdio.h
int main()
{
int t,D,N,j,i;
float T,*x,*y,*z,maxNo,minNo;
scanf(%d,t);
while(t--)
{
scanf(%d %f,N,T);
x=(float*)malloc(sizeof(float)*(N+1));
y=(float*)malloc(sizeof(float)*(N+1));
z=(float*)malloc(sizeof(float)*(N+1));
for(i=0;iN;i++)
{
scanf(%f,x[i]);
}
if((x[1]+x[0])=T || x[0]==0)
{
maxNo=x[0];
for(i=1;iN;i++)
{ x[i]-=i*T;
if(x[i]0)
x[i]=-x[i];
if(x[i]maxNo)
maxNo=x[i];
}
}
else
{ maxNo=0.0;
j=0;
for(i=0;iN;i++)
{
y[i]=x[i]-(x[0]+i*T);
if(y[i]0)
{ z[j]=-y[i];}
if(y[i]maxNo)
{ maxNo=y[i];}
if(z[j]minNo j!=0 y[i]0)
{ minNo=z[j];}
if(y[i]0)
{j++;}
if(j==1 y[i]0)
{minNo=z[0];}
}
if(N==2)
maxNo=maxNo/2;
else maxNo=(maxNo+minNo)/2;
}
printf(%.4f\n,maxNo);
}
return 0;
}
--
Sanchit Mittal
Second Year Undergraduate
Department of Computer Engineering
Delhi College of Engineering
ph- +919582414494
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
[algogeeks] Codechef
I have solved this problem , but i need test cases for this as it it giving WA in online judge. i dont want algo , but if anyone have solved this, please provide with some random test cases or one or two corner test cases. i will be greatful. http://www.codechef.com/problems/ARRAYTRM Given n numbers, you can perform the following operation any number of times : Choose any subset of the numbers, none of which are 0. Decrement the numbers in the subset by 1, and increment the numbers not in the subset by K. Is it possible to perform operations such that all numbers except one of them become 0 ? Input : The first line contains the number of test cases T. 2*T lines follow, 2 for each case. The first line of a test case contains the numbers n and K. The next line contains n numbers, a_1...a_n. Output : Output T lines, one corresponding to each test case. For a test case, output YES if there is a sequence of operations as described, and NO otherwise. Sample Input : 3 2 1 10 10 3 2 1 2 2 3 2 1 2 3 Sample Output : YES YES NO Constraints : 1 = T = 1000 2 = n = 100 1 = K = 10 0 = a_i = 1000 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] codechef problem
Johnny was asked by his math teacher to compute nn (n to the power of n, where n is an integer), and has to read his answer out loud. This is a bit of a tiring task, since the result is probably an extremely large number, and would certainly keep Johnny occupied for a while if he were to do it honestly. But Johnny knows that the teacher will certainly get bored when listening to his answer, and will sleep through most of it! So, Johnny feels he will get away with reading only the first k digits of the result before the teacher falls asleep, and then the last k digits when the teacher wakes up. Write a program to help Johnny to compute the digits he will need to read n range is 10 raise to power 9 k is always smaller than no of digits of n raise to power n -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
