SRM 528

Div2 - 250 MinCostPalindrome

public class MinCostPalindrome {
    public int getMinimum(String s, int oCost, int xCost) {
        int n = s.length();
        char a[] = s.toCharArray();
        int res = 0;
        for (int i = 0; i < n / 2; ++i) {
            if (a[i] != '?' && a[n - i - 1] != '?') {
                if (a[i] != a[n - i - 1]) {
                    return -1;
                }
            } else {
                if (a[i] == '?' && a[n - i - 1] == '?') {
                    res += Math.min(oCost, xCost) * 2;
                } else if (a[i] == 'o' || a[n - i - 1] == 'o') {
                    res += oCost;
                } else {
                    res += xCost;
                }
            }
        }
        return res;
    }
}

Div2 - 500, Div1 - 250 Cut

import java.util.Arrays;
public class Cut {
    public int getMaximum(int[] lens, int cuts) {
        Arrays.sort(lens);
        int res = 0;
        for (int len : lens) {
            if (len % 10 != 0) continue;
            int need = len / 10 - 1;
            if (cuts >= need) {
                res += need + 1;
                cuts -= need;
            } else {
                res += cuts;
                cuts = 0;
            }
        }
        for (int len : lens) {
            if (len % 10 == 0 || len < 10) continue;
            int need = len / 10;
            if (cuts >= need) {
                res += need;
                cuts -= need;
            } else {
                res += cuts;
                cuts = 0;
            }
        }
        return res;
    }
}

Div2 - 1000 Mosquitoes

Div1 - 500 SPartition

Div1 - 1000 ColorfulCookie

public class ColorfulCookie {
    int[] cookies;
    int n, P1, P2;
    static final int MAX = 1000;
    int dp[][] = new int[MAX + 1][51];

    int rec(int n1, int k) {
        if (k == cookies.length) {
            if (n1 == 0) return 0;
            return Integer.MIN_VALUE;
        }
        if (dp[n1][k] != -1) return dp[n1][k];
        int res = Integer.MIN_VALUE;
        for (int i = 0; i <= n1 && P1 * i <= cookies[k]; ++i) {
            int left = cookies[k] - P1 * i;
            int j = Math.min(left / P2, n - i);
            int t = rec(n1 - i, k + 1);
            if (t == Integer.MIN_VALUE) continue;
            res = Math.max(res, t + j);
        }
        return dp[n1][k] = res;
    }

    boolean check(int n) {
        this.n = n;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= cookies.length; ++j) {
                dp[i][j] = -1;
            }
        }
        return rec(n, 0) >= n;
    }
    public int getMaximum(int[] cookies, int P1, int P2) {
        this.cookies = cookies;
        this.P1 = P1;
        this.P2 = P2;
        int sum = 0;
        for (int cur : cookies) {
            sum += cur;
        }
        int lo = 0, hi = sum / (P1 + P2) + 1;
        hi = 1001;
        while (hi - lo > 1) {
            int mid = (lo + hi) / 2;
            if (check(mid)) lo = mid;
            else hi = mid;
        }
        return lo * (P1 + P2);
    }
}

SRM 526.5

Div2 - 250 MagicStonesStore

public class MagicStonesStore {
    public String ableToDivide(int n) {
        return n > 1 ? "YES" : "NO";
    }
}

Div2 - 500, Div1 - 250 MagicCandy

public class MagicCandy {
    public int whichOne(int n) {
        int t = (int)Math.sqrt(n * 1.0);
        if (t * t == n) return n - t + 1;
        int tmp = (t + 1) * (t + 1) - (t + 1) + 1;
        if (tmp <= n) return tmp;
        return t * t + 1;
    }
}

Div2 - 1000 MagicNaming

public class MagicNaming {
    String S;
    
    boolean check(String s1, String s2) {
        String t1 = s1 + s2;
        String t2 = s2 + s1;
        return t1.compareTo(t2) <= 0;
    }
    Integer dp[][] = new Integer[100][100];
    int rec(int k, int prev) {
        if (k == S.length()) return 0;
        if (dp[k][prev] != null) return dp[k][prev];
        String s = S.substring(prev, k);
        int res = Integer.MIN_VALUE;    
        for (int i = k; i < S.length(); ++i) {
            String t = S.substring(k, i + 1);
            if (check(s, t)) {
                int x = rec(i + 1, k);
                if (x == Integer.MIN_VALUE) continue;
                res = Math.max(res, x + 1);
            }
        }
        return dp[k][prev] = res;
    }

    public int maxReindeers(String magicName) {
        this.S = magicName;
        return rec(0, 0);
     }
}

Div1 - 500 MagicBlizzard

Div1 - 1000 MagicMatchesGame

SRM 527

Div 2 250 - P8XMatrixTransformation
It is obvious that we can transform source matrix to destination matrix if and only if number of ones in the first matrix equals number of ones in the second matrix (We always can swap any two elements of source matrix using given operation).

public class P8XMatrixTransformation {
    public String solve(String[] original, String[] target) {
        int n = original.length;
        int m = original[0].length();
        int c = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (original[i].charAt(j) == '1') ++c;
                if (target[i].charAt(j) == '1') --c;
            }
        }
        if (c == 0) return "YES";
        return "NO";
    }
}

Div2 550, Div1 275 - P8XGraphBuilder
As we can see from statement we have to build tree. Any tree has (N - 1) edges where N - number of vertexes. Since each edge (u, v) increase by one degree of u and v then sum of all vertexes degree in tree equals 2(E - 1) and each degree is not greater than N - 1 and not less than 1. If we become any array of degree (call it d) which satisfied previous restrictions we can always build tree using this array.  How we can do it? Sort array in non decreasing order and then let pick up first vertex (its degree is one) and connect it with first not one degree vertex with decreasing them degrees. Note that array keep non decreasing order. Repeat this operation until array would be as (1, 1) and add last edge. We become tree because in process we can't build cycle since we always added edges from left to right by array. And last action consists in finding optimal solution. We can do it using dynamic programming (like knapsack algorithm).

import java.util.Arrays;
public class P8XGraphBuilder {
    public int solve(int[] scores) {
        int N = scores.length + 1;
        int W = 2 * (N - 1);
        int dp[][] = new int[N + 1][W + 1];
        for (int i = 0; i <= N; ++i) {
            Arrays.fill(dp[i], Integer.MIN_VALUE);
        }
        dp[0][0] = 0;
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j < N; ++j) {
                int c = scores[j - 1];
                for (int k = j; k <= W; ++k) {
                    dp[i][k] = Math.max(dp[i][k], dp[i - 1][k - j] + c); 
                }
            }
        }
        return dp[N][W];
    }
}

Div1 1050 - P8XCoinChange

public class P8XCoinChange {
    static final int MOD = 1000 * 1000 + 3;

    int[][] mul(int[][] a, int[][] b) {
        int n = a.length;
        int c[][] = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                long cum = 0;
                for (int k = 0; k < n; ++k) {
                    cum += (long)a[i][k] * b[k][j];
                }
                c[i][j] = (int)(cum % MOD);
            }
        }
        return c;
    }
    int[][] pow(int a[][], long n) {
        int r[][] = new int[a.length][a.length];
        for (int i = 0; i < a.length; ++i) {
            r[i][i] = 1;
        }
        for (; n != 0; n >>= 1) {
            if ((n & 1) == 1) {
                r = mul(r, a);
            }
            a = mul(a, a);
        }
        return r;
    }
    public int solve(long sum, long[] vals) {
        int n = vals.length;
        int a[][][] = new int[n][n][n];
        for (int i = 0; i < n; ++i) {
            a[0][i][0] = 1;
        }
        for (int i = 1; i < n; ++i) {
            a[i] = pow(a[i - 1], vals[i] / vals[i - 1]);
            for (int k = i; k < n; ++k) {
                a[i][k][i]++;
            }
        }
        int r[][] = new int[n][n];
        for (int i = 0; i < n; ++i) {
            r[i][i] = 1;
        }
        for (int i = n - 1; i >= 0; --i) {
            long val = vals[i]; 
            long pw = sum / val;
            sum %= val;
            r = mul(r, pow(a[i], pw));
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += r[n - 1][i];
            ans %= MOD;
        }
        return ans;
     }
}

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