Football corruption P84060


Statement
 

pdf   zip

html

An infamous football club (let us call it X) wants to buy yet another competition. There are n teams, where n = 2m for some m. As usual, the tournament scheme is a complete binary tree, so X will have to win m matches to be the champion. The president of X knows, for every pair of teams i and j, the probability pij that i eliminates j. So he will bribe the football federation, and arrange the play offs so as to maximize the probability that X wins the competition. Can you compute that probability?

Input

Input consists of several cases, each one with n, followed by n lines with n probabilities each, where the j-th number of the i-th line is pij. Assume 1 ≤ m ≤ 3, that pji = 1 − pij for every i ≠ j, and that the diagonal of the matrix has only -1. X is the first team.

Output

For every case, print the probability with four digits after the decimal point. The input cases have no precission issues.

Hint

The expected solution is a “reasonable” backtracking. For instance, 2000 tests with n=8 should be solved in at most one second.

Public test cases

  • Input

    2
-1 0.6
0.4 -1

4
 -1   1 0.5   0
  0  -1 0.7 0.8
0.5 0.3  -1 0.1
  1 0.2 0.9  -1

8
 -1 0.1 0.2 0.3 0.4 0.5 0.6 0.7
0.9  -1 0.9 0.8 0.7 0.6 0.5 0.4
0.8 0.1  -1 0.1 0.2 0.3 0.4 0.5
0.7 0.2 0.9  -1 0.5 0.6 0.7 0.8
0.6 0.3 0.8 0.5  -1 0.2 0.4 0.6
0.5 0.4 0.7 0.4 0.8  -1 0.8 0.4
0.4 0.5 0.6 0.3 0.6 0.2  -1 0.3
0.3 0.6 0.5 0.2 0.4 0.6 0.7  -1

    Output

    0.6000
0.4000
0.1100
    • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++