Connection Status:
Competition Arena > PerfectlyFairGame

PerfectlyFairGame

TCO11 Championship Round · 2011-05-07 · by SnapDragon

TCO11 Championship Round · 2011-05-07 · by SnapDragon · Dynamic Programming, Simple Math
Class Name: PerfectlyFairGame
Return Type: double
Method Name: winChance
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

Dick and Jane are playing a simple game with darts and a board displaying a grid of squares, represented by the String[] board. Each square contains a number from 0 to 9. They each take turns (starting with Dick) tossing a dart at the board. They earn as many points as the number they hit, or 0 points if they miss the board. After each has thrown darts times, the player with the most points wins. If the points end up tied, a fair coin is flipped to determine the winner.


Dick and Jane are equally skilled players, but they are not perfect. If they are aiming at a particular grid square, they actually have a uniform chance of hitting any number in the 3x3 block surrounding it. (They will never aim at a grid square on the edge of the board, since missing is counterproductive.)


Both players play to maximize their odds of winning. Calculate the chance that Jane will win. Since the game is fair and the players are equally skilled, this shouldn't be too hard... right?

Notes

  • The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

  • board will contain between 3 and 20 elements, inclusive.
  • Each character in board will be a digit between '0' and '9', inclusive.
  • Each element of board will contain between 3 and 20 digits, inclusive.
  • Each element of board will contain the same number of digits.
  • darts will be between 1 and 20, inclusive.
Examples
0)
{"123","456","789"}
10
Returns: 0.5

The odds are even, of course.

1)
{"55555","55555","55555","55555","55555"}
20
Returns: 0.5

Everyone scores 5 points each throw. Still even. Duh.

2)
{"0909","9090","0909","9090"}
20
Returns: 0.5

Yawn. Still even. Have you moved on to the Medium yet?

3)
{"888","808","888","000","000","999","999"}
1
Returns: 0.537037037037037

Still ev- ... wait a second. That can't be right, can it?

4)
{"29368","65609","67539","57982","71709"}
5
Returns: 0.5440401329247544

admins: Hi, could you please fix the 250's example output?

5)
{"4225271513","8352579454","1582795371","3365182453","7374843700","3262631490","5261771017","5124728129","1537793032","1147236439"}
20
Returns: 0.5055321764007881

Sigh.

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

Coding Area

Language: C++17 · define a public class PerfectlyFairGame with a public method double winChance(vector<string> board, int darts) · 27 test cases · 2 s / 256 MB per case

Submitting as anonymous