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 526

Div2 250 - CheatingQuiz

import java.util.TreeSet;
import java.util.Set;
public class CheatingQuiz {
    public int[] howMany(String answers) {
        int r[] = new int[answers.length()];
        for (int i = 0; i < answers.length(); ++i) {
            Set<Character> set = new TreeSet<Character>();
            for (int j = i; j < answers.length(); ++j) {
                set.add(answers.charAt(j));
            }
            r[i] = set.size();
        }
        return r;
    }
}

Div2 500, Div1 250 - DucksAlignment

int Abs(int x) {
 return x > 0 ? x : -x;
}
int dist(int i1, int j1, int i2, int j2) {
 return Abs(i1 - i2) + Abs(j1 - j2);
}
class DucksAlignment {
public:
 int minimumTime( vector <string> a) {
  int n = sz(a);
  int m = sz(a[0]);
  int c = 0;
  vector<pii> ij, ji;
  for (int i = 0; i < n; ++i)
   for (int j = 0; j < m; ++j) {
    if (a[i][j] != '.') {
     ++c;
     ij.pb(mp(i, j));
     ji.pb(mp(j, i));
    }
   }
  sort(all(ij));
  sort(all(ji));
  int res = 1 << 30;
  // horizontal
  for (int i = 0; i < n; ++i) {
   for (int j = 0; j + c - 1 < m; ++j) {
    int cur = 0;
    for (int k = 0; k < c; ++k) {
     cur += dist(ji[k].second, ji[k].first, i, j + k);
    }
    res = min(res, cur);
   }
  }
  // vertical
  for (int j = 0; j < m; ++j) {
   for (int i = 0; i + c - 1 < n; ++i) {
    int cur = 0;
    for (int k = 0; k < c; ++k) {
     cur += dist(ij[k].first, ij[k].second, i + k, j);
    }
    res = min(res, cur);
   }
  }
  return res;
 }
};

Div2 1000 - SumOfLuckiness

public class SumOfLuckiness {
    int d[];
    Integer dp[][][];
    int rec(int k, int dif, int was) {
        if (k == d.length) return Math.abs(dif);
        if (dp[k][dif + 200][was] != null) 
            return dp[k][dif + 200][was];
        int hi = was == 1 ? 9 : d[k];
        int res = 0;
        
        for (int i = 0; i <= hi; ++i) {
            int nwas = was;
            int ndif = dif;
            if (i == 4) ++ndif;
            if (i == 7) --ndif;
            if (i < d[k]) nwas = 1;
            res += rec(k + 1, ndif, nwas);
        }
        return dp[k][dif + 200][was] = res;    
    }

    int get(int x) {
        if (x == 0) return 0;
        String s = String.valueOf(x);
        d = new int[s.length()];
        for (int i = 0; i < s.length(); ++i) {
            d[i] = s.charAt(i) - '0';
        }
        dp = new Integer[d.length + 1][400][2];
        return rec(0, 0, 0);
    }
    
    public long theSum(int A, int B) {
        return get(B) - get(A - 1);
    }
}

Div1 500 - PrimeCompositeGame

const int MAX = 500000;
bool P[MAX + 10];
using namespace std;
int K;
const int INF = 1 << 30;
pii A[MAX + 1];

struct Minimizator {
    vi q;
    int n;
    Minimizator(int n) {        
        while (n & (n - 1)) ++n;
        q.assign(n * 2, INF);
        this->n = n;
    }
    void mod(int p, int val) {        
        for (p += n; p; p >>= 1) {
            q[p] = min(q[p], val);
        }        
    }
    int getMin(int lo, int hi) {
        int r = INF;
        for (lo += n, hi += n; lo <= hi; ++lo >>= 1, --hi >>= 1) {
            if ((lo & 1) == 1) r = min(r, q[lo]);
            if ((hi & 1) == 0) r = min(r, q[hi]);
        }
        return r;
    }
};

struct Maximizator {
    vi q;
    int n;
    Maximizator(int n) {        
        while (n & (n - 1)) ++n;
        q.assign(n * 2, -INF);
        this->n = n;
    }
    void modMax(int p, int val) {        
        for (p += n; p; p >>= 1) {
            q[p] = max(q[p], val);
        }        
    }
    int getMax(int lo, int hi) {
        int r = -INF;
        for (lo += n, hi += n; lo <= hi; ++lo >>= 1, --hi >>= 1) {
            if ((lo & 1) == 1) r = max(r, q[lo]);
            if ((hi & 1) == 0) r = max(r, q[hi]);
        }
        return r;
    }
};

void init(int hi) {
    Minimizator mnp(hi + 1), mnc(hi + 1);
    Maximizator mxp(hi + 1), mxc(hi + 1);
    for (int n = 2; n <= hi; ++n) {
        int hi = min(K, n - 2);
        int c_win = P[n] ? mnc.getMin(n - hi, n - 1) : mnp.getMin(n - hi, n - 1);
        int c_lose = P[n] ? mxc.getMax(n - hi, n - 1) : mxp.getMax(n - hi, n - 1);                
        if (c_win != INF) A[n] = mp(1, c_win + 1);
        else if (c_lose != -INF) A[n] = mp(-1, c_lose + 1);  
        else A[n] = mp(-1, 0);        
        if (P[n]) {
            if (A[n].first == -1) mnp.mod(n, A[n].second);
            else mxp.modMax(n, A[n].second);
        } else {
            if (A[n].first == -1) mnc.mod(n, A[n].second);
            else mxc.modMax(n, A[n].second);
        }        
    }
}

class PrimeCompositeGame {
public:
    int theOutcome( int N, int k ) {
        K = k;
        for (int i = 0; i <= N; ++i) P[i] = false; 
        for (int i = 2; i * i <= N; ++i) {
            if (P[i]) continue;
            for (int j = i * i; j <= N; j += i) {
                P[j] = true;
            }
        }
        for (int i = 2; i <= N; ++i) {
            P[i] = !P[i];
        }
        init(N);
        int c_win = INF;
        int c_lose = 0;
        for (int i = 1; i <= K && i <= N - 2; ++i) {
            if (!P[N - i]) continue;
            pii t = A[N - i];
            if (t.first == 1) c_lose = max(c_lose, t.second + 1);        
            if (t.first == -1) c_win = min(c_win, t.second + 1);                
        }
        if (c_win != INF) return c_win;
        return -c_lose;
    }
};

Div1 1000 - DengklekMessage

#include <string>
#include <string.h>
#include <cstdio>
#include <vector>
using namespace std;
#define mp make_pair
#define sz(x) ((int)((x).size()))
typedef vector<string> vs;
typedef vector<int> vi;
typedef pair<int, int> pii;

using namespace std;
vs P;
string G;
bool Mark[1000][1000];
double dp[1000][1000];
pii C[1000][1000];

vi calcP(string &s) {
    int n = sz(s);
    vi p(n, 0);
    int q = 0;
    for (int i = 1; i < n; ++i) {
        while (q && s[i] != s[q]) q = p[q - 1];
        if (s[i] == s[q]) ++q;
        p[i] = q;
    }
    return p;
}

pii calc(int len, int k) {
    string str = G + "#" + G.substr(0, len) + P[k];
    vi p = calcP(str);
    int x = 0;
    for (int i = 0; i < sz(p); ++i) {
        if (p[i] == sz(G)) {
            ++x;
        }
    }
    int nlen = p.back();
    if (len == sz(G)) --x;
    return mp(x, nlen);    
}


void initC() {
    for (int len = 0; len <= sz(G); ++len) {
        for (int k = 0; k < sz(P); ++k) {
            C[len][k] = calc(len, k);
        }
    }
}

double rec(int k, int len) {
    if (k == 0) return 0;
    if (Mark[k][len]) return dp[k][len];
    Mark[k][len] = true;
    double res = 0.0;
    for (int i = 0; i < sz(P); ++i) {
        int nlen = C[len][i].second;
        int x = C[len][i].first;
        res += rec(k - 1, nlen) + x;
    }
    res /= sz(P);
    return dp[k][len] = res;
}

class DengklekMessage {
public:
    double theExpected( vector <string> pieces, vector <string> goodSubstring, long long K ) {
        P = pieces;
        G = "";
        for (int i = 0; i < sz(goodSubstring); ++i) {
            G += goodSubstring[i];
        }
        initC();
        memset(Mark, false, sizeof(Mark));
        if (K <= sz(G)) return rec(K, 0);
        int L = sz(G);
        double t = rec(L, 0);
        double t1 = rec(L + 1, 0);
        return t + (t1 - t) * (K - L);
    }
};