SRM 531

Div2 - 250 UnsortedSequence

import java.util.Arrays;
public class UnsortedSequence {
    public int[] getUnsorted(int[] s) {
        int n = s.length;
        if (n == 1) return new int[0];
        Arrays.sort(s);
        int i = n - 2;
        while (i >= 0 && s[i] == s[i + 1]) --i;
        if (i < 0) return new int[0];
        int t = s[i];
        s[i] = s[i + 1];
        s[i + 1] = t;
        return s;
    }
}

Div2 - 600, Div1 - 300 NoRepeatPlaylist

import java.util.*;
public class NoRepeatPlaylist {
    int N, M, P;
    static final int MOD = 1000 * 1000 * 1000 + 7;

    long dp[][] = new long[101][101];

    long rec(int k, int used) {
        if (k == P) {
            return used == N ? 1 : 0;
        }
        if (dp[k][used] != -1) return dp[k][used];
        long res = 0;
        if (used < N) res = rec(k + 1, used + 1);
        int busy = Math.min(k, M);
        if (used > busy) {
            res += rec(k + 1, used) * (used - busy);
            res %= MOD;
        }
        return dp[k][used] = res;
    }


    public int numPlaylists(int N, int M, int P) {
        this.M = M;
        this.P = P;
        this.N = N;
        for (int i = 0; i <= 100; ++i) {
            Arrays.fill(dp[i], -1);
        }
        long ans = rec(0, 0);
        for (int i = 2; i <= N; ++i) {
            ans = (ans * i) % MOD;
        }
        return (int)ans;
    }
}

Div2 - 950 #

import java.util.*;
public class KingdomReorganization {
    void dfs(int u, char[][] a, boolean[] use) {
        use[u] = true;
        int n = a.length;
        for (int v = 0; v < n; ++v) {
            if (use[v]) continue;
            if (a[u][v] != '1') continue;
            dfs(v, a, use);
        }
    }

    int countOfComponent(char[][] a) {
        int n = a.length;
        int res = 0;
        boolean use[] = new boolean[n];
        for (int i = 0; i < n; ++i) {
            if (use[i]) continue;
            dfs(i, a, use);
            ++res;
        }
        return res;
    }

    class Edge implements Comparable<Edge> {
        int u, v, cost;
        Edge(int u, int v, int cost) {
            this.u = u;
            this.v = v;
            this.cost = cost;
        }
        public int compareTo(Edge e) {
            return cost - e.cost;
        }
    }

    int get(char ch) {
        if (Character.isUpperCase(ch)) return ch - 'A';
        return ch - 'a' + 26;
    }


    public int getCost(String[] kingdom, String[] build, String[] destroy) {
        List<Edge> buildEdges = new ArrayList<Edge>();
        List<Edge> destroyEdges = new ArrayList<Edge>();
        int n = kingdom.length;
        char a[][] = new char[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                a[i][j] = kingdom[i].charAt(j);
                if (i >= j) continue;
                if (a[i][j] == '1') {
                    destroyEdges.add(new Edge(i, j, get(destroy[i].charAt(j))));
                } else {
                    buildEdges.add(new Edge(i, j, get(build[i].charAt(j))));
                }
            }
        }
        Collections.sort(buildEdges);
        Collections.sort(destroyEdges);
        int cnt = countOfComponent(a);
        int res = 0;
        // destroy
        for (int i = 0; i < destroyEdges.size(); ++i) {
            int u = destroyEdges.get(i).u;
            int v = destroyEdges.get(i).v;
            int cost = destroyEdges.get(i).cost;
            a[u][v] = a[v][u] = '0';
            int newCnt = countOfComponent(a);
            if (newCnt == cnt) {
                res += cost;
            } else {
                a[u][v] = a[v][u] = '1';
            }
        }
        // build 
        for (int i = 0; i < buildEdges.size(); ++i) {
            int u = buildEdges.get(i).u;
            int v = buildEdges.get(i).v;
            int cost = buildEdges.get(i).cost;
            a[u][v] = a[v][u] = '1';
            int newCnt = countOfComponent(a);
            if (newCnt == cnt) {
                a[u][v] = a[v][u] = '0';
            } else {
                res += cost;
                cnt--;
            }
        }
        return res;
    }
}

Div1 - 500 #

Div1 - 1000 #