Problem: elimination (2020 round2)

The Facebook Whacker Cup is a series of ping-pong tournaments to find the best paddlers on the social network. A tournament consists of \(N\) ping-pong players and \(N - 1\) elimination matches among them. The players are numbered from \(1\) to \(N\) in increasing order of skill.

In each match, two players will be randomly selected from the set of players still in contention (if there are \(x\) players, then all \(x(x-1)/2\) unordered pairs of them are equally likely to be selected). Those players will then play against each other, with the more skilled (higher-numbered) of the two winning with a probability of \(P\). The loser will then be eliminated from the tournament, and will not be involved in any future matches. After \(N - 1\) such matches, there will be exactly one player remaining who will be declared the Whacker Cup champion!

For each player, determine the expected number of matches which will occur while they're still in contention (before they're either eliminated or the tournament concludes). This should include matches which they either directly compete in (including the one in which they lose and get eliminated), or which simply occur before they've been eliminated. Each of your answers must have at most \(10^{-6}\) absolute or relative error to be considered correct.

# Input

Input begins with an integer \(T\), the number of tournaments. For each tournament, there is one line containing the space-separated integer \(N\) and real number \(P\) (given with at most 3 digits after the decimal point).

# Output

For the \(i\)th tournament, output a line containing *"Case #i:"* followed by \(N\) lines, the \(j\)th of which contains a single real number, the expected number of matches which will occur while player \(j\) is still in contention.

# Constraints

\(1 \le T \le 95\)
\(2 \le N \le 8000\)
\(0.5 \le P \le 1.0\)

The sum of \(N\) across all \(T\) tournaments is at most 50,000.

# Explanation of Sample

In the first tournament, player 2 is guaranteed to defeat player 1. Regardless of the result, however, both players will be present for the tournament's single match.

In the second tournament, player 3 is guaranteed to defeat players 1 and 2, while player 2 is guaranteed to defeat player 1. There are three possible, equally-likely sequences of matches (with `A>B` representing a match in which player \(A\) beats player \(B\)):

- `2>1` followed by `3>2`
- `3>1` followed by `3>2`
- `3>2` followed by `3>1`
  
All players are guaranteed to be in contention during at least the first match. Player 1 has a \(\frac{1}{3}\) chance to also be present for the second match (if the last sequence occurs), player 2's chance is \(\frac{2}{3}\) (if either of the first two sequences occurs), and player 3 is guaranteed to be present for both matches.

In the third tournament, the match results are again deterministic. The first match will feature one of 6 possible player pairs, the second match will feature one of 3 possible pairs of remaining players, and the third match will be between the final pair of players. Overall, there are \(6 * 3 * 1 = 18\) possible scenarios. Across these scenarios, the total counts of hypothetical matches before elimination are 30 for player 1, 35 for player 2, 43 for player 3, and 54 for player 4. Dividing each by 18 yields the expected answer.

In the fourth tournament, matches could go either way with equal probability (skill levels don't matter). There are 6 possible, equally-likely first match outcomes (`1>2`, `2>1`, `1>3`, `3>1`, `2>3`, `3>2`), after which only the eliminated player won't be present for the second match. Therefore, each player has a \(\frac{2}{6}\) chance of being present for one match, and a \(\frac{4}{6}\) chance of being present for both.


Sample input:
6
2 1.0
3 1.0
4 1.0
3 0.5
5 0.678
9 0.87


Sample output:
Case #1:
1.00000000
1.00000000
Case #2:
1.33333333
1.66666667
2.00000000
Case #3:
1.66666667
1.94444444
2.38888889
3.00000000
Case #4:
1.66666667
1.66666667
1.66666667
Case #5:
2.47452857
2.61417298
2.77465280
2.96047982
3.17616583
Case #6:
3.64469088
3.83725603
4.05825232
4.31581280
4.62193375
4.99526004
5.46668555
6.09114388
6.96896476


Solution: This problem can be solved with dynamic programming. Let \(E_{b, w}\) be the expected number of future matches which a player will be present for given that they're currently in the tournament together with \(b\) better and \(w\) worse players than them. The \(i\)th output (the expected number of matches for which player \(i\) will be present) will then be \(E_{N - i, i - 1}\).

Let's define \(F_{b, w}\) similarly to \(E_{b, w}\), except with the additional constraint that the winner of the next match is guaranteed to be the higher-skilled of the two competitors. We'll define \(G_{b, w}\) in much the same way, except with the next match's winner being the lower-skilled competitor. We then have \(E_{b, w} = F_{b, w} * P + G_{b, w} * (1 - P)\).

We'll next consider how to compute \(F_{b, w}\), noting that \(G_{b, w}\) may then be computed very similarly. \(F_{b, w}\) is equal to \(1\) (as the player will certainly be present for the next match) plus the expected number of matches the player will be present after the next match (if they're not eliminated in it). If they're not about to be eliminated, then either a better or a worse player must be eliminated instead. Let \(Q(x) = \frac{x(x - 1)}{2}\) (the number of unordered pairs out of \(x\) players). If \(b > 0\), then there's a \(\frac{Q(b)}{Q(b + w + 1)}\) chance that a better player will be eliminated, meaning that we should add \(E_{b-1, w} * \frac{Q(b)}{Q(b + w + 1)}\) onto \(F_{b, w}\). Similarly, if \(w > 0\), we should add \(E_{b, w-1} * \frac{w(b+1) + Q(w)}{Q(b + w + 1)}\) onto \(F_{b, w}\).

Over the course of the algorithm, we'll compute \(E_{b, w}\) for \(O(N^2)\) pairs of \(b\) and \(w\). Computing each such value takes constant time, resulting in a time complexity of \(O(N^2)\).



Code: // Elimination
// Solution by Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x < 0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x * x); }
string plural(string s) { return(Sz(s) && s[Sz(s) - 1] == 'x' ? s + "en" : s + "s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#define GETCHAR getchar_unlocked

#define LIM 8001

// dyn[b][w] = expected number of remaining rounds
//             when there are b better and w worse players than you
LD dyn[LIM][LIM];

int NumPairs(int c)
{
  return(c * (c - 1) / 2);
}

// inv indicates that b/w have been swapped to capture worse players winning
LD Comp(int b, int w, bool inv)
{
  LD p = (LD)1 / NumPairs(b + w + 1), d = 0;
  // elimination of better player than you
  if (b > 0)
    d += NumPairs(b) * p * (inv ? dyn[w][b - 1] : dyn[b - 1][w]);
  // elimination of worse player than you
  if (w > 0)
    d += (w * (b + 1) + NumPairs(w)) * p * (inv ? dyn[w - 1][b] : dyn[b][w - 1]);
  return(d);
}

void ProcessCase()
{
  int N, i, b, w;
  LD P;
  // input
  scanf("%d%Lf", &N, &P);
  // DP
  Fill(dyn, 0);
  Fox(b, N)
  {
    Fox(w, N - b)
    {
      if (b + w)
      {
        dyn[b][w] = 1 +
          Comp(b, w, false) * P + // better players winning
          Comp(w, b, true) * (1 - P); // worse players winning
      }
    }
  }
  // output
  Fox(i, N)
    printf("%.8Lf\n", dyn[N - i - 1][i]);
}

int main()
{
  int T, t;
  scanf("%d\n", &T);
  Fox1(t, T)
  {
    printf("Case #%d:\n", t);
    ProcessCase();
  }
  return(0);
}