All numbers are distinct, and they are given in increasing order.

A range will take consecutive elements in this list.

We can try greedy.

class RangeEncoding():
	def minRanges(self,a):
		return len(a)-sum(y==x+1 for x,y in zip(a,a[1:]))

How many distinct strings can we possibly generate?

We can try to simulate the process, but memoize answers.

import java.util.*;

public class RemovingParenthesis {
	Map<String, Integer> memo = new TreeMap<>();
	
	public int countWays(String s) {
		if (memo.containsKey(s)) {
			return memo.get(s);
		}
		if (s.isEmpty()) {
			return 1;
		}
		int balance = 1;
		int ans = 0;
		for (int i = 1; i < s.length(); i++) {
			if (s.charAt(i) == '(') {
				balance++;
				continue;
			}
			ans += countWays(s.substring(1, i) + s.substring(i + 1));
			balance--;
			if (balance == 0) {
				break;
			}
		}
		memo.put(s, ans);
		return ans;
	}
}

Let x[i] be the number of openining parenthesis before the i-th closing parenthesis. Then, we need this parenthesis to be removed at turn x[i] or before.

This is also a sufficient condition. To show this, we will show that if the balance for a particular closing parenthesis goes below zero, then it will be removed after turn x[i].

In particular let's look at the leftmost parenthesis whose balance goes negative. At this point we matched i-1 closing parenthesis to its left correctly and this does not effect the balance. In addition for its balance to go negative, we need to match at least x[i]-i+1 other closing parenthesis on its right. So the first turn we can match this closing parenthesis is strictly after turn x[i] which completes the claim.

Using those conditions, we can see the answer is x[0] * (x[1]-1) * (x[2]-2) * ...

#include <bits/stdc++.h>
using namespace std;

long long mod = 1000000000 + 7;

class ParenthesisRemoval {
	public:	int countWays(string s) {
		long long ret = 1;
		int balance = 0;
		for(int i = 0; i < s.length(); i++) {
			if(s[i] == '(')
				balance ++;
			else {
				ret *= balance;
				ret %= mod;
				balance --;
			}
		}
		return (int)ret;
	}
};

Try to solve Saleswoman (div2 hard) in linear time.

WLOG, suppose we go to leftmost point first. This allows us to fix the leftmost visited point. What is the rightmost point we need to visit in this case?

We need to deal with the fact that we can end anywhere we want. We can do that while we are simulating our greedy solution.

public class Salesman {
    public int minMoves(int[] pos, int[] delta) {
        int n = pos.length;
        int ans = solve1(pos, delta);
        for (int i = 0, j = n-1; i < j; i++, j--) {
            int t = pos[i]; pos[i] = pos[j]; pos[j] = t;
            t = delta[i]; delta[i] = delta[j]; delta[j] = t;
        }
        for (int i = 0; i < n; i++) pos[i] = -pos[i];
        ans = Math.min(ans, solve1(pos, delta));
        return ans;
    }

    public int solve1(int[] pos, int[] delta) {
        int n = pos.length;
        int rightneed = n-1;
        while (rightneed >= 0 && delta[rightneed] >= 0) rightneed--;
        if (rightneed < 0) return 0;

        int[] ndemand = new int[n+1];
        ndemand[n] = n;
        for (int i = n-1; i >= 0; i--) {
            if (delta[i] < 0) ndemand[i] = i;
            else ndemand[i] = ndemand[i+1];
        }
        int ans = 1 << 30;
        outer : for (int left = 0; left < n; left++) {
            int right = rightneed;
            int csum = 0;
            for (int i = left; i <= right; i++) {
                csum += delta[i];
            }
            while (csum < 0) {
                right++;
                if (right >= n) break outer;
                csum += delta[right];
            }

            int cdist = Math.abs(pos[left]) + (pos[right] - pos[left]);
            int chave = 0;
            int cneed = 0;
            int goback = 0;
            for (int i = left; i <= right; i++) {
                if (delta[i] < 0) {
                    if (cneed == 0 && chave >= -delta[i]) {
                        chave -= -delta[i];
                    } else {
                        if (cneed == 0) {
                            goback = Math.max(goback, pos[i]);
                        }
                        cneed += -delta[i];
                    }
                } else {
                    chave += delta[i];
                    if (cneed > 0 && chave >= cneed) {
                        chave -= cneed;
                        cneed = 0;
                        cdist += 2 * Math.max(0, pos[i] - goback);
                    }
                }

                int bb;
                if (cneed > 0) {
                    bb = goback;
                } else {
                    bb = pos[Math.min(right, ndemand[i+1])];
                }

                ans = Math.min(ans, cdist + Math.max(0, (pos[right] - bb)));
            }

            if (delta[left] < 0) break;
        }

        return ans;
    }
}