Let dp[i]dp[i] be the number of valid ways to arrange the tournament among ii players. There are i×(i1)2\frac{i\times (i-1)}{2} possible games among ii players. So the number of ways to select some games (possibly zero) from i×(i1)2\frac{i\times (i-1)}{2} games is 2i×(i1)22^{\frac{i\times (i-1)}{2}}. Let the number of invalid ways to select the games (where every player doesn’t participate in at least one game) be xx. So, dp[i]=2i×(i1)2xdp[i] = 2^{\frac{i\times (i-1)}{2}} - x. Now we have to calculate the value of xx.

If exactly jj players do not participate in any game and the remaining (ij)(i-j) players participate in at least one game, there are (ij)i\choose{j} ways to choose jj players from ii and dp[ij]dp[i-j] ways to arrange the games among (ij)(i-j) players. So, there are (ij)×dp[ij]{{i}\choose{j}} \times dp[i-j] ways where exactly jj players do not participate in any game. Now, x= j=1i(ij)×dp[ij]x =  \sum\limits_{j=1}^{i} {{i\choose j}\times dp[i-j]}.

Time complexity O(n2)O(n^2).

Statistics

80% Solution Ratio
NirjhorEarliest, Jun '22
NirjhorFastest, 0.0s
ash_98Lightest, 221 kB
NirjhorShortest, 962B
Toph uses cookies. By continuing you agree to our Cookie Policy.