Winning Contest

This is more a computation problem than one of dynamic programming. If $x(n)_j$ is the number of ways that Alice can have a lead of $j$ after $n$ rounds, with the game not having already ended, and if $\mathbf{x}(n)$ is the column vector $\mathbf{x}(n) \; =\; \left( \begin{array}{c} x(n)_3 \\ x(n)_2 \\ x(n)_1 \\ x(n)_0 \\ x(n)_{-1} \\ x(n)_{-2} \end{array} \right)$ for any $n \in \mathbf{N}$ , then (by a simple "Pascal's Triangle" argument) $\mathbf{x}(n+1) \; =\; \left(\begin{array}{cccccc} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \end{array} \right) \mathbf{x}(n)$ for any $n \in \mathbf{N}$ , and hence $\mathbf{x}(n) \; = \; \left(\begin{array}{cccccc} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \end{array} \right)^n \left(\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{array} \right)$ and hence the number of ways is $\begin{array}{rcl} \displaystyle \sum_{n=1}^{30} x(n)_3 & = & \displaystyle \sum_{n=1}^{30} \left(\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\right)^T \left(\begin{array}{cccccc} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \end{array} \right)^n \left(\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{array} \right) \\ & = & 0 + 0 + 1 + 0 + 3 + 0 + 9 + 0 + 27 + 0 + 81 + 0 + 243 + 0 + 729 + 0 \\ & & + 2187 + 0 + 6561 + 0 + 19683 + 0 + 59049 + 0 + 177147 + 0 + 531441 + 0 + 1594323 + 0 \\ & = & 2391484 \end{array}$

I don't know what dynamic programming is, any way here is classic "programming way" of doing it :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
using namespace std;

int aliceWon(int r, int A, int B){
    int acc = 0;
    if(A + B <= r && (B - A) != 3){
        if((A - B) == 3){
            acc++;
        }
        else{
            acc += aliceWon(r, A+1, B);
            acc += aliceWon(r, A, B+1);
        }
    }
    return acc;
}

int main(){
    int rnd;
    cin >> rnd;
    cout << aliceWon(rnd, 0, 0);
    return 0;
}

Thanks for the problem.

This is a dynamic programming problem. Let's see why:

• Given a sequence, either it is a winning sequence, or Bob or Alice is ahead of the other by some points.
• Given a new letter and the status of an old sequence, we can determine what the status of the new sequence is. For example, if we know that in the latest game Alice won and in the sequence before it, Bob was ahead by two points, Bob is now ahead only by one point.

In essence, we need to keep track of just the previous states.

Let us keep two variables:

• alice[i][n] denoting the number of sequences of length n in which Alice is ahead by i points.
• bob[i][n] denoting the number of sequences of length n in which Bob is ahead by i points.

Now, using the above reasoning, we could say that:

1
2
3
4
5
6

alice[2][n] = alice[2][n-1]
bob[2][n] = bob[2][n-1]
alice[1][n] = alice[0][n-1] + alice[2][n-1]
bob[1][n] = bob[0][n-1] + bob[2][n-1]
alice[0][n] = alice[1][n-1] + bob[1][n-1]
bob[0][n] = alice[1][n-1] + bob[1][n-1]

The base case, certainly is:

1
2

alice[i][0] = 0
bob[i][0] = 0

for all i.

To get the value of the answer, we would need to compute another additional value for Alice, the winning sequences:

1

alice[3][n] = alice[2][n]

What we need to compute is the sum of all values of alice[3][n] from n = 1 to 30

See Christopher's solution for the code.

My solution in python 3

1
2
3
4
5
6
7
8
9

def godeep(sofar, level, maxlevel):
   "Winning Contest"
    if level > maxlevel or sofar == -3 :
        return 0
    if sofar == 3:
        return 1
    return godeep(sofar + 1, level + 1, maxlevel) + godeep(sofar - 1, level + 1, maxlevel)

print(godeep(0,0,30)

Output

1

2391484

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <bits/stdc++.h>
using namespace std;

long long dp[5][105];

int main() {

    dp[2][0] = 1;
    for (int i = 1; i <= 30; i++) {
        dp[0][i] = dp[1][i-1];
        dp[1][i] = dp[2][i-1] + dp[0][i-1];
        dp[2][i] = dp[1][i-1] + dp[3][i-1];
        dp[3][i] = dp[2][i-1] + dp[4][i-1];
        dp[4][i] = dp[3][i-1];
    }

    long long ans = 0;
    for (int i = 0; i < 30; i++)
        ans += dp[0][i];

    cout << ans << endl;

    return 0;
}

• dp[0][i] is the number of valid sequence (no one wins yet) such that Alice is 2 more than Bob.
• dp[1][i] is the number of valid sequence (no one wins yet) such that Alice is 1 more than Bob.
• dp[2][i] is the number of valid sequence (no one wins yet) such that Alice is the same as Bob.
• dp[3][i] is the number of valid sequence (no one wins yet) such that Bob is 1 more than Alice.
• dp[4][i] is the number of valid sequence (no one wins yet) such that Bob is 2 more than Alice.

The base case is simple. For $i=0$ , dp[2][0] = 1 and others are 0 . Then, the transition is pretty interesting too : dp[k][i] = dp[k-1][i-1] + dp[k+1][i] . This is due to either Alice or Bob wins can generate dp[k][i] .

Let $f_r(n)$ be the number of possible sequences of length $n$ at the end of which Alice is $r$ rounds ahead. (E.g. $f_2(4)=3$ .)

The number of ways Alice can win after at most $30$ rounds is $f_2(29)+f_2(28)+f_2(27)+...$ .

If Alice is $2$ rounds ahead, 1 round earlier she must have been $1$ round ahead. $f_2(n)=f_1(n-1)$

$f_1(n)=f_2(n-1)+f_0(n-1)$

$f_0(n)=2f_1(n-1)$

Therefore $f_1(n)=3f_1(n-2))$ $f_1(2k)=0$ , $f_1(1)=1$ , so $f_1(2k-1)=3^k$

The number we seek is $f_2(29)+f_2(28)+f_2(27)+...=f_1(28)+f_1(27)+f_1(26)+... = 3^{13}+3^{12}+...+1=\frac{3^{14}-1}{2}$