class RelativeHeights():
	def countWays(arr):
		def normalize(r):
			w = list(sorted(r))
			return [r.index(x) for x in w]
		print len(set(tuple(normalize(arr[:i] + arr[i+1:])) for i in range(len(arr))))

First, let '(' denote +1, and ')' denote -1. Then, a sequence is correct if all prefixes have nonnegative sum, and the overall sequence has sum 0. Let's ignore the constraint about overall sum being 0 (we can easily check this before doing anything). So, correct sequence can be extended from a previous correct sequence as long as its prefix sum stays nonnegative. So, this helps us write a dp state dp[i][j][k] -> # ways to form a correct sequence given we've used i characters from the first sequence, j characters from the second sequence, and our current prefix sum is k. This is fast enough for this problem.

We don't actually need to store the actual prefix sum, since it's uniquely determined by the first i characters of the first string and first j characters of the second string.

public class InterleavingParenthesisDiv2 {
    public int mod = 1000000007;
    public int countWays(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[] p1 = new int[n+1], p2 = new int[m+1];
        for (int i = 1; i <= n; i++) p1[i] = p1[i-1] + (s1.charAt(i-1) == '(' ? +1 : -1);
        for (int i = 1; i <= m; i++) p2[i] = p2[i-1] + (s2.charAt(i-1) == '(' ? +1 : -1);
        int[][] dp = new int[n+1][m+1];
        dp[0][0] = 1;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (p1[i] + p2[j] < 0) {
                    dp[i][j] = 0;
                    continue;
                }
                if (i>0) dp[i][j] += dp[i-1][j];
                if (j>0) dp[i][j] += dp[i][j-1];
                dp[i][j] %= mod;
            }
        }
        return p1[n] + p2[m] == 0 ? dp[n][m] : 0;
    }
}

Look at example 3.

Example 3 suggests if we want to split our line into k parts such that the maximum length part is minimized.

Let's try to reverse the problem and use binary search instead. Now, we can see that we can proceed greedily.

public class ChainCity {
    public int findMin(int[] dist, int k) {
        int n = dist.length;
        int sum = 0;
        for (int x : dist) sum += x;
        int lo = 0, hi = sum;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            long curlen = 0;
            int nums = 1;

            for (int x = 0; nums <= k && x < n; x++) {
                if (dist[x] + curlen > mid) {
                    nums++;
                    curlen = 0;
                } else {
                    curlen += dist[x];
                }
            }

            if (nums <= k) hi = mid;
            else lo = mid+1;
        }

        return lo;
    }
}

public class InterleavingParenthesis {
    public int mod = 1000000007;
    public int countWays(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[] p1 = new int[n+1], p2 = new int[m+1];
        for (int i = 1; i <= n; i++) p1[i] = p1[i-1] + (s1.charAt(i-1) == '(' ? +1 : -1);
        for (int i = 1; i <= m; i++) p2[i] = p2[i-1] + (s2.charAt(i-1) == '(' ? +1 : -1);
        int[][] dp = new int[n+1][m+1];
        dp[0][0] = 1;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (p1[i] + p2[j] < 0) {
                    dp[i][j] = 0;
                    continue;
                }
                if (i>0) dp[i][j] += dp[i-1][j];
                if (j>0) dp[i][j] += dp[i][j-1];
                while (dp[i][j] >= mod) dp[i][j] -= mod;
            }
        }
        return p1[n] + p2[m] == 0 ? dp[n][m] : 0;
    }
}

Think about what happens if this is a line. Also, see example 3.

Read the solution for ChainCity in div2.

public class CircleCity {
    public int findMin(int[] dist, int k) {
        int n = dist.length;
        int sum = 0;
        for (int x : dist) sum += x;
        int lo = 0, hi = sum;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            boolean ok = false;
            for (int start = 0; !ok && start < n; start++) {
                long curlen = 0;
                int nums = 1;

                for (int x = 0; nums <= k && x < n-1; x++) {
                    int curpos = (start + x) % n;
                    if (dist[curpos] + curlen > mid) {
                        nums++;
                        curlen = 0;
                    } else {
                        curlen += dist[curpos];
                    }
                }

                ok |= nums <= k;
            }
            if (ok) hi = mid;
            else lo = mid+1;
        }
        return lo;
    }
}

When do we have f(arr, |arr|-1) = |arr|?

Can we generalize this condition to when f(arr, |arr|-k) = (|arr| choose k)?

Try to come up with a way to compute g(arr) in polynomial time. Then, this means we can run a brute force over all permutations. This might be a bit slow for n=12, so are there ways to prune?

public class PermutationSubsequence {
    public boolean ok(int[] brr, int[] arr, int idx, int used, int k) {
        if (idx == brr.length) return true;
        for (int i = 0; i < brr.length; i++) {
            if (((used >> i) & 1) == 0 || arr[idx] == i) {
                boolean ok = true;
                for (int j = 0; ok && j < idx; j++) {
                    if (idx - j + Math.abs(i - brr[j]) < k)
                        ok = false;
                }
                if (ok) {
                    brr[idx] = i;
                    if (ok(brr, arr, idx+1, used|(1<<i), k))
                        return true;
                }
            }
        }
        return false;
    }
    public int[] findBest(int[] arr) {
        int n = arr.length;
        int[] ret = new int[n];
        int uu = 0; for (int x : arr) if (x >= 0) uu |= 1 << x;
        for (int i = n; i >= 1; i--) {
            if (ok(ret, arr, 0, uu, i)) {
                return ret;
            }
        }
        return null;
    }
}