SRM 534

Div2 - 250 EllysDirectoryListing

public class EllysDirectoryListing {
    public String[] getFiles(String[] files) {
        int n = files.length;
        if (check(files)) return files;
        int p = getPos(files);
        swap(files, p, n - 1);
        if (check(files)) return files;
        p = getPos(files);
        swap(files, p, n - 2);
        return files;
     }

    boolean check(String files[]) {
        int n = files.length;
        if (files[n - 1].equals(".") && files[n - 2].equals("..")) return true;
        if (files[n - 2].equals(".") && files[n - 1].equals("..")) return true;
        return false;
    }
    int getPos(String files[]) {
        for (int i = 0; i < files.length; ++i) {
            if (files[i].equals(".")) return i;
            if (files[i].equals("..")) return i;
        }
        return -1;
    }
    void swap(String f[], int i, int j) {
        String tmp = f[i];
        f[i] = f[j];
        f[j] = tmp;
    }

}

Div2 - 500, Div1 - 250 EllysCheckers

public class EllysCheckers {
    public String getWinner(String board) {        
        int use = 0;
        N = board.length();
        for (int i = 0; i + 1 < N; ++i) {
            if (board.charAt(i) != '.') {
                use |= 1 << i;
            }
        }
        dp = new Integer[1 << N];
        return rec(use) == 1 ? "YES" : "NO";
     }
    
    Integer dp[];
    int N;

    int rec(int use) {
        if (testBit(use, N - 1)) use ^= 1 << N - 1;
        if (dp[use] != null) return dp[use];
        for (int i = 0; i < N; ++i) {
            if (i + 1 < N && testBit(use, i) && !testBit(use, i + 1)) {
                int nuse = use ^ (1 << i) ^ (1 << i + 1);
                if (rec(nuse) == 0) return dp[use] = 1;
            }
            if (i + 3 < N && testBit(use, i) && testBit(use, i + 1)
            && testBit(use, i + 2) && !testBit(use, i + 3)) {
                int nuse = use ^ (1 << i) ^ (1 << i + 3);
                if (rec(nuse) == 0) return dp[use] = 1;
            }
        }
        return dp[use] = 0;
    }

    boolean testBit(int x, int p) {
        return ((x >> p) & 1) == 1;
    }
}

Div2 - 1000 EllysFiveFriends

public class EllysFiveFriends {

    static final long MOD = 1000 * 1000 * 1000 + 7;

    boolean check(int a[]) {
        for (int i = 0; i < 5; ++i) {
            if (a[i] > 0) return false;
        }
        return true;
    }

    long getHash(int a[]) {
        long r = 0;
        for (int i = 0; i < 5; ++i) {
            r = r * 10007 + a[i];
        }
        return r;
    }

    static final int MAX = 1 << 22;
    static final int MASK = MAX - 1;
    static final int MAXH = 1 << 21;
    int NH;
    long Hkey[];
    int Hval[];
    int Hnext[];
    int h[];

    int get(long key) {
        int pos = (int)(key&MASK);
        for (int cur = h[pos]; cur != 0; cur = Hnext[cur]) {
            if (Hkey[cur] == key)  return Hval[cur];
        }
        return -1;
    }
    int rec(int a[]) {
        if (check(a)) return 1;
        long key = getHash(a);
        int t = get(key);
        if (t != -1) return t;
        int pos = (int)(key&MASK);
        long res = 0;
        for (int i = 0; i < 5; ++i) {
            int j = i + 1;
            if (j == 5) j = 0;
            if (a[i] <= 0 || a[j] <= 0) continue;
            int x = a[i], y = a[j];
            a[i] >>= 1;
            a[j] >>= 1;
            res += rec(a);
            a[i] = x;
            a[j] = y;
            if ((a[i] & 1) == 1 && (a[j] & 1) == 1) {
                --a[i];
                --a[j];
                res += rec(a);
                ++a[i];
                ++a[j];
            }
        }
        int r = (int)(res % MOD);
        Hkey[NH] = key;
        Hval[NH] = r;
        Hnext[NH] = h[pos];
        h[pos] = NH++;
        return r;
    }
    

    public int getZero(int[] numbers) {        
        h = new int[MAX];
        Hkey = new long[MAXH];
        Hval = new int[MAXH];
        Hnext = new int[MAXH];
        NH = 1;
        return rec(numbers);
     }
}

Div1 - 500 EllysNumbers

import java.util.*;

public class EllysNumbers {
    List<Integer> uses;
    int N;

    int[] collect(String[] s) {
        String str = "";
        for (String cur : s) {
            str += cur;
        }
        String ss[] = str.split(" ");
        int r[] = new int[ss.length];
        for (int i = 0; i < ss.length; ++i) {
            r[i] = Integer.valueOf(ss[i]);
        }
        return r;
    }

    public long getSubsets(long n, String[] special) {        
        Set<Integer> divisors = new TreeSet<Integer>();
        int vals[] = collect(special);
        for (int val : vals) {
            add(divisors, val);
        }
        List<Integer> d1 = new ArrayList<Integer>();
        List<Integer> d2 = new ArrayList<Integer>();
        long x = n;
        for (Integer divisor : divisors) {
            int c = 0;
            while (x % divisor == 0) {
                ++c;
                x /= divisor;
            }
            if (c == 0) continue;
            d1.add(divisor);
            d2.add(c);
        }

        if (x > 1) return 0;
        N = d1.size();
        uses = new ArrayList<Integer>();
        for (int val : vals) {
            int cur = val;
            boolean ok = true;
            int use = 0;
            for (int i = 0; ok && i < d1.size(); ++i) {
                int c = 0;
                while (cur % d1.get(i) == 0) {
                    cur /= d1.get(i);
                    ++c;
                }
                if (c == 0) continue;
                if (c == d2.get(i)) {
                    use |= 1 << i;
                    continue;
                }
                ok = false;
            }
            if (cur != 1 || !ok) continue;
            uses.add(use);
        }
        return calc();
     }
    
    long calc() {
        long dp[][] = new long[2][1 << N];
        int prev = 0, next = 1;
        dp[prev][(1 << N) - 1] = 1;
        for (int k = uses.size() - 1; k >= 0; --k) {
            int nuse = uses.get(k);
            for (int use = 0; use < 1 << N; ++use) {
                dp[next][use] = dp[prev][use];
                if ((use + nuse) == (use ^ nuse))
                    dp[next][use] += dp[prev][use ^ nuse];
            }
            int tmp = prev;
            prev = next;
            next = tmp;
        }
        return dp[prev][0];
    }

    void add(Set<Integer> d, int val) {
        for (int i = 2; i * i <= val; ++i) {
            int c = 0;
            while (val % i == 0) {
                val /= i;
                ++c;
            }
            if (c > 0) d.add(i);
        }
        if (val != 1) d.add(val);
    }
}

Div1 - 1000 #

SRM 533

Div2 - 250 PikachuEasy

public class PikachuEasy {
   public String check(String word) {
        String w[] = {"pi", "ka", "chu"};
        while (true) {
            boolean was = false;
            for (String cur : w) {
                if (word.startsWith(cur)) {
                    word = word.substring(cur.length());
                    was = true;
                }
            }
            if (!was) break;
        }
        if (word.length() == 0) return "YES";
        return "NO";
   }
}

Div2 - 500, Div1 - 250 CasketOfStarEasy

public class CasketOfStarEasy {
    int w[];
    Integer dp[][] = new Integer[100][100];
    int rec(int lo, int hi) {
        if (lo + 1 == hi) return 0;
        if (dp[lo][hi] != null) return dp[lo][hi];
        int tmp = w[lo] * w[hi];
        int res = 0;
        for (int k = lo + 1; k < hi; ++k) {
            res = Math.max(res, rec(lo, k) + rec(k, hi) + tmp);
        }
        return dp[lo][hi] = res;
    }
    public int maxEnergy(int[] weight) {
        this.w = weight;
        return rec(0, weight.length - 1);
    }
}

Div2 - 1000 MagicalGirl

public class MagicalGirl {
    int[] day, win, gain;
    int M;
    Double dp[][] = new Double[51][100 * 1000 + 1];
    
    double rec(int k, int m) {
        if (dp[k][m] != null) return dp[k][m];
        int curDay = day[k];
        if (m == 0) return curDay;
        int nextDay = k + 1 < day.length ? day[k + 1] : 10000000;
        int d = nextDay - curDay;
        double r1, r2;
        if (m >= d) r1 = rec(k + 1, m - d);
         else r1 = curDay + m;
        int g = Math.min(m + gain[k], M);
        double p = win[k] / 100.0;
        if (g >= d) r2 = rec(k + 1, g - d) * p + curDay * (1.0 - p);
        else r2 = (curDay + g) * p + curDay * (1.0 - p);
        return dp[k][m] = Math.max(r1, r2);
    }

    public double maxExpectation(int M, int[] day, int[] win, int[] gain) {
        int n = day.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (day[i] > day[j]) {
                    int tmp;
                    tmp = day[i]; day[i] = day[j]; day[j] = tmp;
                    tmp = win[i]; win[i] = win[j]; win[j] = tmp;
                    tmp = gain[i]; gain[i] = gain[j]; gain[j] = tmp;
                }
            }
        }
        this.day = day;
        this.win = win;
        this.gain = gain;
        this.M = M;
        if (M < day[0]) return M;
        return rec(0, M - day[0]);
    }
}

Div1 - 500 #

Div1 - 1000 #

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 #