Connection Status:
Competition Arena > ChutesAndLadders

ChutesAndLadders

SRM 258 · 2005-08-10 · by erinn

SRM 258 · 2005-08-10 · by erinn · Dynamic Programming, Math, Simple Search, Iteration, Simulation
Class Name: ChutesAndLadders
Return Type: double[]
Method Name: winningChance
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

The board game Chutes and Ladders consists of 100 spaces, numbered 0 through 99. Initially, each player begins on the space 0. Each player takes turns rolling a pair of typical six-sided dice, and moves the number of spaces indicated on the dice. Each space of the board might be the start of a chute or a ladder, which immediately warps the player backward or forward to another space on the board. Once a player reaches or passes the last space on the board, that player wins the game.

Any space on the board, except for the first (0) or last (99) space, may be the start of a chute, a ladder, or neither. No space will have both a chute and a ladder, and no space will have more than one chute or ladder. A space that begins a chute or ladder will not be the end of another chute or ladder. Furthermore, no two adjacent spaces will both have a chute and/or ladder. A space may, however, be the landing space of more than one chute and/or ladder. There will be, at most, 20 chutes/ladders on the board

You are given int[]s startLadder and endLadder, whose corresponding elements define the starting and ending points of each of the chutes and ladders on the game board. For instance, startLadder[0] is the space that has a chute/ladder which ends at endLadder[0]. You are also given a int[] players indicating the current position of each player on the board. Player 0 will roll next, followed by player 1, etc.

You are to return a double[] indicating the probability of each player winning the game.

Notes

  • The return value must be within 1e-9 absolute or relative error of the actual result.

Constraints

  • startLadder will contain between 0 and 20 elements, inclusive.
  • endLadder will contain the same number of elements as startLadder.
  • Each element of startLadder will be between 1 and 98, inclusive.
  • Each element of endLadder will be between 0 and 98, inclusive.
  • No two elements of startLadder will be the same.
  • No two elements of startLadder will differ by 1.
  • No element of endLadder will equal an element of startLadder.
  • players will contain between 2 and 4 elements, inclusive.
  • Each element of players will be between 0 and 98, inclusive.
  • No element of player will equal an element of startLadder.
Examples
0)
{}
{}
{0, 0}
Returns: {0.6063557826968836, 0.3936442173031164 }

With no chutes or ladders to worry about, this is just a straight ahead race to the finish. As expected, the first player has an advantage.

1)
{ 7, 23, 42, 58, 87}
{35, 91, 11, 31, 22}
{0, 0, 0, 0}
Returns: {0.2850398049975441, 0.2591808222220256, 0.23726366951493458, 0.21851570326549555 }

Here, we've got a few chutes and ladders, and more players, which evens out the odds a bit.

2)
{}
{}
{0, 30}
Returns: {0.013280440302841312, 0.9867195596971587 }

With the second player starting a good way through the game, he has an advantage in spite of rolling second.

3)
{79, 70, 50, 27,  3,  8, 35, 20, 97, 94, 92, 86, 53, 63, 61, 46, 48, 15}
{98, 90, 66, 83, 13, 30, 43, 41, 77, 74, 72, 23, 52, 59, 18, 25, 10,  5}
{21, 32, 56, 41}
Returns: {0.17890364754713348, 0.13868643400691752, 0.5037066355391879, 0.17870328290676118 }
4)
{98, 95, 92, 89, 86, 83, 80, 77, 74, 71,
68, 65, 62, 59, 56, 53, 50, 47, 44, 41}
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
{0, 0, 0, 0}
Returns: {0.25180999320247693, 0.2505990387847734, 0.2493945326404163, 0.2481964353723289 }

Submissions are judged against all 34 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ChutesAndLadders with a public method vector<double> winningChance(vector<int> startLadder, vector<int> endLadder, vector<int> players) · 34 test cases · 2 s / 256 MB per case

Submitting as anonymous