Home » Interview » Dynamic Programming » New 21 Game

New 21 Game


New 21 Game is a problem that is based on the card game “21”. The problem statement of this problem is simple. We are initially having 0 points. If the value of our current points is less than K points then we draw numbers. During each draw we gain an integer number D points randomly from range 1 to M. Each draw does not depend upon the previous draw. At each draw, the outcome has equal probabilities. Once we hit the points greater than or equal to K point then stop drawing the number. We have to find out the probability that we have less than N points.

Input Format

First-line containing three integer numbers N, K and M.

Output Format

Print the single float type variable containing probability such that absolute error less than 10^-5.

Constraints

  • 0<=K<=N<=10000.
  • 1<=M<=10000.

Sample Input: N=6, K=1, M=10

Sample Output: 0.600000

Explanation: We get a single card, then stops. In 6 out of W = 10 possibilities, our points below N = 6 points.

Working Process For New 21 Game

By the use of the Dynamic Programming approach for finding the solution here. DP[n] = sum(dp from n-W to n-1)/W, since we can reach score n by being at score n-1 and drawing a 1, or being at score n-2 and drawing a 2, and so on. The chance of being at score n-i and drawing i is dp[n-i]/W. However, if we’ve stopped drawing, then we need to sum from n-W to K-1. So properly, dp[n] = sum(dp from max(n-W, 0) to min(n-1, K))/W. The final result is the sum of dp in the range [K, N], since the set of possible end scores are K to K + W – 1, (as such the sum of dp from K to K + W – 1 should be 1.0 if we actually computed the whole vector) and we’re looking for the chance of ending up with a score below or equal to N.

READ  Coin Change Problem

Therefore, the chance of getting N or less points is the chance of ending at K (dp[K]), plus the chance of ending at K+1, and so on up to N.

Algorithm For New 21 Game

Step:1 Find the maximum possible score(m_score) which we reach(min(N,K+M-1)).
Step:2 Create a array of type double for storing the probabilities at each instant.
Step:3 Set DP[0] = 1.00
Step:4 Set windowsum = 0.0
Step:5 For i in range 0 to maximum possible score(m_score):
           if i is less than K then:
              windowsum+=DP[i]
           if i is greater than or equal to M then:
              windowsum-=DP[i]
           DP[i+1] = windowsum/M
Step:6 The final result is the sum of dp in range [K, N].

Implementation For New 21 Game

/*C++ Implementation of "New 21 Game" using DP approach.*/ 
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{
    /*input values.*/
    int n,k,m;
    cin>>n>>k>>m;
    int m_score = min(n, k+m-1);
    /*dp[n] is the probability that score n will be reached at some point.*/
    vector<double> dp(m_score+5);
    /*Since the game starts at score 0, dp[0] is 100%.*/
    dp[0] = 1.0;
    /* dp[n] = sum(dp from n-W to n-1)/W, since we can reach score n by being
       at score n-1 and drawing a 1, or being at score n-2 and drawing a 2, and
       so on. The chance of being at score n-i and drawing an i is dp[n-i]/W.
       However, if we've stopped drawing, then we need to sum from n-W to K-1.
       So properly, dp[n] = sum(dp from max(n-W, 0) to min(n-1, K))/W. */
    
    // wsum, the windowed sum, is the sum or the last W elements, or properly
    // sum(dp from max(n-W, 0) to min(n-1, K)). The next element is wsum/W.
    double wsum = 0.0;
    /*Windowed.*/
    for(int i=0;i<=m_score;++i) 
    { 
        if(i<k) 
        {
            // Only add to wsum if we're still drawing.
            wsum += dp[i];
        }
        if(i-m>=0) 
        {
            // Delete last element from window.
            wsum-=dp[i-m];
        }
        dp[i+1]=wsum/m;
    }
    /*    
    The final result is the sum of dp in range [K, N], since the set of
    possible end scores are K to K + W - 1, (as such the sum of dp from K
    to K + W - 1 should be 1.0 if we actually computed the whole vector) and
    we're looking for the chance of ending up with a score below or equal to N.
    Therefore, the chance of getting N or less points is the chance of ending
    at K (dp[K]), plus the chance of ending at K+1, and so on up to N.
    */
    double ans= accumulate(dp.begin()+k, dp.begin()+n+1, 0.0);
    /*print the result.*/
    cout<<fixed<<setprecision(10)<<ans<<endl;
    return 0;
}
6 1 10
0.6000000000

Time Complexity

O(N) where N is the number of points given to us. We run one loop which runs maximum min(K+M-1, N). So we can say that its linear time complexity. We just update our dp array for each value of i where 0<=i<=min(K+M-1,N).

READ  Dynamic Programming Basics

Space Complexity

O(N) where N is the number of points given to us. We use only single dp array of double type of maximum size equal to min(K+M-1, N).

In the worst case, the maximum size possible is O(N).

References