SWERC notebook: Not Paranoid Enough

Oct 2, 2015 Others

This is (part of) the notebook for my SWERC team, Not Paranoid Enough. We still accept name suggestions. There are comments before each snippet or formula for explanation, but maybe they should be removed before the contest. There are explanations on variations, but maybe they aren’t needed either.

Debugging: common mistakes

Graphs may have repeated edges
If you can output the solution with part of the input, make sure to still read all the input.
Make sure to get the newline before calling gets or getline.
Check if you have put new (empty) lines between test cases
Check for spaces after each line of output
Segmentation faults: Check data structure accesses and possible stack overflow

Utilities

Permutations: with sorted array a: do { ... } while(next_permutation(a));
Java: use java.util.Scanner, and in = new Scanner(System.in) for input. in.hasNextInt() and in.nextInt(). Construct java.math.BigInteger with the number in string form. Use System.out for output. Main class is Main.
Printf for double formatting: "%.2lf" forces a double to have two decimals.
Filling a n-dimensional array: fill(&a[0][0], &a[0][0] + sizeof(a)/sizeof(a[0][0]))

Mathematics

GCD

int gcd(int a, int b) {
    if(a < b) return gcd(b, a);
    if(a % b == 0) return b;
    return gcd(b, a%b);
}

Newton’s Method

For finding roots of a continuous derivable function.

$$x_i = x_{i-1} + \frac{f'(x_{i-1})}{f''(x_{i-1})}$$

Ternary search

For finding extrema. Can be used as-is, or nested. Nested is done on every alteration of the evaluation points

while(fabs(a1-a2) > ERR) {
    if(f(a1) < f(a2)) a2 += (a1-a2)/3.;
	else a1 += (a2-a1)/3.;
}

Dynamic programming and Memoization

Maximum subarray sum (Kadane)

We show the 2D version here. the 1D version is the code block separated by a newline. You can keep track of where the sequence starts and ends by messing with the max_here and max assignments respectively. Use > max_here to keep longer subsequences, >= max_here to keep shorter ones. Take into account circular arrays by adding the sum of all elements and the max of the array with sign changed.

max = mat[0][0];
for(i=0; i<N; i++) {
    memset(aux, 0, sizeof(aux));
    for(k=i; k<N; k++) {
        for(j=0; j<N; j++)
            aux[j] += mat[k][j];

        max_here = aux[0];
        if(max_here > max)
            max = max_here;
        for(j=1; j<N; j++) {
            max_here += aux[j];
            if(aux[j] > max_here)
                max_here = aux[j];
            if(max_here > max)
                max = max_here;
        }
    }
}

Edit distance (Damerau-Levenshtein)

m[0][_] = m[_][0] = 0;. m[i][j] is the edit distance of s1[0..i] and s2[0..j]. m[i][j] = min(operations), where operations are: add character, subtract character m[i-1][j] + 1, m[i][j-1] + 1; change character m[i-1][j-1] + (if s1[i] == s2[j] then 1 else 0; swap last two m[i-2][j-2] + (if s1[i-1] == s2[j] && s1[i] == s2[j-1] then 1), else don’t add this option. You may invent more options.

Longest Increasing Subsequence

There are two solutions: one $\Theta(n^2)$ and one $\Theta(n \log n)$. We show them in order.

for(int i=0; i<N; i++) {
    inc[i] = 1;
    for(int j=0; j<N; j++) {
        if(seq[j] < seq[i]) {
            int v = inc[j] + 1;
            if(v > inc[i])
                inc[i] = v;
        }
    }
	if(inc[i] > max)
	    max = inc[i];
}

ind[0] = 0;
ind_sz = 1;
while(scanf("%d", &seq[seq_sz++]) == 1) {
    /*  Add next element if it's bigger than the current last */ 
    int i = seq_sz-1;
    if (seq[ind[ind_sz-1]] < seq[i]) {
        predecessor[i] = ind[ind_sz-1];
        ind[ind_sz++] = i;
        continue;
    }
    /*  bsearch to find element immediately bigger */
    int u = 0, v = ind_sz-1;
    while(u < v) {
        int c = (u + v) / 2;
        if (seq[ind[c]] < seq[i])
            u = c+1;
        else
            v = c;
    }
    /*  Update b if new value is smaller then previously referenced value  */
    if (seq[i] < seq[ind[u]]) {
        if (u > 0)
            predecessor[i] = ind[u-1];
        ind[u] = i;
    }
}

Longest Common Subsequence

table[_][0] = 0;
for(int i=1; i<n+1; i++) {
    table[i][0] = 0;
    for(int j=1; j<n+1; j++) {
        if(x[i-1] == y[j-1])
            table[i][j] = table[i-1][j-1] + 1;
        else
            table[i][j] = max(table[i-1][j], table[i][j-1]);
    }
}

Traveling Salesman Problem

constexpr Cost SENTINEL = -1;
constexpr int MAX_ELEMS = 14;
int n_elems;
Cost tsp_memoize[1 << (MAX_ELEMS+1)][MAX_ELEMS],
  distances[MAX_ELEMS][MAX_ELEMS];
// n_elems, distances do not include the original node if available

#define TSP(subset, i) (tsp_memoize[subset][i] == SENTINEL ? \
  tsp(subset, i) : tsp_memoize[subset][i])

Cost tsp(const Subset subset, const int i) {
	Subset without = subset ^ (1 << i);
	Cost minimum = numeric_limits<Cost>::max();
	for(int j=0; j<n_elems; j++) {
		if(j==i || (without & (1 << j)) == 0)
			continue;
		Cost v = TSP(without, j) + distances[i][j];
		if(v < minimum) minimum = v;
	}
	return tsp_memoize[subset][i] = minimum;
}

fill(&tsp_memoize[0][0], &tsp_memoize[0][0] + \
	sizeof(tsp_memoize) / sizeof(tsp_memoize[0][0]), sentinel);
for(int i=0; i<n_elems; i++)
	tsp_memoize[1<<i][i] = adj_mat[initial_node][elem_i];
if(n_elems > 1)
	for(int i=0; i<n_elems; i++)
		tsp(0xffff >> (16 - n_elems), i);

Computer Geometry

Intersection between two lines: here is the system solved. Swap all $x$s and $y$s to avoid dividing by zero if $p_x = 0$.
$$s = \frac{P_y - Q_y + \frac{p_y}{p_x}(Q_x - P_x)}{q_y - \frac{p_y}{p_x}q_x}$$

$$x = Q_x + q_x s; \; y = Q_y + q_y s $$

$$t = \frac{Q_x - P_x + q_x*s}{p_x}$$

SWERC