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.
