SWERC notebook: Not Paranoid Enough

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, &a + sizeof(a)/sizeof(a))

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})}$$

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

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;
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;
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[_] = m[_] = 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;
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;
for(int i=1; i<n+1; i++) {
table[i] = 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, &tsp_memoize + \
sizeof(tsp_memoize) / sizeof(tsp_memoize), sentinel);
for(int i=0; i<n_elems; 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}$$ 