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 #