SRM 527: Slooow

This was a very slow week, with no contests, I felt I was out of shape. Anyway, it seems I did sort of well.

Div1 450: P8XMatrixRecovery
You are given the rows of a binary matrix in correct order, some cells are ?, which means they can be 0 or 1. You are also given the columns, in the same format but this time not necessarily in the correct order. Basically, you can try any permutation of columns. It is guaranteed that there will be an answer, return the lexicographically-first matrix that follows the condition.

I noticed that the constraint on the dimensions was 30x30. It sort of led me to think that there was quite some freedom in the solution. When asked to build the lexicographically-first thing and the alphabet is reduced (there are only 0 or 1 as choices), it is possible to try cell by cell from top-left to bottom-right and try to find the lowest possible value in each position given the previous values found.

For example, in this case, imagine we knew of a function that took the rows and the columns and returned true if such matrix is possible. To build the lex-first matrix, just try each ? cell, and ask the question "Is it possible to have a matrix in which this position has 0 ? ". If the answer to that question is true, then the lex-first answer should have a 0 there, else it must have a 1 there. Make sure to use the newly-found values in subsequent iterations.

We just need to know how to answer that question. It is not so difficult. We have a set of columns and we want to assign a unique position from 0 to n-1 to each of the columns. Now, notice that some columns are compatible with some positions and some are not. We can imagine this as a bipartite graph between columns and positions. There is an edge connecting a column with a position if they are compatible. Then use bipartite matching to solve this. Which in turn shall use Max flow. If a perfect matching exists, there is a valid matrix This logic solves the problem, and you can verify that it needs O(n^5) time complexity in total. That is where the 30x30 constraint comes into place...

struct P8XMatrixRecovery 
{ 
//The network class is just a interface to solve max flow. 
 
    bool doMatch(const vector<string> & rows, const vector<string> & columns) 
    { 
        int r = rows.size(); 
        int c = columns.size(); 
         
        network G; 
        for (int i = 0; i < 2*c; i++) { 
            G.addVertex(); 
        } 
        G.sink = G.addVertex(); 
        G.source = G.addVertex(); 
        for (int i=0; i<c; i++) { 
            G.addEdge(G.source, i, 1); 
            G.addEdge(i+c, G.sink, 1); 
        } 
         
        // Use bipartite matching between columns and positions. 
        for (int i=0; i<c; i++) { //O(n^3) 
            for (int j=0; j<c; j++) { //O(n^4) 
                // O(n^5) 
                bool can = true; 
                for (int k=0; (k<r) && can; k++) { //O(n^5) 
                    char a = rows[k][j]; 
                    char b = columns[i][k]; 
                    if ( a != '?' ) { 
                        if (b != '?') { 
                            can &= (a == b); 
                        } 
                    } 
                } 
                if (can ) { 
                    G.addEdge(i, j + c, 1); 
                }             
            } 
        } 
        int f = G.maxFlow(); 
        return (f == c); //O(n^3) 
    } 
    
    vector <string> solve(vector <string> rows, vector <string> columns) 
    { 
        int r = rows.size(); 
        int c = columns.size(); 
        vector<string> res = rows; 
         
        // For each unknown cell. 
        for (int i=0; i<r; i++) { 
            for (int j=0; j<c; j++) { //O(n^2) 
                if (rows[i][j] == '?') { 
                    //Is it possible to place 0 here? 
                    res[i][j] = '0'; 
                    if (! doMatch(res, columns)) { 
                        // If not, place a 1. 
                        res[i][j] = '1'; 
                    } 
                } 
            } 
        } 
         
        return res; 
    } 
}; 

Div1 275: P8XGraphBuilder
So, the problem scores would suggest that this problem was about as hard as the medium. I found it to be harder :). Well, you are given an array of N-1 elements: scores . You have to build a connected graph with N nodes and N-1 edges such that the sum (scores[degree of (vertex i) - 1]) for all i is as large as possible.

I was headed to the right answer from the beginning: A N vertices graph with N-1 edges that is connected is just a fancy way to say "Tree". Trees are quite compatible with dynamic programming, because you can consider each node a root of its own subgraph. In an undirected tree, You can also consider any node of the tree to be a root.

At first I had some issues giving a body to the solution. I eventually came to this: Imagine the state F(current_degree, available_children). You want to return the maximum score a single 'root' will have given its current_degree and the number of children available to add as children or grand-children to this root.

If available_children is 0, then we cannot do anything, the score is score[Current_degree - 1].

If available_children is not 0, then we are forced to add a new child to the 'root'. This is the recursive part. Let us name k the number of vertices that will be children for the new node. Then the total result will be the sum of F(current_degree+1, available_children - 1 - k) + F(1, k). Why? Ok, the degree of the "root" will increase by 1. The number of available children for the remaining nodes, decreases by 1+k. But the new child will also have a score of its own, its degree is initially 1, because of its connection to the root, and it has k nodes available for him.

We can iterate all the values of k, and select the one that maximizes the result.

struct P8XGraphBuilder 
{ 
    int N; 
    vector<int> scores; 
    int mem[100][100]; 
    int rec(int currentdeg, int avchildren) 
    { 
        int & res = mem[currentdeg][avchildren]; 
        if (res == -1)  { 
            res = 0; 
            if (avchildren == 0) { 
                if( currentdeg != 0) { 
                     res = scores[currentdeg-1];                     
                } 
            } else { 
                //how many grandchildren for the next child? 
                for (int k=0; k<avchildren; k++) { 
                    res = std::max(res, rec(currentdeg+1, avchildren-1-k) 
                                        + rec(1, k) ); 
                } 
            } 
        } 
        return res; 
         
         
         
    } 
 
    int solve(vector <int> scores) 
    { 
        this->scores = scores; 
        int N = scores.size() + 1; 
        memset(mem,-1,sizeof(mem)); 
        return rec(0, N-1); 
    } 
}; 

Div1 1050
I think this problem is all about Lucas' theorem. Mostly because of the low modulo value and some other aspects. But I have no further idea.

---
It seems I did well, the only risks would be a silly typo in some code. My performance was slower than many other coders that solved both problems though.