SRM 530

Div2 - 250 GogoXBallsAndBinsEasy
My intuition told me very simple solution. But I don't tried to prove it.

public class GogoXBallsAndBinsEasy {
    public int solve(int[] T) {
        int ans = 0;
        for (int i = 0; i < T.length / 2; ++i) {
            ans += T[T.length - 1 - i] - T[i];
        }
        return ans;
    }
}

Div2 - 500, Div1 - 250 GogoXCake

public class GogoXCake {
    public String solve(String[] cake, String[] cutter) {
        int n = cake.length;
        int m = cake[0].length();
        int r = cutter.length;
        int c = cutter[0].length();
        char a[][] = new char[n][m];
        for (int i = 0; i < n; ++i) {
            a[i] = cake[i].toCharArray();
        }
        for (int i = 0; i + r <= n; ++i) {
            for (int j = 0; j + c <= m; ++j) {
                boolean ok = true;
                for (int i1 = 0; i1 < r; ++i1) {
                    for (int j1 = 0; j1 < c; ++j1) {
                        if (cutter[i1].charAt(j1) != '.') {
                            continue;
                        }
                        if (a[i + i1][j + j1] != '.') {
                            ok = false;
                        }
                    }
                }
                if (!ok) {
                    continue;
                }
                for (int i1 = 0; i1 < r; ++i1) {
                    for (int j1 = 0; j1 < c; ++j1) {
                        if (cutter[i1].charAt(j1) == '.') {
                            a[i + i1][j + j1] = 'X';
                        }
                    }
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (a[i][j] == '.') {
                    return "NO";
                }
            }
        }
        return "YES";
    }
}

Div2 - 1000 GogoXReimuHakurai
Div1 - 500 GogoXMarisaKirisima
Despite the fact that these problems are different (second problem is more common) we can solve them using same approach.

public class GogoXMarisaKirisima {
    public int solve(String[] choices) {
        int n = choices.length;
        boolean a[][] = new boolean[n][n];
        for (int i = 0; i < n; ++i) {            
            for (int j = 0; j < n; ++j) {
                if (i == j) a[i][i] = true;
                else a[i][j] = choices[i].charAt(j) == 'Y';
            }
        }
        for (int k = 0; k < n; ++k) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (a[i][k] && a[k][j]) {
                        a[i][j] = true;
                    }
                }
            }
        }
        if (!a[0][n - 1]) return 0;
        int V = 0, E = 0;
        boolean use[] = new boolean[n];
        for (int i = 0; i < n; ++i) {
            use[i] = a[0][i] && a[i][n - 1];
        }
        for (int i = 0; i < n; ++i) {
            if (!use[i]) continue;
            ++V;
            for (int j = 0; j < n; ++j) {
                if (!use[j]) continue;
                if (choices[i].charAt(j) == 'Y') {
                    ++E;
                }
            }
        }
        return  E - V +  2;
    }
}

Div1 - 1000 GogoXBallsAndBins

import java.util.*;

public class GogoXBallsAndBins {
    int need, N;
    int[] T;
    Map m[][];
    static final long MOD = 1000 * 1000 * 1000 + 9;
    int rec(int k, int wait, int cum) {
        if (k == N) {
            if (cum == need && wait == 0) return 1;
            return 0;
        }
        if (m[k][wait].containsKey((Integer)cum)) 
            return (Integer)m[k][wait].get(cum);
        long res = rec(k + 1, wait, cum);
        long w = wait;
        if (wait > 0) {
            res += rec(k + 1, wait, cum) * w * 2; 
            res += rec(k + 1, wait - 1, cum + 2 * T[k]) * w * w;
        }
        res += rec(k + 1, wait + 1, cum - 2 * T[k]);
        res %= MOD;
        m[k][wait].put(cum, (int)res);
        return (int)res;
    }

    public int solve(int[] T, int moves) {
        this.T = T;
        need = 2 * moves;
        N = T.length;
        m = new Map[N + 1][N + 1];
        for (int i = 0; i <= N; ++i) {
            for (int j = 0; j <= N; ++j) {
                m[i][j] = new HashMap();
            }
        }
        return rec(0, 0, 0);
     }
}

One sum computation

Solving one problem I encountered one problem. I needed calculate one interesting sum: sigma(N / i), where (1 <= i && <= K). How we can do it as fast as possible. We can do it using complexity sqrt(N) moving from two ends. Following code demonstate this approach.

    long smart(long N, long K) {
        long res = 0;
        long t = (long)Math.sqrt(N * 1.0);
        for (long i = 1; i * i < N; ++i) {
            if (i <= K) res += N / i;
            long lo = Math.max(N / (i + 1), t);
            long hi = Math.min(N / i, K);
            if (hi > lo) res += (hi - lo) * i;
        }
        if (t * t == N && t <= K) res += t;
        return res;
    }

After it I recall one neerc problem. But there we need compute a little different sum: sigma(N % i), where (1 <= i && <= K). So we can replace N % i to (N - N / i * i) and addopt previous code to calculate sigma(N / i * i).

SRM 529

Div2 - 250 PairingPawns

public class PairingPawns {
    public int savedPawnCount(int[] start) {
        int n = start.length;
        for (int i = n - 1; i > 0; --i) {
            start[i - 1] += start[i] / 2;
        }
        return start[0];
     }
}

Div2 - 500, Div1 - 250 KingSort

import java.util.*;

public class KingSort implements Comparator<String> {
    Map<String, Integer> map = new HashMap<String, Integer>();

    public String[] getSortedList(String[] kings) {
        String s1[] = ",I,II,III,IV,V,VI,VII,VIII,IX,X".split(",");
        String s2[] = ",X,XX,XXX,XL,L".split(",");
        for (int i = 1; i <= 50; ++i) {
            map.put(s2[i / 10] + s1[i % 10], i);
        }
        Arrays.sort(kings, this);
        return kings;
    }
    public int compare(String s1, String s2) {
        String t1[] = s1.split(" ");
        String t2[] = s2.split(" ");
        if (!t1[0].equals(t2[0])) return t1[0].compareTo(t2[0]);
        return map.get(t1[1]).compareTo(map.get(t2[1]));
    }
}

Div2 - 1000 MinskyMysteryDiv2

public class MinskyMysteryDiv2 {
    long get(long N) {
        if (N < 2) return -1;
        long i = 2;
        while (i * i <= N && N % i != 0) ++i;
        if (i * i > N) i = N;
        return N / i + i;
    }
    public long computeAnswer(long N) {
        return get(N);
        
     }
}

Div1 - 600 MinskyMystery

import java.util.*;

public class MinskyMystery {

    final int MOD = 1000 * 1000 * 1000 + 9;

    long add(long r, long x) {
        x %= MOD;
        if (x < 0) x += MOD;
        return (r + x) % MOD;
    }

    // get sum N/i (i == 1..N)
    long clever(long N) {
        long res = 0;
        long t = (long)Math.sqrt(1.0 * N);
        long i;
        for (i = 1; i * i < N; ++i) {
            res += N / i;
            if (N / i > t) res += (N / i - N / (i + 1)) * i;
        }
        if (i * i == N) res += i;
        return res;
    }

    public int computeAnswer(long N) {
        if (N < 2) return -1;
        long r = 1;
        long j = 2;
        while (j * j <= N && N % j != 0) ++j;
        if (j * j > N) j = N;

        r = add(r, 2 * j - 3);
        r = add(r, (j - 1) % MOD * (N % MOD) % MOD * 3); 
        r = add(r, (j - 2) % MOD * (N % MOD) % MOD); 

        if (j == N) {
            r = add(r, clever(N) - N);
        } else {
            for (long i = 2; true; ++i) {
                r = add(r, N / i);
                if (N % i == 0) break; 
            }
        }
        return (int)r;
    }
}

Div1 - 900 BigAndSmallAirports

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