CareerCup

Consider the board as directed graph.
1. k is linked to k + 1 k + 2, k + 3, k + 4, k + 5, k +6 because from k you can reach these nodes in one throw of dice.
2. If any of these neighbors of k has a ladder which takes you to j, then j becomes the neighbor instead of the base of the ladder. Lets say k + 3 node takes you to j node, then instead of k + 3, j is the neighbor of k.
3. Similarly if any of the neighbors of k has a snake which takes you to l, then l is a neighbor of k.

Using these conditions, build the graph. Now this is transformed into a Shortest path between two nodes in a directed graph problem.

Use dynamic programming :
Following is the algorithm :

Let B[100] is the matrix(I am representing the matrix(10*10) as an array(with Mat[j][k] = B[i] where i = 10*(j-1) + k)) 
A[1] = 1;A[2] = 1;A[3] = 1;A[4] = 1;A[5] = 1;A[6] = 1;
for i=7:100
    if B[i] !=  -1  // -1 to represent snake
        A[i] = A[i-1] + 1;
        for j=i-2:i-7
             if A[i] > A[j] + 1
                 A[i] = A[j] + 1;
    else
        A[i] = MAX   /// this is to ignore the value when we calculate minimum.
return A[100]

Here we don't have to consider expectation, as we only need to tell minimum number of dice rolling,

We have 100 squares an some number of ladders leaving some square and arriving at another square.
Form a graph with 100 vertices. From vertex 'm' there is an edge to any of the vertices 'm+1' to 'm+6' (you can get to the corresponding squares from square 'm' in one roll). Now if a ladder leaves square 'l' for square 'a' do this: on the graph remove all edges ending at vertex 'l' and add new edges ending at vertex 'a'. For instance, the edge between 'l-3' and 'l'is replaced with an edge between 'l-3' and 'a'. Note that vertex 'l' will be removed.

The minimum number of die rolls is equal to the shortest path from vertex 1 to vertex 100.

You can model the problem as a directed weighted graph as follows.

1. Each number 1 ,2,3...100 represents a vertex say v1,v2,v3...v100.
2. If there is a ladder from a node vi to vj , there is an edge from vi to vj with weight vj-vi.
3. If there is a snake from a node vi to vj , there is an edge from vi to vj with weight vi-vj.
4. For any two consecutive nodes vi,vi+1 such that neither vi nor vi+1 have a ladder or a snake there is an edge from vi to vi+1 with weight 1.

For this graph problem now reduces to finding shortest path between v0 and v100.

Snakes and Ladder via DP

B[i] contains the snakes and ladder board in flat form (1 to 100). It contains -1 to denote there's a snake and N to denote there's a ladder where N is the number to which that ladder ends, and 0 otherwise.
A[i] where i is from 1 to 100 stores the min number of dice rolls to reach i from start.
A[i] for i = 1 to 100 is INT_MAX.

MinDiceRolls (Psuedocode)
{
for(int i = 1 to 100)
{
if(B[i] == -1) // its a snake and thus, we don't consider this node
continue;

if(B[i] != 0) // ladder
{
// B[i] will always be having the number greater than i as its the point where ladder ends

A[B[i]] = MIN(A[i-1], A[i-2], A[i-3], A[i-4], A[i-5], A[i-6]) + 1; // i.e. equal to min number of dice rolls that would have been required to reach A[i] (if a ladder would not have been there). Please make sure that index does not reach < 1 and A[i] is != -1, ignore that if that's the case.

A[i] = -1; // implies we can never reach this node in any number of dice rolls as this node has ladder.
}
else
{
// normal case
A[i] = MIN(A[i-1], A[i-2], A[i-3], A[i-4], A[i-5], A[i-6]) + 1;
}
}

return A[100];
}

BFS should be used.snakes head and ladders start should be replaced by their respective other ends in the graph.

{{
test

}}

consider board as a graph ,
when there is a ladder , the node at the base points to the node at top (from ladder base to ladder top)..
same way would be used for snakes.

so all we have to do is find shortest path (kruskal or dijikstra),and later divide by 6

dijkstra's algorithm for shortest path. O(vlogv).
as the edge weights are integers from 1-6, its O(v).

sum of non-continuous elements in an array without considering -ve numbers(snake)