SRM 527

Div 2 250 - P8XMatrixTransformation
It is obvious that we can transform source matrix to destination matrix if and only if number of ones in the first matrix equals number of ones in the second matrix (We always can swap any two elements of source matrix using given operation).

public class P8XMatrixTransformation {
    public String solve(String[] original, String[] target) {
        int n = original.length;
        int m = original[0].length();
        int c = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (original[i].charAt(j) == '1') ++c;
                if (target[i].charAt(j) == '1') --c;
            }
        }
        if (c == 0) return "YES";
        return "NO";
    }
}

Div2 550, Div1 275 - P8XGraphBuilder
As we can see from statement we have to build tree. Any tree has (N - 1) edges where N - number of vertexes. Since each edge (u, v) increase by one degree of u and v then sum of all vertexes degree in tree equals 2(E - 1) and each degree is not greater than N - 1 and not less than 1. If we become any array of degree (call it d) which satisfied previous restrictions we can always build tree using this array.  How we can do it? Sort array in non decreasing order and then let pick up first vertex (its degree is one) and connect it with first not one degree vertex with decreasing them degrees. Note that array keep non decreasing order. Repeat this operation until array would be as (1, 1) and add last edge. We become tree because in process we can't build cycle since we always added edges from left to right by array. And last action consists in finding optimal solution. We can do it using dynamic programming (like knapsack algorithm).

import java.util.Arrays;
public class P8XGraphBuilder {
    public int solve(int[] scores) {
        int N = scores.length + 1;
        int W = 2 * (N - 1);
        int dp[][] = new int[N + 1][W + 1];
        for (int i = 0; i <= N; ++i) {
            Arrays.fill(dp[i], Integer.MIN_VALUE);
        }
        dp[0][0] = 0;
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j < N; ++j) {
                int c = scores[j - 1];
                for (int k = j; k <= W; ++k) {
                    dp[i][k] = Math.max(dp[i][k], dp[i - 1][k - j] + c); 
                }
            }
        }
        return dp[N][W];
    }
}

Div1 1050 - P8XCoinChange

public class P8XCoinChange {
    static final int MOD = 1000 * 1000 + 3;

    int[][] mul(int[][] a, int[][] b) {
        int n = a.length;
        int c[][] = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                long cum = 0;
                for (int k = 0; k < n; ++k) {
                    cum += (long)a[i][k] * b[k][j];
                }
                c[i][j] = (int)(cum % MOD);
            }
        }
        return c;
    }
    int[][] pow(int a[][], long n) {
        int r[][] = new int[a.length][a.length];
        for (int i = 0; i < a.length; ++i) {
            r[i][i] = 1;
        }
        for (; n != 0; n >>= 1) {
            if ((n & 1) == 1) {
                r = mul(r, a);
            }
            a = mul(a, a);
        }
        return r;
    }
    public int solve(long sum, long[] vals) {
        int n = vals.length;
        int a[][][] = new int[n][n][n];
        for (int i = 0; i < n; ++i) {
            a[0][i][0] = 1;
        }
        for (int i = 1; i < n; ++i) {
            a[i] = pow(a[i - 1], vals[i] / vals[i - 1]);
            for (int k = i; k < n; ++k) {
                a[i][k][i]++;
            }
        }
        int r[][] = new int[n][n];
        for (int i = 0; i < n; ++i) {
            r[i][i] = 1;
        }
        for (int i = n - 1; i >= 0; --i) {
            long val = vals[i]; 
            long pw = sum / val;
            sum %= val;
            r = mul(r, pow(a[i], pw));
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += r[n - 1][i];
            ans %= MOD;
        }
        return ans;
     }
}