May 3, 2018 2018 TCO Algorithm Round 1B Editorials

This round had three different authors namely Nickolas, ltdtl and misof.

2018 TCO Algorithm Round 1A Easy: LineOff

The author of this problem is Nickolas.
In this problem, you are given a sequence of points on a line.
Each point can have some color. In one move, you can remove two adjacent points which have the same color. You would like to know the maximum number of moves you can do.
There are various approaches to this problem.
One key observation is that is doing a move will never hurt us, so we can always do any move whenever we find one.
Thus, we can repeatedly find a move, do it, and recursively solve it on the string with those two points removed.
There are at most n/2 moves we can do, and searching for a single moves takes O(n) time, so the overall runtime of this approach is O(n^2)
You can see the Python code below for more details:

class LineOff:
	def movesToDo(self,pts):
		for i in range(len(pts)-1):
			if pts[i]==pts[i+1]:
				return 1 + self.movesToDo(pts[:i] + pts[i+2:])
		return 0

We can do this even faster using a stack.
Consider adding the points one by one from left to right. Let’s keep a stack, which is initially empty.
When considering a point, we can check if the stack is non empty and if the top of the stack matches our current color. If so, we can do a move, and pop the top of the stack. Otherwise, we can push our current color onto the stack.
This is similar to the approach above, but doesn’t re-search from the beginning of the string when we do a move. Since all the stack operations are constant time, and we only go through the list once, the running time of this approach is O(n).
You can see this Python code below for more details:

class LineOff:
	def movesToDo(self,pts):
		stack = []
		ans = 0
		for x in pts:
			if stack and stack[-1] == x:
				stack.pop()
				ans += 1
			else:
				stack.append(x)
		return ans

2018 TCO Algorithm Round 1A Medium: StablePairsDiv1

The author of this problem is ltdtl.
In this problem, you are given three integers n,c,k, you would like to find a sequence x_1, y_1, x_2, y_2, …, x_k, y_k such that the three conditions are satisfied:
Each x_i and y_i must be between 1 and n, inclusive.
x_1, y_1, x_2, y_2, …, must be a strictly increasing sequence.
(x_(i+1) + y_(i+1)) – (x_i + y_i) = c for all valid i.
Our task is to find a sequence that satisfies these three conditions. If there are multiple such sequences, we can return any that have maximum sum.
The third condition hints us to define z_i = x_i + y_i. Condition 3 just states that z_(i+1) – z_i = c, so z_i forms an arithmetic sequence with difference c.
Thus, to maximize our sum, we can see this is equivalent to maximizing z_k.
Now, given any valid sequence, we can add a constant term to all numbers to get a valid sequence. Thus, we know we can set y_k without any consequence. Similarly, we can show that if there is a solution, then there is one where x_k is n-1.
So, we can reduce this problem to, construct a strictly increasing sequence, where the last two terms sum to sum number W. We can solve this recursively by adding elements in two at a time greedily from the end. See the python code below for more details.
You can see the python code for more details:

class StablePairsDiv1:
	def merge(self,a,b):
		return a and a+b
	def get(self,n,want):
		d = n+n-1-want
		return [n-1-d/2-d%2,n-d/2]
	def findMaxStablePairs(self,n,c,k,wantsum=None):
		if wantsum is None: wantsum = n+n-1
		if not 1+2 <= wantsum <= n+n-1: return []
		g = self.get(n,wantsum)
		return g if k == 1 else self.merge(self.findMaxStablePairs(g[0]-1,c,k-1,sum(g)-c), g)

This greedy can be hard to prove during the contest, and there is an easier to prove dynamic programming solution that also works. In particular, we can just keep track of the last two elements of our sequence, and consider appending two more elements, and check that this satisfies all the conditions.
The runtime is slightly slower, but correctness should be easier.
… todo more explanation
See the Java code below for more details:

public class StablePairsDiv1 {
	boolean[][][] dp;
	int[][][] prev; // [k][n][2*n]
	int[] trace(int c, int i, int y, int is) {
		int[] ans = new int[i*2];
		while(i >= 1) {
			int x = is + (i-1)*c - y;
			ans[i*2-2] = x;
			ans[i*2-1] = y;
			int w = prev[i][y][is];
			i--;
			y=w;
		}
		return ans;
	}
	public int[] findMaxStablePairs(int n, int c, int k) {
		int[] ans = new int[0];
		if(k > n/2) return ans;
		// init.
		dp = new boolean[k+1][][];
		prev = new int[k+1][][];
		for(int i = 0; i <= k; i++) {
			dp[i] = new boolean[n+1][];
			prev[i] = new int[n+1][];
			for(int y = 1; y <= n; y++) {
				dp[i][y] = new boolean[2*n+1];
				prev[i][y] = new int[2*n+1];
				for(int is = 0; is <= n+n; is++)
					dp[i][y][is] = false;
			}
		}
		// solve.
		int min_s = (1+2), max_s = (n-1)+n;
		for(int i = 1; i <= k; i++) { // k boolean updated = false; for(int is = max_s; is >= min_s; is--) { // 2n (actually, much smaller if k is big.)
				for(int y = n; y >= 2; y--) { // n
					int x = is + (i-1)*c - y;
					if(x >= y) break;
					if(x<1) continue;
					if(i==1) {
						dp[i][y][is] = true;
						updated = true;
					}
					else {
						for(int w = 1; w < x; w++) { // n
							if(dp[i-1][w][is]) {
								dp[i][y][is] = true;
								updated = true;
								prev[i][y][is] = w;
								break;
							}
						}
					}
					if(i==k && dp[i][y][is]) {
						return trace(c, i, y, is);
					}
				}
			}
			if(!updated) break;
		}
		return ans;
	}
}

2018 TCO Algorithm Round 1A Hard: ThreeSameLetters

The author of this problem is misof.
In this problem, we want to count the number “one block strings” of length L that consist of the first S characters of the alphabet. A “one block string” is a string that contains exactly one block, where a block is three consecutive equal character. For example “abbba” is a one-block string, but “aaaa” is not (i.e. in this case, the two blocks overlap).
This suggests a dynamic programming approach. I’ll highlight a variety of approaches.
Typically, in dynamic programming problem, it helps to think about what state we need to keep track to just determine if a string is valid or not. For example, to determine if a string is valid, we would need to keep track of whether we have seen a block yet, and what the last two characters are.
Thus, this suggests a dp state of dp[p][i][j][k] -> number of ways to make a string of length p, given there are exactly i blocks in this prefix, the second to last character is j, and the last character is k.
There are L * 2 * S * S states in this dp table, and each state requires looking at S transitions (i.e. characters we can add), so the overall runtime is O(L*S^3).
Here is the first approach in Java.

import java.util.*;
import java.util.regex.*;
import java.lang.*;
import java.io.*;
public final class ThreeSameLetters {
    public int countStringsSlower (int L, int S) {
        if (L == 1) return 0;
        int[][][] counts = new int[2][S][S];
        # at l-th iteration, cnt[i][j][k] -> number of ways to make str of length l with exactly i blocks of length 3, and the last characters being j,k
        for (int c=0; c<2; ++c) for (int s1=0; s1<S; ++s1) for (int s2=0; s2<S; ++s2) counts[s1][s2] = 1-c;
        for (int l=0; l<L-2; ++l) {
            int[][][] newcounts = new int[2][S][S];
            for (int c=0; c<2; ++c) for (int s1=0; s1<S; ++s1) for (int s2=0; s2<S; ++s2) newcounts[s1][s2] = 0;
            for (int c=0; c<2; ++c) for (int s1=0; s1<S; ++s1) for (int s2=0; s2<S; ++s2) for (int s3=0; s3<S; ++s3) { if (c == 1 && s1 == s2 && s2 == s3) continue; int add = (s1 == s2 && s2 == s3) ? 1 : 0; newcounts[s2][s3] += counts[s1][s2]; if (newcounts[s2][s3] >= 1000000007) newcounts[s2][s3] -= 1000000007;
            }
            counts = newcounts;
        }
        int answer = 0;
        for (int s1=0; s1<S; ++s1) for (int s2=0; s2<S; ++s2) { answer += counts[1][s1][s2]; if (answer >= 1000000007) answer -= 1000000007;
        }
        return answer;
    }
}

We can make this slightly faster by noting we don’t need to explicitly store what the exact characters are. All that matters is the length of the a suffix of equal characters. When adding a character, either it is the same as the current suffix of equal characters (1 way to extend this), or it is different (S-1) ways to choose this. This speeds up our algorithm so it does not depend on S. In particular, it gets rid of all factors of S, so this algorithm’s runtime is O(L) with some constant factors.
Here is a Java solution of the second solution.

import java.util.*;
import java.util.regex.*;
import java.lang.*;
import java.io.*;
public final class ThreeSameLetters {
    public int countStrings (int L, int S) {
        long[][][] cnt = new long[L+1][2][3];
        // cnt[i][j][k] -> number of ways to make str of length i with exactly j blocks of length 3, and the last k characters equal
        cnt[0][0][0] = 1;
        for (int l=0; l<L; ++l) {
            for (int b=0; b<=1; ++b) {
                for (int s=0; s<=2; ++s) {
                    // append a different letter
                    cnt[l+1][b][1] += cnt[l][b][s] * (S-1);
                    // append the same letter
                    if (s == 2) {
                        if (b == 0) cnt[l+1][1][2] += cnt[l][b][s];
                    } else {
                        cnt[l+1][b][s+1] += cnt[l][b][s];
                    }
                }
            }
            for (int b=0; b<=1; ++b) {
                for (int s=0; s<=2; ++s) {
                    cnt[l+1][b][s] %= 1000000007;
                }
            }
        }
        return (int)((cnt[L][1][1] + cnt[L][1][2])%1000000007);
    }
};

We can speed this up by a constant factor even further.
Let’s approach this problem from a different direction. Let’s fix the position of the block in our string. Then, the prefix before the block and suffix after the block are completely independent. We can also note these problems are also identical (i.e. only depend on the length of the prefix/suffix).
To solve this problem, let’s consider how we want to fill our suffix. We can go from left to right starting from our block. We first choose a character different from the last character added (or if no character has been added yet, choose the character from the block), and then append this character exactly once or twice to our string. Thus, this can be computed with a dp also. (This should look similar to how fibonacci numbers are computed).
The runtime of this approach is O(L), with a better constant factor than the second solution.
See the Python code below for more details.

class ThreeSameLetters:
	def countStrings(self,L,S):
		t = [1, S-1]
		for i in range(L):
			t.append((t[-1] + t[-2]) * (S-1))
		return S * sum(t[i]*t[L-3-i] for i in range(L-3+1)) % 1000000007