Football corruption P84060


Statement
 

pdf   zip

thehtml

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 ij, 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++