P4190 [CTSC2010] Three-Nation Go Relay Tournament

The annual “Nongshim Cup” three-nation Go relay tournament is the highest-level Go competition in the world and the most exciting contest among China, Japan, and Korea. This problem is based on the rules of that event. The three-nation Go relay tournament is a match among national teams of three countries. The rules are briefly as follows: 1. Let the three countries be $A$, $B$, and $C$. Each country has $n$ players (in the real event above, $n = 5$), named $A_1, A_2, \ldots, A_n$, $B_1, B_2, \ldots, B_n$, and $C_1, C_2, \ldots, C_n$. 2. Every game has a winner and a loser. The loser of a game is eliminated. 3. The first player to appear for each team is fixed to be that team’s $n$-th player, i.e., $A_n$, $B_n$, and $C_n$. 4. One team is drawn uniformly at random. That team has a bye in round 1, and the $n$-th players of the other two teams play the first game. 5. The winner of the first game (the “winner” here always means the player who wins that game) plays the $n$-th player of the team that had the bye in the second game. For example, if $C_n$ defeats $A_n$ in the first game, then the second game is $C_n$ vs. $B_n$. 6. From the third game onward, the team that did not participate in the previous game selects one not-yet-eliminated player to play against the previous game’s winner. 7. This process continues until all players of some team have been eliminated. 8. When only two teams remain, after each game, the losing side chooses one not-yet-eliminated player to play the next game against the winner. 9. When all players of either of the two remaining teams are eliminated, the match ends, and the remaining team wins the Nongshim Cup. A new edition of the tournament is about to begin. As the leader of Team $A$, you have computed the win probabilities among all $3n$ players — that is, for any two players $Q$ and $R$ from different teams, we know that the probability that $Q$ defeats $R$ is $p$ ($0 \leq p \leq 1$), and the probability that $R$ defeats $Q$ is $1 - p$. Since your country is overwhelmingly strong, assume the other two teams will both target you. Every decision by Teams $B$ and $C$ — i.e., the order in which they send players — aims to minimize the probability that Team $A$ wins the title, while Team $A$’s decisions aim to maximize that probability. Your task is to compute, under this highly unfavorable scenario and assuming all three sides play optimally, the expected probability $E_A$ that Team $A$ wins the championship. About the expectation: suppose the current game is between players $Q$ and $R$, and $Q$ defeats $R$ with probability $p$. Then Team $A$’s winning expectation at this moment is $E_A = p \times E_1 + (1 - p) \times E_2$, where $E_1$ is the expectation that Team $A$ wins the title after $Q$ defeats $R$, and $E_2$ is the expectation after $R$ defeats $Q$. $E_1$ and $E_2$ are computed recursively using the same formula. Team $A$’s decisions will maximize this expectation, while Teams $B$ and $C$ will minimize it. If all players of Teams $B$ and $C$ are eliminated, the expectation is $1$; if all players of Team $A$ are eliminated, the expectation is $0$. For example, when each team has $3$ players, the head-to-head win probabilities are given by the following three $3\times 3$ matrices. In each matrix, every value $p$ is the row player’s probability of defeating the column player, and the column player’s probability of defeating the row player is $1 - p$.  The third players of the three teams are of equal strength. After the first two games, the probability that the current winner comes from any of the three teams is the same. Suppose the winner of the second game is $B_3$, and in the third game it is Team $A$’s turn to send a player. Team $A$ can choose between $A_1$ and $A_2$. If we send $A_2$, although the third game is guaranteed to defeat $B_3$ (win probability $100 \%$), Team $C$ will send $C_2$ in the fourth game, against whom $A_2$ surely loses (win probability $0$). In the fifth game, Team $B$ will send $B_1$, and in the sixth game only $A_1$ can be sent. Since $B_2$, who surely defeats $A_1$, has not yet appeared, $A_1$ will be eliminated sooner or later, and Team $A$’s winning probability is $0$. If we send $A_1$, although the win probability against $B_3$ in this game is only $50 \%$, the probability of winning the championship is $6.25 \%$. Therefore, in the third game we should send $A_1$. Considering the six possible pairs of players in the third game, the final expected championship probability is: $$ \dfrac{(6.25\%+3.125\%+18.75\%+25\%+60.9375\%+50\%)}{6} = 27.34375\%.$$

The input file is go.in. The first line contains an integer $n$, the number of players on each team. Lines $2$ to $n + 1$ each contain $n$ real numbers, forming an $n \times n$ matrix that gives Team $A$’s win probabilities against Team $B$. In particular, on line $i + 1$, the $j$-th number is the probability that player $A_i$ defeats player $B_j$. Line $n + 2$ is a blank line. Lines $n + 3$ to $2n + 2$ each contain $n$ real numbers, forming an $n \times n$ matrix that gives Team $A$’s win probabilities against Team $C$. In particular, on line $i + n + 2$, the $j$-th number is the probability that player $A_i$ defeats player $C_j$. Line $2n + 3$ is a blank line. Lines $2n + 4$ to $3n + 3$ each contain $n$ real numbers, forming an $n \times n$ matrix that gives Team $B$’s win probabilities against Team $C$. In particular, on line $i + 2n + 3$, the $j$-th number is the probability that player $B_i$ defeats player $C_j$.

The output file go.out contains a single real number with $6$ decimal places, the probability that Team $A$ wins the championship.

- For $30\%$ of the testdata, $n \leq 4$. - For $40\%$ of the testdata, $n \leq 5$. - For $100\%$ of the testdata, $n \leq 7$. - For $10\%$ of the testdata, in each of the three win-probability matrices, every matrix has constant entries (all elements in a given matrix are the same), but different matrices may have different values. Translated by ChatGPT 5