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);
    }
};