a bit of topcoder: SRM 636 Div. 1

Problem Statement:
TopCoder SRM 636 Div. 1 500

Summary:
Given an array called board of dimension MxN ( \(M, N\leq 20\) ). Each cell board[i][j] contains either '#' or '.', indicating 'full' or 'empty' respectively. We are to choose r cells out of the empty cells. Between 2 cells, we define distance of board[i][j] and board[m][n] is \(\sqrt{(i-m)^2+(j-n)^2}\). For each board[i][j], an edge is drawn between that cell and another cell with the smallest distance. If there is a tie, draw the edge to the one with lower row index, and if there is still a tie, choose the one with lower column index. The resulting undirected graphs have a number of connected components. Find the expected number of connected components.

One of the most important observation that makes solving this problem possible: If two cells have double edges (each of them have edge pointing to one another), then they contribute to one connected component.

We need some background on probability though, especially on Expectation and Indicator Function:
1. X is the random variable representing the number of connected components in a graph. Equivalently, from our observation, that X is equal to the number of pairs of double edges.
2. \(E(X) = \sum {xP(X=x)} \)
3. \(I\) is indicator function, \(I(A) = 1\) if event A occurs, 0 if it does not. If we define a random variable \(X_A = I(A)\), then \(E(X_A) = P(A)\).
4. Let \(A_{(c,d)}\) be an event that there is a double edge between two cells c and d. Furthermore, we define \(X_{(c,d)} = I(A_{(c,d)}) \). We have \(X = \sum_{c,d \in \text{board cells}, c\neq d} X_{(c,d)} \).
5. Hence E(X) = E( \( \sum_{c,d \in \text{board cells}, c\neq d} X_{(c,d)} \) ), which is equal to the sum of all probabilities of each \(A_{(c,d)}\).

Here is the implementation:

/*
X = number of double edges 
E[X] = sum xP(X=x)
P(i-j has double edge)
Given P(X=1), can I get P(X=k) k>1? Seems terribly inefficient.
Let's use Indicator function instead
Let I(edge i-j) = 1 if i-j has double edge
if we sort all edges into one sequence
X(i) = I(i-th edge)

E[X] = E[X(i)]
     = sum {i=1 to |E|} E(X(i))
And E(X(i)) = P(ith-edge) since expectation of an indicator is its prability
Now the problem reduces to finding probability of each edges from happening.

Complexity: O(N^2) to perform check for each edge. total O(N^3)
*/


class ClosestRabbit{
public:
    vector<string> board;
    double ncr[403][403];
    int M, N, R;
    int emp;

    int dist(int ia, int ja, int ib, int jb){
        return (ia-ib)*(ia-ib) + (ja-jb)*(ja-jb);
    }
    
    int countAvailable(int ia, int ja, int ib, int jb){
        int ret = 0;
        int mindist = dist(ia, ja, ib, jb);
        for(int i=0;i<M;++i){
            for(int j=0;j<N;++j){
                if(i == ia && j == ja) continue;
                if(i == ib && j == jb) continue;
                if(board[i][j] == '#' || mindist > dist(i,j,ia,ja) || mindist > dist(i,j,ib,jb)){
                    continue;
                }
                if(mindist == dist(i,j,ia,ja)){
                    if(i < ib) continue;
                    if(i == ib && j < jb) continue;
                }
                if(mindist == dist(i,j,ib,jb)){
                    if(i < ia) continue;
                    if(i == ia && j < ja) continue;
                }
                ++ret;
            }
        }
        return ret;
    }
    
    double prob(int ia, int ja, int ib, int jb){
        if(board[ia][ja] == '#' || board[ib][jb] == '#') return 0;
        int avail = countAvailable(ia,ja,ib,jb);
        return ncr[avail][R-2];
    }
    
    double getExpected(vector<string> board, int r){
        this->board = board;
        M = board.size();
        N = board[0].size();
        R = r;
        emp = 0;
        for(int i=0;i<M;++i){
            for(int j=0;j<N;++j){
                if(board[i][j] == '.') ++emp;
            }
        }
        for(int i=0;i<=emp;++i){
            ncr[i][0] = 1;
            if(i>0) ncr[i-1][i] = 0;
        }
        for(int i=1;i<=emp;++i){
            for(int j=i;j>=1;--j){
                ncr[i][j] = ncr[i-1][j] + ncr[i-1][j-1];
            }
        }
        double ans = 0;
        for(int ia=0;ia<M;++ia){
            for(int ja=0;ja<N;++ja){
                for(int ib=0;ib<M;++ib){
                    for(int jb=0;jb<N;++jb){
                        if(ib == ia && jb == ja) continue;
                        ans += prob(ia, ja, ib, jb);
                    }
                }
            }
        }
        return ans/ncr[emp][r]/2.0;
    }
};