Connection Status:
Competition Arena > OneArmedBandit

OneArmedBandit

SRM 226 · 2005-01-05 · by erinn

SRM 226 · 2005-01-05 · by erinn · Math, Simulation
Class Name: OneArmedBandit
Return Type: double
Method Name: progressiveJackpot
Arg Types: (vector<string>, string, vector<string>)
Problem Statement

Problem Statement

You are at the local casino, and notice that the slot machines are set up with a progressive jackpot that continues to grow until someone wins it. Being mathematically-minded, you decide that you will only play the slot machine when the progressive jackpot is high enough that the overall odds are in your favor. In other words, when the expected payout rate is greater than the cost of playing.

Being meticulous, you have taken note of the payoff table for non-jackpot payouts, and have likewise noted the symbols that must line up in order to win the jackpot. Additionally, you have observed many players, and through careful record keeping, have determined the order of the symbols appearing on each on the wheels on the slot machine. It has also been your observation that each wheel appears to operate independently, and has an equal chance of stopping at any given location.

You are given a String[], wheels, where each element of wheels represents the symbols that appear on a wheel of the slot machine. Each character of each element of wheels indicates a single symbol on that wheel. Each symbol is denoted by a capital letter. You are also given a String, jackpotLine, indicating the required symbols to win the jackpot. Finally, you are given a String[], payoffTable, indicating the various ways to win a payout. Each element of payoffTable will be in the form "[payoutLine] [payoutAmount]", where [payoutLine] is the required symbols, and [payoutAmount] is an integer with no leading zeros. A '-' character in any of the payout lines or the jackpotLine indicates that any symbol can appear in that position.

You are to return a double indicating the minimum amount of the progressive jackpot that pushes the overall expected payout rate high enough to make the odds favorable. If the jackpot can never be high enough to make the odds favorable, return -1.

Notes

  • In this example, the slot machine has only a single payout line, and you play only a single coin at a time.
  • The slot machine is set up so that all wheels are equally likely to land on any location.
  • If the symbols line up in such a way that more than one payout line applies, then all applicable payouts are awarded.

Constraints

  • wheels will contain between 1 and 10 elements, inclusive.
  • Each element of wheels will contain between 1 and 50 'A'-'Z' characters, inclusive.
  • Each element of wheels must have the same number of characters.
  • The character length of jackpotLine will be equal to the number of elements in wheels.
  • Each character of jackpotLine will be 'A'-'Z', or a dash ('-').
  • payoffTable will contain between 0 and 50 elements, inclusive.
  • Each element of payoffTable will be of the form "[payoutLine] [payoutAmount]".
  • The character length of [payoutLine] will be equal to the number of elements in wheels.
  • Each character of [payoutLine] will be 'A'-'Z', or a dash ('-').
  • Each value of [payoutAmount] will represent an integer between 1 and 999999, inclusive, with no leading zeros.
  • The expected payout from payoffTable will not be within 1e-6 of 1.
Examples
0)
{"ABC", "ABC", "ABC"}
"AAA"
{"BBB 5", "CCC 2"}
Returns: 20.0

This is a very simple slot machine with three distinct symbols on each of three wheels. The chances of any particular symbol appearing on a specific wheel are 1/3, and hence the chances of any particular line appearing are 1/27. So, the expected payout for the two non-jackpot lines are 5/27 and 2/27, totally 7/27. Our jackpot line needs an expected payout of 20/27 for our total expected payout to let us break even. Using the equation for expected outcome gives us: expected = probability * payout => payout = expected / probability Solving, we need a payout of at least 20 to break even.

1)
{"ABC", "ABC", "ABC"}
"AAA"
{"AAB 4", "AA- 3", "AB- 2"}
Returns: 8.0

We're on the same slot machine, but with a different payout configuration that utilizes the wildcard slot. Here, the probabilities for each of the payout lines are 1/27, 1/9, and 1/9. So, the expected gains are 4/27, 3/9, and 2/9, totalling 19/27. Thus, the jackpot line must have an expected payoff of 8/27. Solving, like above, we need the jackpot to be at least 8.

2)
{"ABC", "ABC", "ABC"}
"AAA"
{"AA- 5", "A-- 2"}
Returns: 0.0

Here we have an interesting scenario, where the machine actually pays out, on average, more than what is put into it, without even considering the big jackpot. So, we don't care what the progressive jackpot is up to.

3)
{"ABC", "ABC", "BBC"}
"AAA"
{"AAB 4", "AA- 3", "AB- 2"}
Returns: -1.0

The casino that is running this machine looks a little shady, since it's not even possible to win the jackpot at all. Therefore, it's never statistically a good idea to play this machine.

4)
{"DABCDBCDCD", "BCDBDACDCD", "DCDADBCDBC", "DBDCABCDCD"}
"AAAA"
{}
Returns: 10000.0

This particular machine is all or nothing. With 10 symbols on each of 4 wheels, you have a 1 in 10,000 chance of hitting the big jackpot.

5)
{"DABCDBCDCD", "BCDBDACDCD", "DCDADBCDBC", "DBDCABCDCD"}
"AAAA"
{"AAAE 20"}
Returns: 10000.0

Here, the only non-jackpot payout is impossible (this is a shady casino!), so this is, in effect, the same as the above example.

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

Coding Area

Language: C++17 · define a public class OneArmedBandit with a public method double progressiveJackpot(vector<string> wheels, string jackpotLine, vector<string> payoffTable) · 42 test cases · 2 s / 256 MB per case

Submitting as anonymous