Re: [algogeeks] CODECHEF FLIP COIN problem

2011-02-09 Thread Arpit Sood
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

Re: [algogeeks] CODECHEF FLIP COIN problem

2011-02-09 Thread Arpit Sood
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

Re: [algogeeks] CODECHEF FLIP COIN problem

2011-02-09 Thread Gaurav Saxena
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

Re: [algogeeks] CODECHEF FLIP COIN problem

2011-02-08 Thread Gaurav Saxena
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

Re: [algogeeks] CODECHEF FLIP COIN problem

2011-02-08 Thread sunny agrawal
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

Re: [algogeeks] CODECHEF FLIP COIN problem

2011-02-08 Thread Gaurav Saxena
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

Re: [algogeeks] CODECHEF FLIP COIN problem

2011-02-08 Thread sunny agrawal
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

Re: [algogeeks] CODECHEF FLIP COIN problem

2011-02-08 Thread Gaurav Saxena
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

Re: [algogeeks] CODECHEF FLIP COIN problem

2011-02-08 Thread Ankur Khurana
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 * *

[algogeeks] CODECHEF FLIP COIN problem

2011-02-07 Thread Gaurav Saxena
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

Re: [algogeeks] CODECHEF FLIP COIN problem

2011-02-07 Thread sunny agrawal
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