Re: [algogeeks] Re: probability

[Salil Joshi]

@Dave
In point # 1, I had mentioned that P(A survives) + P(B survives)  + P(C
survives) = 1 as the dual will be carried out till only 1 man is left. Do
you agree on this?

By your calculations, P(A survives) = 0.17 * 1 + 0.5 = 0.67
P(C survives) = 0.4962
They add to more than 1. Please let me know your views.



On Mon, Jan 3, 2011 at 11:34 AM, Dave  wrote:

> @Salil. The point that is incorrect is:
> 2. Now, by shooting in air C increases his probability by your
> argument,
> which is not good for A.
> Thus, P(A shooting at C) should NOT be 0 if A is intelligent.
>
> If A shoots C, then B hits A with 50% probability, but if A shoots B,
> then C hits A with only 33% probability. Thus, A's probability of
> survival is higher if he shoots B rather than C.
> Hence, P(A survives) = .67 * P(A shoots B) + .5 * P(A shoots C).
> But since P(A shoots B) + P(A shoots C) = 1,  it follows that
> P(A survives) = 0.67 * P(A shoots B) + 0.5 * [1 - P(A shoots B)]
> = 0.17 * P(A shoots B) + 0.5.
> Therefore, P(A survives) is maximized when P(A shoots B) = 1 and P(A
> shoots C) = 0.
>
> Dave
>
> On Jan 2, 11:07 pm, Salil Joshi  wrote:
> > @Dave,
> > Can you please point out which of the 3 points mentioned earlier sounds
> > incorrect? Because I think that this problem is much like the Three Body
> > problem, and we can not just maximize the likelihood for C, ignoring A &
> B.
> > They will also try to maximize their survival likelihood
> >
> >
> >
> >
> >
> > On Mon, Jan 3, 2011 at 1:34 AM, Dave  wrote:
> > > @Salil: If C shoots at A instead of into the air, he increases the
> > > odds that he will be shot by B, because if C hits A then B will shoot
> > > at C instead of A.
> >
> > > On the other hand, if C shoots at B instead of into the air, he
> > > increases the odds that he will be shot by A.
> >
> > > Thus, shooting at either A or B decreases his odds of survival.
> >
> > > Dave
> >
> > > On Jan 2, 12:25 pm, Salil Joshi  wrote:
> > > > @Dave
> > > > 1. In the end only 1 will survive (after max of 2 rounds).
> > > > i.e. P(A survives in end) + P(B survives in end) + P(C survives in
> end) =
> > > 1
> >
> > > > 2. Now, by shooting in air C increases his probability by your
> argument,
> > > > which is not good for A.
> > > > Thus, P(A shooting at C) should NOT be 0 if A is intelligent.
> >
> > > > 3. If it is not 0, P(C's survival) decreases (doesn't remain
> 0.49624).
> >
> > > > Please let me know if this is clear enough.
> >
> > > > On Sun, Jan 2, 2011 at 11:15 PM, Dave 
> wrote:
> > > > > @Salil: Just to make sure we are on the same page, A hits with 100%
> > > > > probability, B hits with 50% probability, and C hits with 33%
> > > > > probability. C shoots first, then B, then A. Then the shooting
> > > > > continues among the survivors in that order until only one is
> > > > > standing.
> >
> > > > > If all three are alive and it is A's turn to shoot, he logically
> will
> > > > > choose to shoot at B rather than C since B has a greater
> probability
> > > > > of hitting him. Thus, your P(A shooting at C) = 0 if B is unhit
> when
> > > > > it is A's turn.
> >
> > > > > Similarly, if it is B's turn to choose between shooting at A or C,
> he
> > > > > rationally will choose A since A will shoot at and hit B if A gets
> a
> > > > > turn. So your P(B shooting at C) = 0 if A is unhit when it is B's
> > > > > turn.
> >
> > > > > If you dispute either of the above two paragraphs, please clealy
> state
> > > > > your objection.
> >
> > > > > Dave
> >
> > > > > On Jan 1, 11:19 pm, Salil Joshi  wrote:
> > > > > > @Dave,
> > > > > > Yeah, I had read those numbers on internet as this puzzle is well
> > > known.
> > > > > > However I am not convinced with the calculations because of
> following
> > > 2
> > > > > > points:
> >
> > > > > > 1) If C shoots in air, the probability of survival is more for
> the
> > > > > > probabilities considered in the calculations with which A & B
> will
> > > shoot
> > > > > at
> > > > > > him.
> > > > > > Now, if A & B are intelligent, they will know that increasing
> > > survival
> > > > > > probability for C is bad for them (you can calculate survival
> > > probability
> > > > > > for A & B in each case), and therefore they will shoot at C with
> > > higher
> > > > > > probability than what they were planning earlier.
> >
> > > > > > 2) C's survival probability depends on P(A shooting at C) * 1 and
> P(B
> > > > > > shooting at C) * 1/2.
> > > > > > If C shoots at A, P(A shooting at C) is less by 33% and P(B
> shooting
> > > at
> > > > > C)
> > > > > > is more by 33%. So, if P(A shooting at C) dominates by logic in
> 1st
> > > > > point,
> > > > > > C's survival probability will be now more.
> >
> > > > > > On Sun, Jan 2, 2011 at 7:59 AM, Dave 
> > > wrote:
> > > > > > > @Salil: Working out the probabilities, we find that:
> >
> > > > > > > 1. If C initially shoots at A, C's probability of survival is ~
> > > > > > > 0.35867.
> > > > > > > 2. If C initially shoots at B, C's probability of 

[algogeeks] Re: Longest increasing subsequence

[Prims]

Hello Anand

I am getting the error "Blog not found" . Could you please provide me
the correct link.

-Prims

On Dec 31 2010, 1:44 pm, Anand  wrote:
> Longest increasing subsequence using segment tree with O(nlogn)
>
> http://anandtechblog.blogspot.com/2010/12/longest-increasing-subseque...
>
>
>
> On Thu, Dec 30, 2010 at 11:27 PM, juver++  wrote:
> > And of course simple binary search.
>
> > --
> > 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.- Hide quoted text -
>
> - Show quoted text -

-- 
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] Re: probability

[Dave]

@Salil. The point that is incorrect is:
2. Now, by shooting in air C increases his probability by your
argument,
which is not good for A.
Thus, P(A shooting at C) should NOT be 0 if A is intelligent.

If A shoots C, then B hits A with 50% probability, but if A shoots B,
then C hits A with only 33% probability. Thus, A's probability of
survival is higher if he shoots B rather than C.
Hence, P(A survives) = .67 * P(A shoots B) + .5 * P(A shoots C).
But since P(A shoots B) + P(A shoots C) = 1,  it follows that
P(A survives) = 0.67 * P(A shoots B) + 0.5 * [1 - P(A shoots B)]
= 0.17 * P(A shoots B) + 0.5.
Therefore, P(A survives) is maximized when P(A shoots B) = 1 and P(A
shoots C) = 0.

Dave

On Jan 2, 11:07 pm, Salil Joshi  wrote:
> @Dave,
> Can you please point out which of the 3 points mentioned earlier sounds
> incorrect? Because I think that this problem is much like the Three Body
> problem, and we can not just maximize the likelihood for C, ignoring A & B.
> They will also try to maximize their survival likelihood
>
>
>
>
>
> On Mon, Jan 3, 2011 at 1:34 AM, Dave  wrote:
> > @Salil: If C shoots at A instead of into the air, he increases the
> > odds that he will be shot by B, because if C hits A then B will shoot
> > at C instead of A.
>
> > On the other hand, if C shoots at B instead of into the air, he
> > increases the odds that he will be shot by A.
>
> > Thus, shooting at either A or B decreases his odds of survival.
>
> > Dave
>
> > On Jan 2, 12:25 pm, Salil Joshi  wrote:
> > > @Dave
> > > 1. In the end only 1 will survive (after max of 2 rounds).
> > > i.e. P(A survives in end) + P(B survives in end) + P(C survives in end) =
> > 1
>
> > > 2. Now, by shooting in air C increases his probability by your argument,
> > > which is not good for A.
> > > Thus, P(A shooting at C) should NOT be 0 if A is intelligent.
>
> > > 3. If it is not 0, P(C's survival) decreases (doesn't remain 0.49624).
>
> > > Please let me know if this is clear enough.
>
> > > On Sun, Jan 2, 2011 at 11:15 PM, Dave  wrote:
> > > > @Salil: Just to make sure we are on the same page, A hits with 100%
> > > > probability, B hits with 50% probability, and C hits with 33%
> > > > probability. C shoots first, then B, then A. Then the shooting
> > > > continues among the survivors in that order until only one is
> > > > standing.
>
> > > > If all three are alive and it is A's turn to shoot, he logically will
> > > > choose to shoot at B rather than C since B has a greater probability
> > > > of hitting him. Thus, your P(A shooting at C) = 0 if B is unhit when
> > > > it is A's turn.
>
> > > > Similarly, if it is B's turn to choose between shooting at A or C, he
> > > > rationally will choose A since A will shoot at and hit B if A gets a
> > > > turn. So your P(B shooting at C) = 0 if A is unhit when it is B's
> > > > turn.
>
> > > > If you dispute either of the above two paragraphs, please clealy state
> > > > your objection.
>
> > > > Dave
>
> > > > On Jan 1, 11:19 pm, Salil Joshi  wrote:
> > > > > @Dave,
> > > > > Yeah, I had read those numbers on internet as this puzzle is well
> > known.
> > > > > However I am not convinced with the calculations because of following
> > 2
> > > > > points:
>
> > > > > 1) If C shoots in air, the probability of survival is more for the
> > > > > probabilities considered in the calculations with which A & B will
> > shoot
> > > > at
> > > > > him.
> > > > > Now, if A & B are intelligent, they will know that increasing
> > survival
> > > > > probability for C is bad for them (you can calculate survival
> > probability
> > > > > for A & B in each case), and therefore they will shoot at C with
> > higher
> > > > > probability than what they were planning earlier.
>
> > > > > 2) C's survival probability depends on P(A shooting at C) * 1 and P(B
> > > > > shooting at C) * 1/2.
> > > > > If C shoots at A, P(A shooting at C) is less by 33% and P(B shooting
> > at
> > > > C)
> > > > > is more by 33%. So, if P(A shooting at C) dominates by logic in 1st
> > > > point,
> > > > > C's survival probability will be now more.
>
> > > > > On Sun, Jan 2, 2011 at 7:59 AM, Dave 
> > wrote:
> > > > > > @Salil: Working out the probabilities, we find that:
>
> > > > > > 1. If C initially shoots at A, C's probability of survival is ~
> > > > > > 0.35867.
> > > > > > 2. If C initially shoots at B, C's probability of survival is ~
> > > > > > 0.27679.
> > > > > > 3. If C initially shoots in the air, C's probability of survival is
> > ~
> > > > > > 0.49624.
>
> > > > > > Dave
>
> > > > > > On Jan 1, 11:30 am, Salil Joshi  wrote:
> > > > > > > @Rahul,
> > > > > > > As per my understanding,
> > > > > > > In any round P(C is dead) = P(A is alive * A shoots C * A's shot
> > is
> > > > > > > accurate) + P(B is alive * B shoots C * B's shot is accurate)
> > > > > > > this is to be minimized.
> > > > > > > by not shooting at either A or B in 1st chance, how is this
> > > > probability
> > > > > > less
> > > > > > > for C?
>
> > > > >

Re: [algogeeks] Re: probability

[Salil Joshi]

@Dave,
Can you please point out which of the 3 points mentioned earlier sounds
incorrect? Because I think that this problem is much like the Three Body
problem, and we can not just maximize the likelihood for C, ignoring A & B.
They will also try to maximize their survival likelihood.


On Mon, Jan 3, 2011 at 1:34 AM, Dave  wrote:

> @Salil: If C shoots at A instead of into the air, he increases the
> odds that he will be shot by B, because if C hits A then B will shoot
> at C instead of A.
>
> On the other hand, if C shoots at B instead of into the air, he
> increases the odds that he will be shot by A.
>
> Thus, shooting at either A or B decreases his odds of survival.
>
> Dave
>
> On Jan 2, 12:25 pm, Salil Joshi  wrote:
> > @Dave
> > 1. In the end only 1 will survive (after max of 2 rounds).
> > i.e. P(A survives in end) + P(B survives in end) + P(C survives in end) =
> 1
> >
> > 2. Now, by shooting in air C increases his probability by your argument,
> > which is not good for A.
> > Thus, P(A shooting at C) should NOT be 0 if A is intelligent.
> >
> > 3. If it is not 0, P(C's survival) decreases (doesn't remain 0.49624).
> >
> > Please let me know if this is clear enough.
> >
> >
> >
> >
> >
> > On Sun, Jan 2, 2011 at 11:15 PM, Dave  wrote:
> > > @Salil: Just to make sure we are on the same page, A hits with 100%
> > > probability, B hits with 50% probability, and C hits with 33%
> > > probability. C shoots first, then B, then A. Then the shooting
> > > continues among the survivors in that order until only one is
> > > standing.
> >
> > > If all three are alive and it is A's turn to shoot, he logically will
> > > choose to shoot at B rather than C since B has a greater probability
> > > of hitting him. Thus, your P(A shooting at C) = 0 if B is unhit when
> > > it is A's turn.
> >
> > > Similarly, if it is B's turn to choose between shooting at A or C, he
> > > rationally will choose A since A will shoot at and hit B if A gets a
> > > turn. So your P(B shooting at C) = 0 if A is unhit when it is B's
> > > turn.
> >
> > > If you dispute either of the above two paragraphs, please clealy state
> > > your objection.
> >
> > > Dave
> >
> > > On Jan 1, 11:19 pm, Salil Joshi  wrote:
> > > > @Dave,
> > > > Yeah, I had read those numbers on internet as this puzzle is well
> known.
> > > > However I am not convinced with the calculations because of following
> 2
> > > > points:
> >
> > > > 1) If C shoots in air, the probability of survival is more for the
> > > > probabilities considered in the calculations with which A & B will
> shoot
> > > at
> > > > him.
> > > > Now, if A & B are intelligent, they will know that increasing
> survival
> > > > probability for C is bad for them (you can calculate survival
> probability
> > > > for A & B in each case), and therefore they will shoot at C with
> higher
> > > > probability than what they were planning earlier.
> >
> > > > 2) C's survival probability depends on P(A shooting at C) * 1 and P(B
> > > > shooting at C) * 1/2.
> > > > If C shoots at A, P(A shooting at C) is less by 33% and P(B shooting
> at
> > > C)
> > > > is more by 33%. So, if P(A shooting at C) dominates by logic in 1st
> > > point,
> > > > C's survival probability will be now more.
> >
> > > > On Sun, Jan 2, 2011 at 7:59 AM, Dave 
> wrote:
> > > > > @Salil: Working out the probabilities, we find that:
> >
> > > > > 1. If C initially shoots at A, C's probability of survival is ~
> > > > > 0.35867.
> > > > > 2. If C initially shoots at B, C's probability of survival is ~
> > > > > 0.27679.
> > > > > 3. If C initially shoots in the air, C's probability of survival is
> ~
> > > > > 0.49624.
> >
> > > > > Dave
> >
> > > > > On Jan 1, 11:30 am, Salil Joshi  wrote:
> > > > > > @Rahul,
> > > > > > As per my understanding,
> > > > > > In any round P(C is dead) = P(A is alive * A shoots C * A's shot
> is
> > > > > > accurate) + P(B is alive * B shoots C * B's shot is accurate)
> > > > > > this is to be minimized.
> > > > > > by not shooting at either A or B in 1st chance, how is this
> > > probability
> > > > > less
> > > > > > for C?
> >
> > > > > > On Sat, Jan 1, 2011 at 10:43 PM, Salil Joshi <
> > > joshi.sali...@gmail.com
> > > > > >wrote:
> >
> > > > > > > @Rahul,
> > > > > > > What purpose is served by wasting the shot? If C shoots at A or
> B,
> > > at
> > > > > least
> > > > > > > some probability that C is dead in future will be reduced.
> >
> > > > > > > On Sat, Jan 1, 2011 at 10:14 PM, RAHUL KUJUR <
> > > > > kujurismonu2...@gmail.com>wrote:
> >
> > > > > > >> @snehal:
> > > > > > >> will the shooting take place in increasing order of accuracy
> of
> > > > > hitting
> > > > > > >> the target and is that at a time only one person can take a
> > > shot???
> > > > > > >> if yes then
> > > > > > >> @Salil:
> > > > > > >> my answer would be the same as above. what C will do is that
> it
> > > will
> > > > > first
> > > > > > >> let A and B kill each other first.
> > > > > > >> After C wastes his shot it 

Re: [algogeeks] Re: Interview question amazon

[rahul patil]

On Sun, Jan 2, 2011 at 8:30 PM, Akash Agrawal wrote:

> I have written a kinda messed-up code for the same. Which is basically a
> bottom-up approach.
>
> Please find the same as attached. Some boundary conditions might be missed
> and code can be written in a more decorated, beautiful fashion.
>
> Logic:
>
>- start from the root,
>- keep the nodes value in an array.
>- Move up until current node is right child of its parent.
>- then search for value in right sub-tree.(LFS)
>
>
> Regards,
> Akash Agrawal
> http://tech-queries.blogspot.com/
>
>
>
> On Fri, Dec 31, 2010 at 7:59 PM, MAC  wrote:
>
>> No , we had to find all the paths . Some paths could include the root .
>>
>>
>> On Tue, Dec 28, 2010 at 11:12 PM, yq Zhang wrote:
>>
>>> I think the original question says "Path can go from left subtree tree ,
>>> include root and go to right tree as well". This should mean the path must
>>> include the root.
>>>
>>>
>>> On Tue, Dec 28, 2010 at 4:52 AM, shanushaan <
>>> er.srivastavaro...@gmail.com> wrote:
>>>
 Not clear what path you are referring to.

 Question. Should the path include root value always? (What is problem
 with only left or only right path (not containing root))
   In your example for 16 one more path can be 0 1 5 10 as
 well. Should algo return all the paths or just first one.

 On Dec 26, 10:08 pm, MAC  wrote:
 > you are given a bst where each node has a int value , parent pointer ,
 and
 > left and right pointers , write a function to find a path with a given
 sum
 > value. Path can go from left subtree tree , include root and go to
 right
 > tree as well . we need to find these paths also .
 >
 > 5
 >1 10
 > 0 2  6 11
 >
 > so to find 16 we say it is 1 to 5 to 10
 >
 > --
 > thanks
 > --mac

 --
 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.
>>>
>>
>>
>>
>> --
>> thanks
>> --mac
>>
>>  --
>> 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.
>


If we rebuild a tree in which a node can point its parent too(adding extra
field parent in tree node)
then whole tree structure  will look like branched linked list.

Then, it will be easy to find out the best complexity solution with the help
of dynamic programming approach and introducing boundaries.

though it will take extra O(n) space and at max  O(n^2) time complexity.

-- 
Regards,
Rahul Patil

-- 
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] Re: Longest Palindrome

[aniket chatterjee]

@Anand:I went through the link posted in your blog.But I found the
method little bit hard to understand.
@Aviral:Please elaborate the approach or give some link as in your
blog I didn't find the solution.
It will be very helpful.Thanks in advance.

-- 
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] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

[yq Zhang]

keep min for stack is easy. just use another stack to keep the min for each
top.

Sent from Nexus one
On Jan 2, 2011 11:43 AM, "Anuj Kumar"  wrote:
> @juver++ how will implwment find_min() function?
>
> On Sun, Jan 2, 2011 at 2:33 PM, juver++  wrote:
>
>> Simulate queue using two stacks.
>>
>> --
>> 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.
>>
>
>
>
> --
> Anuj Kumar
> Third Year Undergraduate,
> Dept. of Computer Science and Engineering
> NIT Durgapur
>
> --
> 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] Re: probability

[Dave]

@Salil: If C shoots at A instead of into the air, he increases the
odds that he will be shot by B, because if C hits A then B will shoot
at C instead of A.

On the other hand, if C shoots at B instead of into the air, he
increases the odds that he will be shot by A.

Thus, shooting at either A or B decreases his odds of survival.

Dave

On Jan 2, 12:25 pm, Salil Joshi  wrote:
> @Dave
> 1. In the end only 1 will survive (after max of 2 rounds).
> i.e. P(A survives in end) + P(B survives in end) + P(C survives in end) = 1
>
> 2. Now, by shooting in air C increases his probability by your argument,
> which is not good for A.
> Thus, P(A shooting at C) should NOT be 0 if A is intelligent.
>
> 3. If it is not 0, P(C's survival) decreases (doesn't remain 0.49624).
>
> Please let me know if this is clear enough.
>
>
>
>
>
> On Sun, Jan 2, 2011 at 11:15 PM, Dave  wrote:
> > @Salil: Just to make sure we are on the same page, A hits with 100%
> > probability, B hits with 50% probability, and C hits with 33%
> > probability. C shoots first, then B, then A. Then the shooting
> > continues among the survivors in that order until only one is
> > standing.
>
> > If all three are alive and it is A's turn to shoot, he logically will
> > choose to shoot at B rather than C since B has a greater probability
> > of hitting him. Thus, your P(A shooting at C) = 0 if B is unhit when
> > it is A's turn.
>
> > Similarly, if it is B's turn to choose between shooting at A or C, he
> > rationally will choose A since A will shoot at and hit B if A gets a
> > turn. So your P(B shooting at C) = 0 if A is unhit when it is B's
> > turn.
>
> > If you dispute either of the above two paragraphs, please clealy state
> > your objection.
>
> > Dave
>
> > On Jan 1, 11:19 pm, Salil Joshi  wrote:
> > > @Dave,
> > > Yeah, I had read those numbers on internet as this puzzle is well known.
> > > However I am not convinced with the calculations because of following 2
> > > points:
>
> > > 1) If C shoots in air, the probability of survival is more for the
> > > probabilities considered in the calculations with which A & B will shoot
> > at
> > > him.
> > > Now, if A & B are intelligent, they will know that increasing survival
> > > probability for C is bad for them (you can calculate survival probability
> > > for A & B in each case), and therefore they will shoot at C with higher
> > > probability than what they were planning earlier.
>
> > > 2) C's survival probability depends on P(A shooting at C) * 1 and P(B
> > > shooting at C) * 1/2.
> > > If C shoots at A, P(A shooting at C) is less by 33% and P(B shooting at
> > C)
> > > is more by 33%. So, if P(A shooting at C) dominates by logic in 1st
> > point,
> > > C's survival probability will be now more.
>
> > > On Sun, Jan 2, 2011 at 7:59 AM, Dave  wrote:
> > > > @Salil: Working out the probabilities, we find that:
>
> > > > 1. If C initially shoots at A, C's probability of survival is ~
> > > > 0.35867.
> > > > 2. If C initially shoots at B, C's probability of survival is ~
> > > > 0.27679.
> > > > 3. If C initially shoots in the air, C's probability of survival is ~
> > > > 0.49624.
>
> > > > Dave
>
> > > > On Jan 1, 11:30 am, Salil Joshi  wrote:
> > > > > @Rahul,
> > > > > As per my understanding,
> > > > > In any round P(C is dead) = P(A is alive * A shoots C * A's shot is
> > > > > accurate) + P(B is alive * B shoots C * B's shot is accurate)
> > > > > this is to be minimized.
> > > > > by not shooting at either A or B in 1st chance, how is this
> > probability
> > > > less
> > > > > for C?
>
> > > > > On Sat, Jan 1, 2011 at 10:43 PM, Salil Joshi <
> > joshi.sali...@gmail.com
> > > > >wrote:
>
> > > > > > @Rahul,
> > > > > > What purpose is served by wasting the shot? If C shoots at A or B,
> > at
> > > > least
> > > > > > some probability that C is dead in future will be reduced.
>
> > > > > > On Sat, Jan 1, 2011 at 10:14 PM, RAHUL KUJUR <
> > > > kujurismonu2...@gmail.com>wrote:
>
> > > > > >> @snehal:
> > > > > >> will the shooting take place in increasing order of accuracy of
> > > > hitting
> > > > > >> the target and is that at a time only one person can take a
> > shot???
> > > > > >> if yes then
> > > > > >> @Salil:
> > > > > >> my answer would be the same as above. what C will do is that it
> > will
> > > > first
> > > > > >> let A and B kill each other first.
> > > > > >> After C wastes his shot it will be B's turn. B can kill C, but in
> > that
> > > > > >> case the turn would go to A and he would surely kill B. If B goes
> > > > after A,
> > > > > >> then B may hit it or miss it(as its probability of hitting is 50%)
> > > > > >> If B misses it
> > > > > >> then
> > > > > >> it depends on A whom to kill. A may kill B or C. A will try to
> > kill
> > > > one
> > > > > >> who is better shooter i.e. B as C is less likely to hit A.
> > > > > >> If B hits A then we are done. Round 1 is complete(as required in
> > the
> > > > > >> question) and C survives the first round.
> > > > > >> Look th

[algogeeks] Re: Longest Palindrome

[Aviral Gupta]

Use suffix tree ...
http://coders-stop.blogspot.com/2010/11/suffix-trees.html

On Dec 31 2010, 3:19 am, Anand  wrote:
> http://anandtechblog.blogspot.com/2010/06/find-longest-palindromic-su...
>
> On Thu, Dec 30, 2010 at 1:10 PM, Aniket  wrote:
> > How do you find the longest palindrome in a given string in O(n) time?
>
> > --
> > 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.

Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

[Anuj Kumar]

@juver++ how will implwment find_min() function?

On Sun, Jan 2, 2011 at 2:33 PM, juver++  wrote:

> Simulate queue using two stacks.
>
> --
> 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.
>



-- 
Anuj Kumar
Third Year Undergraduate,
Dept. of Computer Science and Engineering
NIT Durgapur

-- 
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] Re: codechef jan challenge

[juver++]

Solve it by yourslef.

-- 
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] Re: probability

[Salil Joshi]

@Dave
1. In the end only 1 will survive (after max of 2 rounds).
i.e. P(A survives in end) + P(B survives in end) + P(C survives in end) = 1

2. Now, by shooting in air C increases his probability by your argument,
which is not good for A.
Thus, P(A shooting at C) should NOT be 0 if A is intelligent.

3. If it is not 0, P(C's survival) decreases (doesn't remain 0.49624).

Please let me know if this is clear enough.



On Sun, Jan 2, 2011 at 11:15 PM, Dave  wrote:

> @Salil: Just to make sure we are on the same page, A hits with 100%
> probability, B hits with 50% probability, and C hits with 33%
> probability. C shoots first, then B, then A. Then the shooting
> continues among the survivors in that order until only one is
> standing.
>
> If all three are alive and it is A's turn to shoot, he logically will
> choose to shoot at B rather than C since B has a greater probability
> of hitting him. Thus, your P(A shooting at C) = 0 if B is unhit when
> it is A's turn.
>
> Similarly, if it is B's turn to choose between shooting at A or C, he
> rationally will choose A since A will shoot at and hit B if A gets a
> turn. So your P(B shooting at C) = 0 if A is unhit when it is B's
> turn.
>
> If you dispute either of the above two paragraphs, please clealy state
> your objection.
>
> Dave
>
> On Jan 1, 11:19 pm, Salil Joshi  wrote:
> > @Dave,
> > Yeah, I had read those numbers on internet as this puzzle is well known.
> > However I am not convinced with the calculations because of following 2
> > points:
> >
> > 1) If C shoots in air, the probability of survival is more for the
> > probabilities considered in the calculations with which A & B will shoot
> at
> > him.
> > Now, if A & B are intelligent, they will know that increasing survival
> > probability for C is bad for them (you can calculate survival probability
> > for A & B in each case), and therefore they will shoot at C with higher
> > probability than what they were planning earlier.
> >
> > 2) C's survival probability depends on P(A shooting at C) * 1 and P(B
> > shooting at C) * 1/2.
> > If C shoots at A, P(A shooting at C) is less by 33% and P(B shooting at
> C)
> > is more by 33%. So, if P(A shooting at C) dominates by logic in 1st
> point,
> > C's survival probability will be now more.
> >
> >
> >
> >
> >
> > On Sun, Jan 2, 2011 at 7:59 AM, Dave  wrote:
> > > @Salil: Working out the probabilities, we find that:
> >
> > > 1. If C initially shoots at A, C's probability of survival is ~
> > > 0.35867.
> > > 2. If C initially shoots at B, C's probability of survival is ~
> > > 0.27679.
> > > 3. If C initially shoots in the air, C's probability of survival is ~
> > > 0.49624.
> >
> > > Dave
> >
> > > On Jan 1, 11:30 am, Salil Joshi  wrote:
> > > > @Rahul,
> > > > As per my understanding,
> > > > In any round P(C is dead) = P(A is alive * A shoots C * A's shot is
> > > > accurate) + P(B is alive * B shoots C * B's shot is accurate)
> > > > this is to be minimized.
> > > > by not shooting at either A or B in 1st chance, how is this
> probability
> > > less
> > > > for C?
> >
> > > > On Sat, Jan 1, 2011 at 10:43 PM, Salil Joshi <
> joshi.sali...@gmail.com
> > > >wrote:
> >
> > > > > @Rahul,
> > > > > What purpose is served by wasting the shot? If C shoots at A or B,
> at
> > > least
> > > > > some probability that C is dead in future will be reduced.
> >
> > > > > On Sat, Jan 1, 2011 at 10:14 PM, RAHUL KUJUR <
> > > kujurismonu2...@gmail.com>wrote:
> >
> > > > >> @snehal:
> > > > >> will the shooting take place in increasing order of accuracy of
> > > hitting
> > > > >> the target and is that at a time only one person can take a
> shot???
> > > > >> if yes then
> > > > >> @Salil:
> > > > >> my answer would be the same as above. what C will do is that it
> will
> > > first
> > > > >> let A and B kill each other first.
> > > > >> After C wastes his shot it will be B's turn. B can kill C, but in
> that
> > > > >> case the turn would go to A and he would surely kill B. If B goes
> > > after A,
> > > > >> then B may hit it or miss it(as its probability of hitting is 50%)
> > > > >> If B misses it
> > > > >> then
> > > > >> it depends on A whom to kill. A may kill B or C. A will try to
> kill
> > > one
> > > > >> who is better shooter i.e. B as C is less likely to hit A.
> > > > >> If B hits A then we are done. Round 1 is complete(as required in
> the
> > > > >> question) and C survives the first round.
> > > > >> Look the problem is not that who gets killed at last but rather
> what C
> > > > >> should fire in the first round obviously to survive(as I
> understood
> > > the
> > > > >> problem). It may happen that eventually C gets killed. But what
> should
> > > C
> > > > >> shoot in first round to survive.
> >
> > > > >> --
> > > > >> 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 gr

Re: [algogeeks] Re: Float Comparison

[aniket chatterjee]

This link may be helpful:

http://www.cygnus-software.com/papers/comparingfloats/Comparing%20floating%20point%20numbers.htm

-- 
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

[radha krishnan]

Wow: Its a Running Contest :)

On Sun, Jan 2, 2011 at 11:07 PM, sanchit mittal  wrote:
> http://www.codechef.com/JAN11/problems/FLUSHOT/
> m getting wrong answer
> if there is any problem wid my algorythm do let me know
>
>> #include
>>
>> 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;i>
>>         {
>>
>>             scanf("%f",&x[i]);
>>
>>             }
>>
>>         if((x[1]+x[0])<=T || x[0]==0)
>>
>>         {
>>
>>             maxNo=x[0];
>>
>>             for(i=1;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;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] Re: probability

[Dave]

@Salil: Just to make sure we are on the same page, A hits with 100%
probability, B hits with 50% probability, and C hits with 33%
probability. C shoots first, then B, then A. Then the shooting
continues among the survivors in that order until only one is
standing.

If all three are alive and it is A's turn to shoot, he logically will
choose to shoot at B rather than C since B has a greater probability
of hitting him. Thus, your P(A shooting at C) = 0 if B is unhit when
it is A's turn.

Similarly, if it is B's turn to choose between shooting at A or C, he
rationally will choose A since A will shoot at and hit B if A gets a
turn. So your P(B shooting at C) = 0 if A is unhit when it is B's
turn.

If you dispute either of the above two paragraphs, please clealy state
your objection.

Dave

On Jan 1, 11:19 pm, Salil Joshi  wrote:
> @Dave,
> Yeah, I had read those numbers on internet as this puzzle is well known.
> However I am not convinced with the calculations because of following 2
> points:
>
> 1) If C shoots in air, the probability of survival is more for the
> probabilities considered in the calculations with which A & B will shoot at
> him.
> Now, if A & B are intelligent, they will know that increasing survival
> probability for C is bad for them (you can calculate survival probability
> for A & B in each case), and therefore they will shoot at C with higher
> probability than what they were planning earlier.
>
> 2) C's survival probability depends on P(A shooting at C) * 1 and P(B
> shooting at C) * 1/2.
> If C shoots at A, P(A shooting at C) is less by 33% and P(B shooting at C)
> is more by 33%. So, if P(A shooting at C) dominates by logic in 1st point,
> C's survival probability will be now more.
>
>
>
>
>
> On Sun, Jan 2, 2011 at 7:59 AM, Dave  wrote:
> > @Salil: Working out the probabilities, we find that:
>
> > 1. If C initially shoots at A, C's probability of survival is ~
> > 0.35867.
> > 2. If C initially shoots at B, C's probability of survival is ~
> > 0.27679.
> > 3. If C initially shoots in the air, C's probability of survival is ~
> > 0.49624.
>
> > Dave
>
> > On Jan 1, 11:30 am, Salil Joshi  wrote:
> > > @Rahul,
> > > As per my understanding,
> > > In any round P(C is dead) = P(A is alive * A shoots C * A's shot is
> > > accurate) + P(B is alive * B shoots C * B's shot is accurate)
> > > this is to be minimized.
> > > by not shooting at either A or B in 1st chance, how is this probability
> > less
> > > for C?
>
> > > On Sat, Jan 1, 2011 at 10:43 PM, Salil Joshi  > >wrote:
>
> > > > @Rahul,
> > > > What purpose is served by wasting the shot? If C shoots at A or B, at
> > least
> > > > some probability that C is dead in future will be reduced.
>
> > > > On Sat, Jan 1, 2011 at 10:14 PM, RAHUL KUJUR <
> > kujurismonu2...@gmail.com>wrote:
>
> > > >> @snehal:
> > > >> will the shooting take place in increasing order of accuracy of
> > hitting
> > > >> the target and is that at a time only one person can take a shot???
> > > >> if yes then
> > > >> @Salil:
> > > >> my answer would be the same as above. what C will do is that it will
> > first
> > > >> let A and B kill each other first.
> > > >> After C wastes his shot it will be B's turn. B can kill C, but in that
> > > >> case the turn would go to A and he would surely kill B. If B goes
> > after A,
> > > >> then B may hit it or miss it(as its probability of hitting is 50%)
> > > >> If B misses it
> > > >> then
> > > >> it depends on A whom to kill. A may kill B or C. A will try to kill
> > one
> > > >> who is better shooter i.e. B as C is less likely to hit A.
> > > >> If B hits A then we are done. Round 1 is complete(as required in the
> > > >> question) and C survives the first round.
> > > >> Look the problem is not that who gets killed at last but rather what C
> > > >> should fire in the first round obviously to survive(as I understood
> > the
> > > >> problem). It may happen that eventually C gets killed. But what should
> > C
> > > >> shoot in first round to survive.
>
> > > >> --
> > > >> 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.
>
> > > > --
>
> > > > 
> > > > Thanks & Regards
> > > > Salil Joshi.
> > > > CSE MTech II, IITB
> > > > A-414, Hostel 12
> > > > +91.9819.442.865
>
> > > > This is a confidential E-Mail. If it has reached you by mistake or if
> > you
> > > > are not the intended receiver, please send it back to me.
>
> > > --
>
> > > 
> > > Thanks & Regards
> > > Salil Joshi.
> > > CSE MTech II, IITB
> > > A-414, Hostel 12
> > > +91.9819.442.865
>
> > > This is a confidential E-Mail. If it has reached you by mistake or if you
> > > are not the inten

[algogeeks] codechef jan challenge

[sanchit mittal]

http://www.codechef.com/JAN11/problems/FLUSHOT/

*m getting wrong answer*
*if there is any problem wid my algorythm do let me know*


#include


> 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;imaxNo)

   maxNo=x[i];

  }



}

else

{maxNo=0.0;

 j=0;

 for(i=0;imaxNo)

   { 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.

[algogeeks] Enigma - Online Puzzle championship

[Manjunath Manohar]

Hi

Enigma - Online puzzle championship organised by Kurukshetra, international
tech fest of anna university under the patronage of UNESCO.

So what u guys waiting for, exciting prizes are awaiting you.

www.enigma.kurukshetra.org.in

Regards,
Enigma Team
+91 9940014458

-- 
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] Re: Float Comparison

[sanchit mittal]

oups gt my mistake.btw hnx for replying

On Sun, Jan 2, 2011 at 10:10 PM, juver++  wrote:

> There is no need in epsilon comparison when you need to compare it with <
> or > operators.
>
> --
> 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.
>



-- 
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] Re: Float Comparison

[sanchit mittal]

#include
#include
int main()
{
int t,D,N,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;imaxNo)
   maxNo=x[i];
  }

}
else
{
 for(i=0;imaxNo)
  { printf("max, y%d %f, %f\n",i,maxNo,y[i]);/*here is the
problem max before entering this loop evrytym has value 0.000 which i hav
changed evrytym */
   maxNo=y[i];
   printf("maxafter %f",maxNo);}

 if(y[i] wrote:

> There is no need in epsilon comparison when you need to compare it with <
> or > operators.
>
> --
> 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.
>



-- 
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] Re: Float Comparison

[juver++]

There is no need in epsilon comparison when you need to compare it with < or 
> operators.

-- 
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] Re: Float Comparison

[sanchit mittal]

i dont know how shud i modify my code using epsilon shall i mail it to
someone or straightaway post it here .?


On Sun, Jan 2, 2011 at 9:58 PM, sanchit mittal  wrote:

> i was doin a check on which one of the two floats is greater using > sign
> but was unable to do soi m actually solving this prob:
> http://www.codechef.com/JAN11/problems/FLUSHOT/
>  i hav code wid me shud i
> post it here?
>
>
> On Sun, Jan 2, 2011 at 9:13 PM, juver++  wrote:
>
>> a == b ==> a < b - EPS
>> a <= b ==> a < b + EPS
>>
>> all other relations are straighforward.
>>
>>  --
>> 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.
>>
>
>
>
> --
> Sanchit Mittal
> Department of Computer Engineering
> Delhi College of Engineering
> ph- +919582414494
>



-- 
Sanchit Mittal
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] Re: Float Comparison

[sanchit mittal]

i was doin a check on which one of the two floats is greater using > sign
but was unable to do soi m actually solving this prob:
http://www.codechef.com/JAN11/problems/FLUSHOT/
i hav code wid me shud i
post it here?

On Sun, Jan 2, 2011 at 9:13 PM, juver++  wrote:

> a == b ==> a < b - EPS
> a <= b ==> a < b + EPS
>
> all other relations are straighforward.
>
>  --
> 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.
>



-- 
Sanchit Mittal
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] Plz Explain The Output.

[juver++]

char type is signed by default, so it represents value 255 as -1.
Code outputs first byte as unsigned int value, where -1 == 4294967295.

-- 
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] Re: Float Comparison

[juver++]

a == b ==> a < b - EPS
a <= b ==> a < b + EPS

all other relations are straighforward.

-- 
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] Re: Interview question amazon

[Akash Agrawal]

I have written a kinda messed-up code for the same. Which is basically a
bottom-up approach.

Please find the same as attached. Some boundary conditions might be missed
and code can be written in a more decorated, beautiful fashion.

Logic:

   - start from the root,
   - keep the nodes value in an array.
   - Move up until current node is right child of its parent.
   - then search for value in right sub-tree.(LFS)


Regards,
Akash Agrawal
http://tech-queries.blogspot.com/


On Fri, Dec 31, 2010 at 7:59 PM, MAC  wrote:

> No , we had to find all the paths . Some paths could include the root .
>
>
> On Tue, Dec 28, 2010 at 11:12 PM, yq Zhang  wrote:
>
>> I think the original question says "Path can go from left subtree tree ,
>> include root and go to right tree as well". This should mean the path must
>> include the root.
>>
>>
>> On Tue, Dec 28, 2010 at 4:52 AM, shanushaan > > wrote:
>>
>>> Not clear what path you are referring to.
>>>
>>> Question. Should the path include root value always? (What is problem
>>> with only left or only right path (not containing root))
>>>   In your example for 16 one more path can be 0 1 5 10 as
>>> well. Should algo return all the paths or just first one.
>>>
>>> On Dec 26, 10:08 pm, MAC  wrote:
>>> > you are given a bst where each node has a int value , parent pointer ,
>>> and
>>> > left and right pointers , write a function to find a path with a given
>>> sum
>>> > value. Path can go from left subtree tree , include root and go to
>>> right
>>> > tree as well . we need to find these paths also .
>>> >
>>> > 5
>>> >1 10
>>> > 0 2  6 11
>>> >
>>> > so to find 16 we say it is 1 to 5 to 10
>>> >
>>> > --
>>> > thanks
>>> > --mac
>>>
>>> --
>>> 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.
>>
>
>
>
> --
> thanks
> --mac
>
>  --
> 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.



treesum.cc
Description: Binary data

Re: [algogeeks] Find a specific number in a special matrix.

[jai gupta]

For n x m take first element of all the rows and insert in a min heap.
Now take the smallest element and and if we have a track of from which row
it belongs, we can take an element out of that row
and insert in the heap.
this will be done n x m times. Hence we have a time complexity of
O(nmlog(m))

-- 
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] puzzle

[jai gupta]

@swayambhoo:
ofcourse a cubical room must me symmetrical at allcorners, Hence, neway it
will reach in
min_dis=sqrt((4+3)^2+5^2)=8.6

-- 
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] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

[juver++]

Simulate queue using two stacks.

-- 
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.