[algogeeks] extendible hashing
i want to implement extendible hashing for may major project.so the crux of the problem is to directly access the disk block without using the undelying os file system interface.one idea which comes to my mind is to build a virtual file system interface for my project but currently i want to avoid that.so is there any API in unix or windows which can do the job or is there any existing file system which uses the extendible hashing in its implementation.please help its urgent. -- 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] amazon
Can you give me solution for N=1 and N=2? I don't think that it is possible for every N. -- 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] Re: array(amazon && microsoft)
U using extra space, if you using extra space, simple C++ implementation will be use a priority queue and do BFS. On Wed, Feb 9, 2011 at 10:47 AM, jalaj jaiswal wrote: > @algoseeker > > mine approach is also the same but m inserting the elements in a min heap > and you in a set.. i guess extraction of minimum element will be better in > terms of complexity if we use a heap > > > On Wed, Feb 9, 2011 at 10:01 AM, Ujjwal Raj wrote: > >> I see a scope of optimization in the algo. >> In step 2. Before inserting the element a[i][j], you can make sure that >> a[i][j-1] and a[i-1][j] are in the set. If not then do no insert a[i][j] in >> the heap. (considering the boundary condition, if j-1 < 0 or i-1 < 0 then >> assume it is true) >> >> Correct me if I am wrong. >> >> >> On Tue, Feb 8, 2011 at 11:40 PM, algoseeker wrote: >> >>> Just coded the solution, it worked on all the test cases described here >>> in this thread using the algo i described above :) >>> >>> The code is available at >>> https://github.com/algoseeker/Interview/tree/master/sorting >>> >>> -- >>> 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. >> > > > > -- > With Regards, > *Jalaj Jaiswal* (+919019947895) > Software developer, Cisco Systems > Final Year Undergraduate, > IIIT ALLAHABAD > > -- > 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] Re: Meetings puzzle
didn't quite get it, can you please elaborate. thanks On Feb 8, 10:38 pm, Ujjwal Raj wrote: > Use dynamic programming: > 1) Sort the events in order of finishing time. > f1, f2, f3, f4, ... fn > > E(fn) = E(sn) + 1; > Solve the above recursion > sn is start time of event n > > On Wed, Feb 9, 2011 at 11:30 AM, Sachin Agarwal > wrote: > > > > > > > > > Suppose I have a room and I want to schedule meetings in it. You're > > given a list of meeting start and end times. Find a way to schedule > > the maximum number of meetings in the room. > > > -- > > 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.
Re: [algogeeks] Meetings puzzle
Use dynamic programming: 1) Sort the events in order of finishing time. f1, f2, f3, f4, ... fn E(fn) = E(sn) + 1; Solve the above recursion sn is start time of event n On Wed, Feb 9, 2011 at 11:30 AM, Sachin Agarwal wrote: > Suppose I have a room and I want to schedule meetings in it. You're > given a list of meeting start and end times. Find a way to schedule > the maximum number of meetings in the room. > > -- > 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] amazon
Place N number from 1 to N, in 2N positions in such a way so that there are Exactly “a” number of cells between two placed locations of number “a”. Write a program to display numbers placed in this way. Example:- (1) One of the possible placement for 7 numbers in 14 positions is : 5 7 2 3 6 2 5 3 4 7 1 6 1 4 -- With Regards, *Jalaj Jaiswal* (+919019947895) Software developer, Cisco Systems Final Year Undergraduate, IIIT ALLAHABAD -- 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] Meetings puzzle
Suppose I have a room and I want to schedule meetings in it. You're given a list of meeting start and end times. Find a way to schedule the maximum number of meetings in the room. -- 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] Re: Puzzle For Puzzled Minds
@Bittu: Since you didn't say what the weights are, I presume that I
can choose the weights. So I simply choose 125 1 kg weights. Then I
can weigh the required sugar packets with 125 weight movements: simply
add a 1 kg weight for each subsequent sugar packet.
Further presuming that this is not the answer you want, let me note
that this can be solved as a binary Gray code problem. A Gray code is
a binary numeral system where two successive values differ in only one
bit. See, e.g., http://en.wikipedia.org/wiki/Gray_code. If we use
weights 1, 2, 4, 8, 16, 32, and 64 kg, we can generate all of the
integers from 1 to 127 in 127 steps, each consisting of adding or
removing exactly one weight. We don't need two of these integers,
namely 126 and 127. Unfortunately, they come in the middle of the
sequence, so you can't just truncate them from the end. When you get
to 126 and 127, you just go on to the next number without weighing any
sugar. So it takes 127 weight movements. The first few are
(starting with the weight pan empty)
add 1: weight = 1
add 2: weight = 3
rem 1: weight = 2
add 4: weight = 6
add 1: weight = 7
rem 2: weight = 5
rem 1: weight = 4
add 8: weight = 12
add 1: weight = 13
add 2: weight = 15
rem 1: weight = 14
rem 4: weight = 10
add 1: weight = 11
...
A loop something like this will print this table:
int i, gray, prev = 0;
for( i = 1 ; i < 128 ; ++i )
{
gray = i ^ (i >> 1); // this gives the ith number in Gray code
sequence.
if( gray > prev )
printf("add %i: weight = %i\n",prev ^ gray, gray);
else
printf("rem %i: weight = %i\n",prev ^ gray, gray);
prev = gray;
}
Again, this gives the required 125 weights (plus 2 additional ones if
you wanted them) in 127 weight movements.
Dave
On Feb 8, 1:35 pm, bittu wrote:
> This is an altogether different one in the same scenario. You have to
> make 125 packets of sugar with first one weighing 1 kg, second 2 kg,
> third 3 kg etc ...and 125th one weighing 125kg.You can only use one
> pan of the common balance for measurement for weighing sugar, the
> other pan had to be used for weights i.e. weights should be used for
> each weighing.
> It has come into notice that moving weights into and out of the pan of
> the balance takes time and this time depends on the number on the
> number of weights that are moved. For example - If we need to measure
> 4 kg using weights 1 and 3 only, it will take twice as much time
> needed to measure 1 kg. Lets say we want to make sugar packets of
> weights 1,3,4 using weights 1 and 3 only. For this first we measure 1
> kg, with 1 unit of time, we place 3 kg along with 1 kg and measure 4kg
> with again 1 unit of time, and finally we move 1kg out of pan to
> measure 3kg in 1 unit of time. So in 3 units of time we could measure
> 1,3 and 4kg using weights 1 and 3 only.
>
> Now you have to make sugar packets of all weights from 1 to 125 in
> minimum time, in other words in minimum movement of weights. The
> question here is to find out the minimum number of weighs needed and
> the weight of each the weights used and the strategy to be followed
> for the creation of 125 packets of sugar.
>
> Thanks & Regards
> Shashank Mani >>
--
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] Re: array(amazon && microsoft)
@algoseeker mine approach is also the same but m inserting the elements in a min heap and you in a set.. i guess extraction of minimum element will be better in terms of complexity if we use a heap On Wed, Feb 9, 2011 at 10:01 AM, Ujjwal Raj wrote: > I see a scope of optimization in the algo. > In step 2. Before inserting the element a[i][j], you can make sure that > a[i][j-1] and a[i-1][j] are in the set. If not then do no insert a[i][j] in > the heap. (considering the boundary condition, if j-1 < 0 or i-1 < 0 then > assume it is true) > > Correct me if I am wrong. > > > On Tue, Feb 8, 2011 at 11:40 PM, algoseeker wrote: > >> Just coded the solution, it worked on all the test cases described here in >> this thread using the algo i described above :) >> >> The code is available at >> https://github.com/algoseeker/Interview/tree/master/sorting >> >> -- >> 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. > -- With Regards, *Jalaj Jaiswal* (+919019947895) Software developer, Cisco Systems Final Year Undergraduate, IIIT ALLAHABAD -- 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] Re: array(amazon && microsoft)
I see a scope of optimization in the algo. In step 2. Before inserting the element a[i][j], you can make sure that a[i][j-1] and a[i-1][j] are in the set. If not then do no insert a[i][j] in the heap. (considering the boundary condition, if j-1 < 0 or i-1 < 0 then assume it is true) Correct me if I am wrong. On Tue, Feb 8, 2011 at 11:40 PM, algoseeker wrote: > Just coded the solution, it worked on all the test cases described here in > this thread using the algo i described above :) > > The code is available at > https://github.com/algoseeker/Interview/tree/master/sorting > > -- > 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.
Re: [algogeeks] Puzzle Will Stuck
u can find more explanation here: http://www.techinterview.org/post/526370758/100-doors-in-a-row On Tue, Feb 8, 2011 at 12:52 PM, sunny agrawal wrote: > finally all square number gates will be open > > > On Wed, Feb 9, 2011 at 2:10 AM, bittu wrote: > >> There are N doors in a row numbered from 1 to N. Initially all are >> closed. >> Then you make N passes by the N doors. In pass 1 you toggle the all >> the doors (1,2,3,4)starting from the first door. In the second >> pass you toggle every second door(2,4,6,8,...). In the third pass you >> toggle all third doors(3,6,9...).Similarly you make N passes. >> >> Question is what is the state of door k after N passes. >> >> Thanks & Regards >> Shashank >> >> >> -- >> 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. > -- Thank You Rajeev Kumar -- 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] Puzzle Will Stuck
finally all square number gates will be open On Wed, Feb 9, 2011 at 2:10 AM, bittu wrote: > There are N doors in a row numbered from 1 to N. Initially all are > closed. > Then you make N passes by the N doors. In pass 1 you toggle the all > the doors (1,2,3,4)starting from the first door. In the second > pass you toggle every second door(2,4,6,8,...). In the third pass you > toggle all third doors(3,6,9...).Similarly you make N passes. > > Question is what is the state of door k after N passes. > > Thanks & Regards > Shashank >> > > -- > 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] Puzzle Will Stuck
There are N doors in a row numbered from 1 to N. Initially all are closed. Then you make N passes by the N doors. In pass 1 you toggle the all the doors (1,2,3,4)starting from the first door. In the second pass you toggle every second door(2,4,6,8,...). In the third pass you toggle all third doors(3,6,9...).Similarly you make N passes. Question is what is the state of door k after N passes. Thanks & Regards Shashank >> -- 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] Puzzle For Puzzled Minds
This is an altogether different one in the same scenario. You have to make 125 packets of sugar with first one weighing 1 kg, second 2 kg, third 3 kg etc ...and 125th one weighing 125kg.You can only use one pan of the common balance for measurement for weighing sugar, the other pan had to be used for weights i.e. weights should be used for each weighing. It has come into notice that moving weights into and out of the pan of the balance takes time and this time depends on the number on the number of weights that are moved. For example - If we need to measure 4 kg using weights 1 and 3 only, it will take twice as much time needed to measure 1 kg. Lets say we want to make sugar packets of weights 1,3,4 using weights 1 and 3 only. For this first we measure 1 kg, with 1 unit of time, we place 3 kg along with 1 kg and measure 4kg with again 1 unit of time, and finally we move 1kg out of pan to measure 3kg in 1 unit of time. So in 3 units of time we could measure 1,3 and 4kg using weights 1 and 3 only. Now you have to make sugar packets of all weights from 1 to 125 in minimum time, in other words in minimum movement of weights. The question here is to find out the minimum number of weighs needed and the weight of each the weights used and the strategy to be followed for the creation of 125 packets of sugar. Thanks & Regards Shashank Mani >> -- 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] Re: array(amazon && microsoft)
Just coded the solution, it worked on all the test cases described here in this thread using the algo i described above :) The code is available at https://github.com/algoseeker/Interview/tree/master/sorting -- 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] Re: array(amazon && microsoft)
I am not very sure about the correctness of this procedure. But my approach would be as follows: Concept: Maintain a set of numbers in which you maintain the values along with its array indices, such that the next number in the sorted output will be a part of this set. Consider the set contains elements as tuples (i,j) where i,j are the indices of the array of an element. Since, it's a set, we shall not maintain duplicate tuples. 1. Pick a[0][0] and output it as first element in sorted array. 2. Invariant : Whenever you output any element at a[i][j], then we include the elements at a[i+1][j] and a[i][j+1] (checking boundary conditions) in the set i mentioned above, along with the indices. 3. Now, find the smallest element in this set and output it. Suppose it is a[i][j], then repeat step 2 and then again step 3, until we find the set becomes empty. Please check if i am missing something here. -- 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] required .net developer
*please send matching profile to st...@dwlabs.com* Need . net developer Location: Syracuse, NY Duration:6+months Skills: . Must have prior experience developing within C# 3.5 and/or 4.0 framework. Must also have experience developing desktop applications (WPF). -- 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] Re: one more from amazon
@shashank i think there are some duplicate outputs by this algorithm (112,211)... Thanks and regards, Gajendra Dadheech On Mon, Feb 7, 2011 at 2:29 PM, bittu wrote: > @gajendra > > i found that its basically combination problem > we have to print all combination of all number in given range that > can compose a given number > > Examples: > For n = 1, the program should print following: > 1 > > For n = 2, the program should print following: > 1 1 > 2 > > For n = 3, the program should print following: > 1 1 1 > 1 2 > 2 1 > 3 > > For n = 4, the program should print following: > 1 1 1 1 > 1 1 2 > 1 2 1 > 1 3 > 2 1 1 > 2 2 > 3 1 > > and so on … > > Algorithm: > At first position we can have three numbers 1 or 2 or 3. > First put 1 at first position and recursively call for n-1. > Then put 2 at first position and recursively call for n-2. > Then put 3 at first position and recursively call for n-3. > If n becomes 0 then we have formed a combination that compose n, so > print the current combination > > You Can Find generalized Code here You Can make it Customize acc. to > your recq. > > http://codepad.org/uw2K9a2c > > Thanks & Rergards > Shashank Mani >> "The best way to escape from a problem is to solve > it." > > -- > 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.
Re: [algogeeks] Re: fedora 12
o k---thanks mittal -- Thanks & Regards...* *Sudhir Mishra *IT 3rd YEAR* *Motilal Nehru National institute Of Technology-ALLAHABAD. * -- 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
try lazy propogation
On Tue, Feb 8, 2011 at 8:14 PM, Gaurav Saxena wrote:
> 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
> #include
>
>
> #define MAX 30
> #define loop0(i,j) for(int i=0;i #define loop1(i,j) for(int i=1;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 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 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
>>> 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
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 .
>
>
>>>
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
#include
#define MAX 30
#define loop0(i,j) for(int i=0;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 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 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 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 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
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
> 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 gr
Re: [algogeeks] Re: array(amazon && microsoft)
using merge sort takes lot of space complexity.
alternaticely we can solve it using a min- heap
let the array be
0 1 2
0 2 3
1 3 4
then first of all insert top left elemnt in heap(guranteed to be minimum)
heap contans {0}
then and insert elements just greater then i.e to the right and below to it
in heap and remove minimum mark the placea[0][0] as -1and print it. do not
insert if you have -1 over there(avoiding repetition.)
-1 1 2
0 2 3
1 3 4
so now 0 gets printed and in heap we have 0(a[1][0]) and 1(a[0][1]).
now insert element adjacent to a[1][0] i.e 0, now heap contains 1(a[2][0])
and 2[a[1][1]] and 1(a[0][1]).
-1 -1 2
-1 -1 3
-1 3 4
till now printed 0,0
now 1(a[0][1]) gets extracted and and 2 a[0][2] gets in heap so that the
heap now contains 1(a[2][0]) and 2[a[1][1]] and 2 a[0][2]
till now printed 0,0,1
-1 -1 -1
-1 -1 3
-1 -1 4
now 1(a[2][0]) gets extracted and 3 a[2][1] gets in heap and heap now
contains 3 a[2][1] and 2[a[1][1]] and 2 a[0][2]
till now printed 0,0,1,1
do in similar way i hope its better in terms of space complexity and
b/w O(n*n) and O(n*nlog(n*n))
On Tue, Feb 8, 2011 at 6:54 PM, arpit busy in novels <
arpitbhatnagarm...@gmail.com> wrote:
> take 1st as 763 2nd as 753 merge them k[]=76533
>
>
> take 42 as 1st 42 as 2nd merge as l[] 422
> now merge k & l as 7654332 add 2 ie
> a[00] always lowest
>
>
> On Tue, Feb 8, 2011 at 5:47 PM, September5th wrote:
>
>> How do you handle this condition???
>>
>> 1 2 3
>> 2 4 5
>> 3 6 7
>>
>> 3 is smaller than 4~
>>
>> On Feb 8, 2:48 am, arpit busy in novels
>> wrote:
>> > after a bit analysis i stick strongly to my soln :
>> >
>> > 0 1 2 3since element of last row & column will
>> > always be greater than rest of array
>> > 2 2 3 4
>> > 3 3 4 5
>> > 4 5 6 7 take 7654 as 1st & 7543 as 2nd merge
>> them
>> > as k[]
>> >
>> > array reduced to
>> > 0 1 2
>> > 2 2 3
>> > 3 3 4 take 433 as 1st432 as 2nd
>> > merge them as l[]
>> >
>> > 0 1
>> > 2 2 22 & 21 as m[]
>> >
>> > merge all k[] m[] l[] add least element always a[0,0]
>> > ..hope this is clear least on
>> my
>> > side
>>
>> --
>> 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.
>>
>>
>
>
> --
> Arpit Bhatnagar
> (MNIT JAIPUR)
>
> --
> 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.
>
--
With Regards,
*Jalaj Jaiswal* (+919019947895)
Software developer, Cisco Systems
Final Year Undergraduate,
IIIT ALLAHABAD
--
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] Re: array(amazon && microsoft)
as per my analisys sort elements diagonally in the 2d arry. we can define diagonals by a[0,i] to a[i,0] is a[0,i],a[1,i-1],a[2,i-2],.. a[i-1,1],a[i,0], sort the elements if i > col_size then diagonal is a[0,i] is define as a[0,i],a[1,i-1],a[2,i-2]...a[x,i-x] where i-x < col_size, now print the arry normally .. it will print sorted output. --paramesh On Tue, Feb 8, 2011 at 6:54 PM, arpit busy in novels wrote: > take 1st as 763 2nd as 753 merge them k[]=76533 > > take 42 as 1st 42 as 2nd merge as l[] 422 > now merge k & l as 7654332 add 2 ie > a[00] always lowest > > On Tue, Feb 8, 2011 at 5:47 PM, September5th wrote: >> >> How do you handle this condition??? >> >> 1 2 3 >> 2 4 5 >> 3 6 7 >> >> 3 is smaller than 4~ >> >> On Feb 8, 2:48 am, arpit busy in novels >> wrote: >> > after a bit analysis i stick strongly to my soln : >> > >> > 0 1 2 3 since element of last row & column will >> > always be greater than rest of array >> > 2 2 3 4 >> > 3 3 4 5 >> > 4 5 6 7 take 7654 as 1st & 7543 as 2nd merge >> > them >> > as k[] >> > >> > array reduced to >> > 0 1 2 >> > 2 2 3 >> > 3 3 4 take 433 as 1st 432 as 2nd >> > merge them as l[] >> > >> > 0 1 >> > 2 2 22 & 21 as m[] >> > >> > merge all k[] m[] l[] add least element always a[0,0] >> > ..hope this is clear least on >> > my >> > side >> >> -- >> 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. >> > > > > -- > Arpit Bhatnagar > (MNIT JAIPUR) > > -- > 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] Re: array(amazon && microsoft)
@Jalaj: An efficient algorithm follows: 1. Using a data structure (int value, int row, int col), place the first column of the array into a minheap. Because the columns are sorted, the data can simply be copied in order, with row and column numbers appended; no heap ordering operations will be needed to establish the heap condition. 2. Print the root node of the heap. 3. Replace the root node with the element of the array that is in the next column of the same row. If all of the elements in that row have been printed, instead move the last node in the heap into the root position and decrease the heap size by 1. 4. Perform a downheap operation to restore the heap condition. 5. Go back to step 2 if the heap is not empty. Comments: 1. You can interchange "row" and "column" in the above description if you prefer. 2. If the array is of size m by n, then the work involved in this algorithm is O(m n log m) if you use the algorithm as described above, or O(m n log n) if you switch "row" and "column." 3. The heap will have m or n nodes, so you need 3*m or 3*n extra memory. I suppose that we could write this as O(m + n). Dave On Feb 7, 2:43 am, jalaj jaiswal wrote: > You are given a array with rows sorted and column sorted. You have to print > entire array in sorted order. > > -- > With Regards, > *Jalaj Jaiswal* (+919019947895) > Software developer, Cisco Systems > Final Year Undergraduate, > IIIT ALLAHABAD -- 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] Re: array(amazon && microsoft)
take 1st as 763 2nd as 753 merge them k[]=76533 take 42 as 1st 42 as 2nd merge as l[] 422 now merge k & l as 7654332 add 2 ie a[00] always lowest On Tue, Feb 8, 2011 at 5:47 PM, September5th wrote: > How do you handle this condition??? > > 1 2 3 > 2 4 5 > 3 6 7 > > 3 is smaller than 4~ > > On Feb 8, 2:48 am, arpit busy in novels > wrote: > > after a bit analysis i stick strongly to my soln : > > > > 0 1 2 3since element of last row & column will > > always be greater than rest of array > > 2 2 3 4 > > 3 3 4 5 > > 4 5 6 7 take 7654 as 1st & 7543 as 2nd merge > them > > as k[] > > > > array reduced to > > 0 1 2 > > 2 2 3 > > 3 3 4 take 433 as 1st432 as 2nd > > merge them as l[] > > > > 0 1 > > 2 2 22 & 21 as m[] > > > > merge all k[] m[] l[] add least element always a[0,0] > > ..hope this is clear least on my > > side > > -- > 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. > > -- Arpit Bhatnagar (MNIT JAIPUR) -- 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] Re: array(amazon && microsoft)
Merge sort with divide and conquer: suppose n by n array, Method 1. 1-> Get sorted top half and sorted bottom half, (To get sorted top half and sorted bottom half, recursively using this process) 2-> and merge them together. Time complexity: T(n * n) = 2 * T(n/2 * n) + n * n [until only 2 rows left] ==> T(n * n) = n * n * log2 n do not use property " column is sorted " Method 2. 1-> Divide the square into 4 sub area, top-left(A), top-right(B), bottom-left(C), bottom-right(D) 2-> Get every area sorted (recursively) 3-> Connect A and D directly, every cell in D is bigger than every cell in A (call the new sorted array A-D) 4-> Merge B and C, call it B-C 5-> Merge A-D and B-C Time complexity: T(n * n) = 4 * T(n/2 * n/2) + 1.5 * n * n [until only 2 rows left] ==> T(n * n) = 1.5 * n * n * log4 n (a bit faster than method 1) On Feb 7, 4:43 pm, jalaj jaiswal wrote: > You are given a array with rows sorted and column sorted. You have to print > entire array in sorted order. > > -- > With Regards, > *Jalaj Jaiswal* (+919019947895) > Software developer, Cisco Systems > Final Year Undergraduate, > IIIT ALLAHABAD -- 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] Re: array(amazon && microsoft)
How do you handle this condition??? 1 2 3 2 4 5 3 6 7 3 is smaller than 4~ On Feb 8, 2:48 am, arpit busy in novels wrote: > after a bit analysis i stick strongly to my soln : > > 0 1 2 3 since element of last row & column will > always be greater than rest of array > 2 2 3 4 > 3 3 4 5 > 4 5 6 7 take 7654 as 1st & 7543 as 2nd merge them > as k[] > > array reduced to > 0 1 2 > 2 2 3 > 3 3 4 take 433 as 1st 432 as 2nd > merge them as l[] > > 0 1 > 2 2 22 & 21 as m[] > > merge all k[] m[] l[] add least element always a[0,0] > ..hope this is clear least on my > side -- 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] Re: fedora 12
search on google for unetbootin. this will help you to create a bootable pen drive from the iso file for any linux distribution. Mohit Mittal -- 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] Re: Find all the subset of an array whose sum is equal to some number
isn't the problem of of genrating all subset e.g. power set & in that power set we have check which subset has the sum value equal to given sum thats it... -- 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
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 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 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 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 >>> 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 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. >> > > > > -- > 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
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 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 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 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 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. > -- 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.gif>><<33F.gif>>
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 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 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 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.
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 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 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.
