Preliminaries

Let \(P_1,P_2,\dots, P_N\) be the numbers on the balls in the order they are drawn from the box. Here, \(P\) is a permutation of \((1,2,\dots, N)\), and all \(N!\) possible permutations \(P\) occur with equal probability. We can therefore think of \(P\) as being chosen uniformly at random and fixed before the game starts, with its entries revealed one by one from the beginning as the game proceeds.

From now on, we will forget about the balls and focus only on their numbers. We say that two numbers can be paired if their sum is less than \(M\). If Alice ever holds two numbers that cannot be paired, her score becomes \(0\). If the score is not \(0\), it is given by the number she holds at the end.

The Optimal Strategy and the Score

Alice’s choice is which of the two numbers she currently holds to keep. She makes this choice \(N-1\) times. Note that when making a choice, she can refer to the set of numbers drawn so far.

Alice’s optimal strategy is as follows. Let the numbers she currently holds be \(x\lt y\).

• If every number that has yet to appear can be paired with \(y\), keep \(y\).
• Otherwise, keep \(x\).

This strategy is optimal because it remains optimal even if Alice knows all of \(P\) while playing the game. In fact, the score obtained by following this strategy is:

• \(0\) if there exists an \(i\in [2,N]\) such that, for every \(j\lt i\), \(P_j\) cannot be paired with \(P_i\).
• Otherwise, the maximum \(P_i\) such that, for every \(j\gt i\), \(P_j\) can be paired with \(P_i\).

Even with full knowledge of \(P\), this score cannot be exceeded. From now on, we will forget about the strategy and regard the permutation \(P\) as determining the score above. Also, since the score is deterministically determined, instead of computing the expected value directly, we will compute the sum of the scores over all permutations \(P\) and divide by \(N!\) at the end.

Insertion DP

If \(M\le N+1\), the number \(N\) cannot be paired with any other number, so the answer is \(0\). If \(M\ge 2N\), any two numbers can be paired, so the answer is \(N\). From now on, assume \(N+2\le M\le 2N-1\). To compute the sum of the scores, we only need to consider permutations \(P\) whose score is not \(0\).

Label each number \(i\) as follows.

• A if \(1\le i\lt M/2\).
• B if \(M/2\le i\le N\).

B-labeled numbers cannot be paired with each other. Thus, at least one of \(P_1,P_2\) is A-labeled. Also, swapping \(P_1,P_2\) does not change the score. Therefore, from now on, we will consider only permutations in which \(P_1\) is A-labeled, and count their contribution to the answer twice when \(P_2\) is B-labeled.

Consider starting with an empty sequence and repeatedly inserting numbers at arbitrary positions in a certain order. From now on, we use “earlier” and “later” to refer to the relative order in which numbers appear in this insertion order, and “left” and “right” to refer to their positions in \(P\). First, consider the following example with \(N=20,M=30\).

1,2,3,4,5,6,7,8,9,20,10,19,11,18,12,17,13,16,14,15
A,A,A,A,A,A,A,A,A,B ,A ,B ,A ,B ,A ,B ,A ,B ,A ,B 

The first line gives the order in which the numbers are inserted, and the second line gives their labels. For general \(N,M\), the order follows these rules.

• First come \(1,2,\dots, M-N-1\). All of these are labeled A.
• Next come \(N,M-N,N-1,M-N+1,\dots\). The labels alternate between B and A; the B-labeled numbers appear in descending order starting from \(N\), and the A-labeled numbers in ascending order starting from \(M-N\).

These labels and this order have the following properties.

• An A-labeled number can be paired with other A-labeled numbers, cannot be paired with earlier B-labeled numbers, and can be paired with later B-labeled numbers.
• A B-labeled number cannot be paired with other B-labeled numbers, can be paired with earlier A-labeled numbers, and cannot be paired with later A-labeled numbers.

When inserting numbers in this order, the condition for the score not to be \(0\) can be expressed as follows.

• Never insert a B-labeled number at the beginning of the sequence as it stands at that moment.

At least one of any two numbers that cannot be paired is B-labeled. If a B-labeled number is not inserted at the beginning, some earlier A-labeled number lies to its left, so the score does not become \(0\). Conversely, if B-labeled numbers are inserted at the beginning, the last such number inserted will either end up at the beginning or have only some later A-labeled numbers to its left, resulting in a score of \(0\).

Next, let us characterize the number that determines the score. First, any number that does not satisfy the following condition cannot determine the score.

• At the time it is inserted, there is no B-labeled number to its right.

This is because it cannot be paired with a B-labeled number that was already to its right when it was inserted. Conversely, the last number inserted that satisfies this condition determines the score. First, let us verify that this number \(x\) can indeed determine the score; that is, Alice can finish with \(x\) in hand. After \(x\) is inserted, in particular, no numbers are inserted to its right. Since there were no B-labeled numbers to its right when it was inserted, whether \(x\) is labeled A or B, it can be paired with every number to its right. Next, let us verify that no number larger than \(x\) can determine the score; that is, Alice cannot finish with a number larger than \(x\) in hand. The case where \(x\) is B-labeled is easy. Only B-labeled numbers can be larger than \(x\), and B-labeled numbers are inserted in descending order. Among the B-labeled numbers, only the rightmost one can determine the score. The case where \(x\) is A-labeled is slightly more involved. All B-labeled numbers that appear earlier than \(x\) lie to the left of \(x\), but they cannot be paired with \(x\), so they cannot determine the score. A-labeled numbers are inserted in ascending order. Thus, any A-labeled number larger than \(x\) appears later than \(x\), but all such numbers have a B-labeled number to their right when they are inserted, so they cannot determine the score either.

Combining these observations, we can design the following insertion DP.

Define \(dp(p,f,x)\coloneqq\) the following sum over all insertion histories characterized by these parameters:

• \(p\): Have we already decided that a number inserted so far will determine the score?
• \(f\): Is the number in position \(2\) of the partially constructed \(P\) B-labeled?
• \(x\): The rightmost B-labeled number in the partially constructed \(P\) is in position \(x\) from the beginning.

Over all such insertion histories, store:

• the sum of \(1\) (the number of ways), when \(p=0\);
• the sum of the scores, when \(p=1\).

For initialization, instead of starting with the empty sequence, use the values corresponding to states in which the first \(M-N\) numbers in the insertion order have already been inserted. This lets us start with a B-labeled number already present. When setting the initial values, note that the only number we can commit to as determining the score is the sole B-labeled number, \(N\). After we have committed to a number determining the score, transitions must insert numbers to the left of the rightmost B-labeled number. The transitions differ depending on whether the inserted number is A-labeled or B-labeled, but we omit the details. Refer to the example implementation that examines all insertion positions in \(O(N^3)\) time. This DP can be accelerated by using prefix sums in the transitions, giving \(O(N^2)\) time overall.

Example implementation (C++) Examining all insertion positions in \(O(N^3)\) time (TLE)

Example implementation (C++) \(O(N^2)\) time