June 2, 2018 2018 TCO Algorithm Round 2A Editorials

Round 2A is the first round of TCO2018 that marks the start of the “serious” part of the TCO algorithm track since all competitors, including high rated ones (who got a bye in round 1), can compete.
895 competitors qualified through rounds 1A or 1B, while 252 competitors received byes, for a total of 1147 competitors. There are only 200 spots in round 2A for advancement to round 3, (see http://tco18.topcoder.com/algorithm/rules/ for a refresher on the rules). This is also an opportunity to win a t-shirt! (All round 3 participants will earn an exclusive Topcoder t-shirt).
The writer of these problems is [ltdtl]. The writer of this editorial is [lg5293].

Div1 Easy ArithmeticSequenceDiv1:

In this problem, you are given a sequence of numbers. You can change the value of any term to any integer at the cost equal to the absolute difference between the old value and the new value. You can apply this operation as many times as you want, and at the end you want an arithmetic sequence. You would like to know the minimum cost to make this happen.
There are a few different approaches to this problem.
For the first approach, we can first observe that it is never optimal to apply the operation to all elements in the array (i.e. there will always be one element that stays the same). To prove this, suppose we had an optimal answer that did an operation to every element in the array. We can always shift all elements up by one or down by one until one of them equals their original value without increasing the cost of our operations.
Thus, we can iterate through which element stays the same, and also iterate through the possible values of the differences in the arithmetic sequence (this will fix the value of all other elements), then compute the cost to get the minimum. In particular, you can show that since the numbers are bounded from 1 to 100, the optimal difference’s absolute value will not exceed 100.

A sample Java implementation is shown here:
public class ArithmeticSequenceDiv1 {
	public int findMinCost(int[] x) {
		int n = x.length;
		int ans = 0;
		// base solution: change every term to 0.
		for(int i = 0; i < n; i++) ans += x[i];
		for(int i = 0; i < n; i++) { // fix x[i].
			for(int d = -100; d <= 100; d++) {
				int sum = 0;
				for(int j = 0; j < n; j++) {
					int y = x[i] + (j-i)*d;
					sum += Math.abs(x[j] - y);
				}
				ans = Math.min(ans, sum);
			}
		}
		return ans;
	}
};

This code takes O(n^3) time, O(n) from fixing which element stays the same, O(n) for iterating through the differences, and O(n) for computing the cost given fixing the two things above.
For the second approach, let’s first start by trying to solve the easier version of the problem where we want to make all numbers the same.
This is a somewhat standard problem, in which the solution is to make all numbers equal to the median (you can see a proof here: https://math.stackexchange.com/questions/113270/the-median-minimizes-the-sum-of-absolute-deviations).
This can be implemented with the following python code:
def f(a):
m = sorted(a)[len(a)/2]
return sum(abs(y-m) for y in a)
This method takes O(n log n) time to sort, and O(n) to sum the absolute differences.
Now, how do we return back to the arithmetic sequence?
We know our arithmetic sequence is going to be of the form a,a+d,a+2d,…a+(n-1)d.
We’ll show we can reduce our problem of trying to find how to make all the numbers equal.
Let’s pretend we know what d is, and fix d to be a constant.
If our original array is x_0, x_1, …, x_(n-1), let’s replace x_i with z_i = x_i – i * d.
Then, we can see that |x_i – (a + i*d)| is equal to |z_i – a|.
Thus, minimizing the cost to make x an arithmetic sequence with difference d is equivalent to minimizing the cost needed to make z a constant sequence, which we know how to do already!
Thus, it suffices to just try all values of d. What values of d would be reasonable? In this case, since the numbers are bounded from 1 to 100, we can just try d from -100 to 100.
Here is the complete code:

class ArithmeticSequenceDiv1:
	def findMinCost(self,x):
		def f(a):
			m = sorted(a)[len(a)/2]
			return sum(abs(y-m) for y in a)
		return min(f(map(lambda y: y[1]-y[0]*d, enumerate(x))) for d in range(-200,200))

To break this down, enumerate(x) returns an array of tuples [(0, x[0]), (1, x[1]), (2, x[2]), …]. We apply the function y[1] – y[0]*d to each tuple in this list to get z. Finally, we can plug z in to our function f that we wrote earlier to get the minimum cost.
Since we are trying O(n) different values of d, and each d takes O(n log n) time to check, the runtime of this approach is O(n^2 log n).

Div1 Medium MakingRegularGraph:

In this problem, you are given a graph and you would like to add edges so the graph is 2-regular (i.e. all nodes have degree 2). You are not allowed to add multiple edges in this graph. Also, you would like to return the lexicographically smallest solution (as defined in the problem statement).
First, one key observation is that a 2 regular graph consists of disjoint cycles (you can see this reference for a proof: https://math.stackexchange.com/questions/1814242/prove-that-every-vertex-of-a-2-regular-graph-g-lies-on-an-exactly-one-circle/1814269).
To solve the original problem, we know that our graph is a collection of disjoint paths or cycles (path in this case can include a single node by itself). We can ignore already formed cycles, so it suffices to join paths together.
To solve this, we can proceed greedily. Let’s keep a heap of all of our paths. The heap will contain tuples of the form (smaller index endpoint, larger index endpoint).
To choose which edge to add, we only need to consider the top two paths in our heap, and add the edge is lexicographically smallest. We have to be careful about closing a cycle (since if we remove this cycle we need to make sure there are at least 3 nodes remaining to form a full cycle so we can use all nodes in some cycle).
Here is a python implementation.

import heapq
class MakingRegularGraph:
	def addEdges(self,n,x,y):
		if n <= 2:
			return [-1]
		g = [[] for __ in xrange(n)]
		deg = [0 for __ in xrange(n)]
		conn = [[False for _ in xrange(n)] for __ in xrange(n)]
		for i in range(n):
			conn[i][i] = True
		for a,b in zip(x,y):
			g[a].append(b)
			g[b].append(a)
			deg[a] += 1
			deg[b] += 1
			conn[a][b] = True
			conn[b][a] = True
		vis = [False for __ in xrange(n)]
		def dfs(node):
			vis[node] = True
			for a in g[node]:
				if not vis[a]:
					x,y = dfs(a)
					return x,y+1
			return node, 1
		def make(a,b):
			return min(a,b), max(a,b)
		heap = []
		for i in range(n):
			if not vis[i] and deg[i] <= 1: o, count = dfs(i) heapq.heappush(heap, (make(o,i), count)) have = sum(vis) if len(heap) == 0: return [] ans = [] while len(heap) > 1:
			t1 = heapq.heappop(heap)
			s1 = t1[0]
			n1 = t1[1]
			t2 = heapq.heappop(heap)
			s2 = t2[0]
			n2 = t2[1]
			if make(s1[0],s1[1]) < make(s1[0],s2[0]) and not conn[s1[0]][s1[1]] and have - n1 > 2:
				ans.extend(make(*s1))
				have -= n1
				heapq.heappush(heap, t2)
			else:
				conn[s1[0]][s2[0]] = True
				conn[s2[0]][s1[0]] = True
				ans.extend(make(s1[0],s2[0]))
				heapq.heappush(heap, (make(s1[1],s2[1]), n1+n2))
		if conn[heap[0][0][0]][heap[0][0][1]]:
			return [-1]
		ans.extend(make(*heap[0][0]))
		return ans

The time complexity of this approach is O(n log n), since there are at most O(n) iterations of the while loop, each of which takes O(log n) time to perform.

Div1 Hard ObtuseTrianglesDiv1:

In this problem, we are given numbers a, a+1, a+2, …, a+3*n-1, and we would like to group these numbers into triples so that each triple can be the side lengths of an obtuse triangle.
Let’s do this construction recursively.
Let’s fix a, and for small enough n, we can do a brute force to generate a solution.
Now, let k = floor(n/2), and given a valid solution for (a, k), we will show how to generate a solution for (a, n).
The triangles for (a, k) are (x_1, y_1, z_1), …, (x_k, y_k, z_k), all obtuse, with x_i < y_i < z_i. In addition, we will also add the restriction that x_1 = a, x_2 = a+1, … x_(n/2) = a+k-1.
For (a, n), we can first create triangles k triangles of the form (x_i, y_i + (n – k), z_i + (n – k)). We can check this is still an obtuse triangle. This will take numbers from the union of intervals [a, a+k-1] and [a+k+(n-k),a+3*k-1+(n-k)] = [a+n,a+n+2*k-1]
The remaining (n-k) triangles can be of the form (k+i+a, k+i+2*n+a, 2*k+n+i+a) for i between 0 and n-k-1, inclusive.
This will take numbers from union of intervals [k+a,k+(n-k)-1+a] = [k+a, n-1+a], [k+2*n+a,k+n-k-1+2*n] = [k+2*n+a,3*n-1], and [2*k+n+a, 2*k+n+n-k-1+a] = [a+n+2*k, 2*n+k+a-1].
Also, we can see that the smallest side of all the triangles form the numbers in the interval [a,a+n-1] inclusive, so this completes the recursion.
We can check these 3n triangles are obtuse, and the side lengths are distinct integers between a and a+3*n-1, inclusive.
See the sample Java implementation below:

import java.util.Set;
import java.util.HashSet;
public class ObtuseTrianglesDiv1 {
	boolean doit(long[][] sav, int mini, int n, int x, int mask) {
		if(x == n) {
			return true;
		}
		int a = x, b, c;
		if((mask & (1<<a)) != 0) { // should not be reached.
			return false;
		}
		for(b = n; b < 3*n; b++) {
			if((mask & (1<<b)) != 0) continue;
			for(c = b+1; c < 3*n; c++) {
				if((mask & (1<<c)) != 0) continue;
				if((a+mini)+(b+mini) <= (c+mini)) break; if((mini+a)*(mini+a)+(mini+b)*(mini+b) >= (mini+c)*(mini+c)) continue;
				sav[x][0] = a+mini; sav[x][1] = b+mini; sav[x][2] = c+mini;
				if(doit(sav, mini, n, x+1, mask+(1<<a)+(1<<b)+(1<<c)))
					return true;
			}
		}
		return false;
	}
	long[] brute(int a, int n) {
		if(a==1) return new long[0];
		long[][] sav = new long[n][];
		for(int i = 0; i < n; i++) sav[i] = new long[3];
		if(doit(sav, a, n, 0, 0)) {
			long[] ret = new long[n];
			for(int l = 0; l < n; l++) {
				long val = sav[l][0];
				val *= 10000L;
				val += sav[l][1];
				val *= 10000L;
				val += sav[l][2];
				ret[l] = val;
			}
			return ret;
		}
		return new long[0];
	}
	long encode(long x, long y, long z) {
		long ret = x;
		ret *= 10000L; ret += y;
		ret *= 10000L; ret += z;
		return ret;
	}
	public long[] findObtuseTriangles(int a, int n) {
		if(a==1) return new long[0];
		switch(a) {
			case 2:
			if(n <= 1) return brute(a, n);
			break;
			case 3: case 4:
			if(n <= 3) return brute(a, n);
			break;
			case 5: case 6:
			if(n <= 7) return brute(a, n);
			break;
			case 7: case 8: case 9: case 10:
			if(n <= 9) return brute(a, n);
			break;
			default: // should not be reached.
			return new long[0];
		}
		int hn = n/2; // solve smaller problem first.
		long[] tmp = findObtuseTrianglesInternal(a, hn);
		long[] ret = new long[n];
		for(int i = 0; i < n; i++) {
			if(i < hn) {
				long x, y, z;
				z = tmp[i] % 10000;
				y = (tmp[i]/10000) % 10000;
				x = (tmp[i]/10000/10000);
				y += (n-hn);
				z += (n-hn);
				ret[i] = encode(x, y, z);
			} else {
				long x, y, z;
				x = i+a;
				y = i + 2*n + a;
				z = i + n + hn+a;
				ret[i] = encode(x, y, z);
			}
		}
		return ret;
	}
};