int no_of_steps[arr_length] = {MAX};
if ( (arr_length==0) || (arr[0] == 0) ) //if there are no elements or
the very first element is 0 - we can't jump anywhere
return MAX;
no_of_steps[0] = 0; //no jumps required to jump from element 0 to itself.
for (int i=1; iarr_length; i++)
{
^ cout no_of_steps[arr_length -1];
On Mon, Jul 9, 2012 at 8:44 PM, algo bard algo.b...@gmail.com wrote:
int no_of_steps[arr_length] = {MAX};
if ( (arr_length==0) || (arr[0] == 0) ) //if there are no elements
or the very first element is 0 - we can't jump anywhere
return MAX;
There is a greedy solution discussion about this approach. I don't have a
formal proof for this.
Any counter example will be helpful.
at every place 'k' .. do the following.
-- find max ( a[k+i]+i ) where 1 = i = a[i]
for the given example:
A = {4 0 0 3 6 5 4 7 1 0 1 2}
initially a 4, the
farthest from
2: Find a vertex v1 | the farthest form r.
3: Find a vertex v2 | the farthest form v1.
won't v2 be farthest from r? or we are talking about alternate pats also
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jun 20, 2012
@ashish it wont be...first we r finding one end from any node dat is r n
den frm dat end we r traversing to other deepest end...
it is possible dat r b d intermediate node...n distance from r to v2 is
smaller than from r to v1
--
You received this message because you are subscribed to the Google
I am asking again .. can any one please suggest better method for getting
the median on the longest path of the tree ..
efficient method .
On Tue, Jun 19, 2012 at 5:08 PM, Nishant Pandey
nishant.bits.me...@gmail.com wrote:
for getting diameter we can simply add the max height of left subtree
As you traverse along and find the diameter of the tree, keep track of the
number of nodes thereby traversed. Let that be equal to n.
Now, centre is the node corresponding to floor((n+1)/2).
On Wed, Jun 20, 2012 at 5:19 PM, Nishant Pandey
nishant.bits.me...@gmail.com wrote:
I am asking again
for getting diameter we can simply add the max height of left subtree and
max height of the right sub tree .
the main issue is how efficiently we find median on that longest path to
get the center of the tree .
can any bdy sugest optimized algo for that ?
On Mon, Jun 18, 2012 at 6:08 PM, rajesh
I found it in some paper ;)
Diameter and center
De nition 4. The diameter of tree is the length of the longest path.
De nition 5. A center is a vertex v such that the longest path from v to a
leaf is minimal
over all vertices in the tree.Tree center(s) can be found using simple
algorithm.
@maddy: The students should be assigned consecutive books only. That is, u
CANNOT assign book 1, 2 and 5 to a single student. either assign book 1, 2
and 3 or 1 and 2 or any such combination of consecutive numbers.
On Thursday, June 14, 2012 12:26:09 PM UTC+5:30, algogeek wrote:
In a
I think this algorithm is used for calculating poset in graph.
On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote:
+ 1 for DK's solution. Is that a standard algorithm coz I feel like I have
heard it somewhere ??
On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com
+ 1 for DK's solution. Is that a standard algorithm coz I feel like I have
heard it somewhere ??
On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote:
@KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3).
Could you please state how you can use the traversals directly to get the
On Jun 16, 2:1@shubham
couldnt understand following logic in you algo please explain
when first k elemnts traversed then traverse again k elemnts of B
and
S[2*k-i]+=B[i])...again S[i-2*k]+=B[i][.so on till B is traversed
completely.
6 am, Shubham Sandeep s.shubhamsand...@gmail.com wrote:
wat
@Dave - Can you please explain how did you generate the series? Shouldn't it
be : 1/2 + 2(1/4) + 3(1/8) and so on?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
Dave shouldn't it be :: E(x) = Summation( xp(x) ) thus it should
be 1*1/2 + 2*(1/2 * 1/2) + 3*(1/2 * 1/2 * 1/2) .
On Sun, Aug 7, 2011 at 11:55 AM, Nitish Garg nitishgarg1...@gmail.comwrote:
@Dave - Can you please explain how did you generate the series? Shouldn't
it be : 1/2 +
Traverse the tree inorder. Store the values in an array. Find the element in
the middle of the array.
On Sun, Aug 7, 2011 at 8:57 AM, subramania jeeva
subramaniaje...@gmail.comwrote:
5
/\
6 7
/
8
Here the centre is both 5 and 6 . we need to find both of them..:)
Probability of getting an even sum in one roll is 1/2..
Thus, expected number of rolls required to get even sum is inverse of that
i.e. 2.
Alternatively, Going by basics...
Let P(x) be probability of getting Even sum in x rolls.
P(1) = 1/2(Even)
P(2) = (1/2) * (1/2) (Odd + Odd)
P(3) = (1/2)
@kunal patil:
how can u say Probability of getting an even sum in one roll is 1/2
if tht is the case..can u find the ans in one go if the dice is having *5
faces*??
i mean the numbers on dice are 1 2 3 4 5 ...and it is unbiased...
what will be the *Probability of getting an even sum in one
@kunal patil
expected number of rolls required to get even sum is inverse of that
i.e. 2
can we say like this all the time ?
i have understood the alternative method, thanks :D
On Sun, Aug 7, 2011 at 1:33 PM, Kunal Patil kp101...@gmail.com wrote:
Probability of getting an even sum in one roll
@Everyone: Wladimir has posted the correct solution to the problem and it is
an O(N) bottom up solution.
*The original solution:*
On Wednesday, 6 October 2010 21:10:40 UTC+5:30, wladimirufc wrote:
Find the leaf of tree then put all leaf in a queue.
While queue not empty:
remove u from
Codechef Ques(Initiative of Directi)
use DFS, BFS or Floyd Warshall... :)
--
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
@kunal patil:
U were proceeding in correct way...in next series u cud hav seen a
formation of arithmatico geometric series...
It doesnt matter what the value of no of faces in a dice is..ans will
be always 2...:)
My simplified soln: o+e+1
o=probability of odd number coming in 1
throw of dice
@KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3).
Could you please state how you can use the traversals directly to get the
center? (And prove your correctness too?)
The solution given by Wladimir ( expanded upon by me) is O(N) and uses
(somewhat) the inverse of a BFS as a traversal.
--
From any node, find the farthest node by DFS, save its location(say
A). Now start DFS from A, and reach the farthest node, say B. AB will
be diameter of tree and longest path. The central node will be the
centre of tree. O(n) solution.
On Jul 27, 1:53 am, sivaviknesh s sivavikne...@gmail.com
@Shady: There is a 1/2 probability of getting an even number on the
first roll. In the 1/2 of the cases where the first roll is odd, roll
again and note that there is a 1/2 chance of getting an odd number.
Etc. The probability of needing n rolls is 1/2 to the nth power.
The series is 1 + 2 *
5
/\
6 7
/
8
Here the centre is both 5 and 6 . we need to find both of them..:)
Cheers
~ Jeeva ~
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
the question is clear..you draw the sample test case and work out ..
you will understand
1
/ / \
4 2 3
/\
5 6
here from node 2 the maximum cost to reach any node 'i' is 2 and
minimum is 1
...so M(2) = max(1,2)=2..the same is the case
we can do like creating an adjacency matrix..populate all values i.e.
cost to reach each node...finally find the nodes that has min value...any
other gud solutions??
On Wed, Jul 27, 2011 at 2:16 AM, sivaviknesh s sivavikne...@gmail.comwrote:
the question is clear..you draw the sample test
I am thinking on these lines.
Start from any node. DFS to the fartheset node from there. let the
farthest node be B. Start a new DFS from B to reach the fartheset node
from B , let that be C. It can be proved that BC is the longest path
in the tree. Then, the node in the center will be the answer
I don't understand what you mean when you say minimum among all the
nodes in the graph.
In any case, your definition of centre of tree looks similar to the
closeness centrality measure -
http://www.faculty.ucr.edu/~hanneman/nettext/C10_Centrality.html#Closeness
I doubt you can do it in O(N)...
30 matches
Mail list logo
