King's Summit

 problem

observations

There are n points: x₁=(r₁,c₁), x₂=(r₂,c₂),...,x_n=(r_n,c_n). The time it takes to get from point a=(r_a,c_a) to point b=(r_b,c_b) is the chebyshev distance between a and b: ||a-b||_inf. This is length of the shortest "king-walk" between a and b on a chess-board. Thus, if all the persons meet at "summit" point s=(r_s,c_s), then it will take max(||s-x₁||_inf, ||s-x₂||_inf, ..., ||s-x_n||_inf) time, i.e. the longest time to reach the summit across all persons equals the total time it takes everyone to reach the summit. 

The chebyshev distance between points a and b is the L_inf norm of the difference between a and b. The L_inf norm selects the maximum component: ||a-b||_inf=max(|r_a-r_b|,|c_a-c_b|). Additionally, |p| = max(-p, p). Hence, the L_inf norm of ||a-b||_inf = max(|r_a-r_b|,|c_a-c_b|) = max(r_a-r_b, r_b-r_a, c_a-c_b, c_b-c_a).

This leads to a big max expression:

time to reach summit becomes

= max(||s-x₁||_inf, ||s-x₂||_inf, ..., ||s-x_n||_inf)

= max(rs - rx1, rx1 - rs, cs - cx1, cx1 - cs,

           rs - rx2, rx2 - rs, cs - cx2, cx2 - cs,

           ...

           rs - rxn, rxn - rs, cs - cxn, cxn - cs)

Assume that the components of persons' starting positions are ordered:

rsmallest ≤ rsecond_smallest ≤ ... ≤ rbiggest

csmallest ≤ csecond_smallest ≤ ... ≤ cbiggest

Then, rs - rsmallest ≥ rs - rx2 ≥ ...rs - rbiggest. Exploiting this structure for the other maximum arguments, leads to this expression for the maximum time to summit:

= max(rs - rsmallest, rbiggest - rs, cs - csmallest, cbiggest - cs).

And, the minimum of this expression in terms of s=(rs,cs) is max( ceil((rbiggest - rsmallest) / 2), ceil((cbiggest - csmallest) / 2).

solution

Codeforces union find problem involving cycles

 Codeforces Round 1040 (Div. 2) Problem C

Observations

Given n ranges, the problem involves maximally covering the range [1, 2n] with those ranges, while jointly minimizing cycles between the endpoints of those ranges/ undirected edges. [1, 2n] will be maximally covered by taking all ranges, but this does not necessarily avoid cycles. The important observation is that all cycles have a minimum and maximum point, e.g. 1 and 4 in S = {(1, 2), (2, 4), (1, 4)}. There are always two "paths" to get from the minimum to the maximum. In the case of S, {(1, 2), (2, 4)} or {(1, 4)}. Getting from the minimum to the maximum while avoiding a cycle is then just a matter of take one path and only one path.

Solution

 Take ranges/ undirected edges greedily. Only take an edge (a, b) if b is not currently reachable from a, i.e. the other "path" has not already been taken

Newton's method and the Jacobi method similarity part 1

Solve f(x) = 0. f is once differentiable.

1. f(x) = 0

2. f(x) + Jf(x)(x - x) = 0

Jf(x) is the jacobian of f evaluated at x.

3. f(x_t) + Jf(x_t)(x_t+1 - x_t) = 0

4. Jf(x_t)(x_t+1 - x_t) = -f(x_t)

Finding the step (x_t+1 - x_t) involves solving the system of linear equations Jf(x_t)(x_t+1 - x_t) = -f(x_t). This iterative scheme for solving nonlinear systems of equations is Newton's method. 

The Jacobi method is also an iterative method, but its for solving diagonally dominant systems of linear equations.

Solve Ax = b. A is diagonally dominant.

1. Ax = b

2. (D + L + U)x = b

D is the diagonal of A. L is the lower triangular portion of A. U is the upper triangular portion of A.

3. Dx_t+1 = b - Lx_t - Ux_t

4. x_t+1 = D^-1(b - (L+U)x_t)

Notice the similarity between steps two and three in the derivation of Jacobi's method and Newton's method. Step two exploits an expansion/ decomposition, and then a "leap" is made to go from a system of variable(s) x to a system of x_t+1 and x_t.

But surely, one can't just use any decomposition they'd like. The iterative method has to be consistent and convergent.

In the next post, I will prove that this is the case for both methods, and then go back to these derivations to recover the train of thought that lead to performing step two and three in the first place. This will allow me to contrive whatever iterative methods, I would like. This is very important, because many systems of equations and optimization programs exhibit lots of structure that can be exploited.

Distinct Values Subsequences

problem

observations

The number of non-empty subsequences of an array of length n is 2ⁿ - 1. If each number in the array appears once, then this is the answer.

The order of the numbers in the array does not affect the count, just the number frequencies.

Why is observation one true: each number can either appear or not appear, and the empty set is not counted, so (1 + 1)...(1 + 1) - 1 = 2ⁿ - 1. Each number contributes a term of (1 + 1): the first one is absence, while the second one is incidence.

But what if a number occurs more than once? A subsequence can either not have a number or have just one instance of it. That "choice" is easily expressed as a trivial combination: (frequency of number choose 1) = frequency of number. The expression for the general answer is (1 + frequency of first number)(1 + frequency of second number)...(1 + frequency of last number) - 1.

You could feasibly compute this expression directly mod 1e⁹+7, but there is a cooler incremental, indirect computation.

solution

#include<iostream>

#include<unordered_map>

using namespace std;

long long binpow(long long a, long long b, long long m) {

    a %= m;

    long long res = 1;

    while (b > 0) {

        if (b & 1)

            res = res * a % m;

        a = a * a % m;

        b >>= 1;

    }

    return res;

}

int main() {

        const long long MOD = 1000000007;

        int n;

        cin >> n;

        unordered_map<int, int> freq;

        long long count = 1;

        for (int i = 0;i < n;++i) {

                int x; 

                cin >> x;

                count = count + (count * binpow(freq[x] + 1, MOD - 2, MOD) % MOD) % MOD;

                ++freq[x];

        }

        count = count - 1 % MOD;

        cout << count << endl;

}

Distinct Values Subarrays

problem

observations

1. The number of subarrays of an array of length n is n(n + 1)/2. If each number in the array appears once, then this is the answer.

2. What if you find a covering of the array into disjoint segments each with distinct numbers, e.g. [1, 2, 3, 1] becomes [1, 2, 3], [1]. Can you apply the formula independently to the segments and sum the results? No, this fails to count segments that cross the split and would underestimate the correct answer. Also, such a covering might not be unique.

3. What if you forego disjoint-ness and expand the segments as much as possible while keeping the numbers distinct: [1, 2, 3, 1] becomes [1, 2, 3], [2, 3, 1]. This covering is unique, but now you overestimate the correct answer because the segments overlap. , that the amount of overshoot is equal to the number of subarrays of [2, 3]. A nice expression for the correct number of subarrays follows from this observation resembling the inclusion-exclusion principle formula.

4. If x₁, ..., x_k are distinct, but x₁, ..., x_k, x_k+1 are not distinct, then one of the numbers in x₁, ..., x_k is x_k+1. If x_j = x_k+1 with 1 ≤ j ≤ k, then x_j+1, ..., x_k+1 is distinct. This means that storing the index of incidence for each number in x₁, ..., x_k is enough to find out the start of the second segment in the construction from observation three.

solution

You can compute the expression from observation three in a sliding window fashion by exploiting the structure from observation four.

two problems

Codeforces Round 1011 (Div. 2) Problem C

Solution: x + y = x xor y as long as the addition involves no carries, i.e. the bits that are set in a should be disjoint from the ones in b. Multiples of powers of two are always disjoint from numbers less than that power of two. if x ≠ y, then without loss of generality, one of x and y will be bigger than the other, so choose the k that makes the the bigger one a power of two. If the numbers x and y given are equal to each other, then (x + k) + (y + k) ≠ (x + k) xor (y + k) for all non-negative numbers k (unless x = y = 0).

Building Roads

Solution: This is basically just a connected components problem. Once you identify the connected components, connect them minimally with # components - 1 edges: connect one vertex in each connected component to one vertex in a single chosen component of your choice. Here's my union find solution. You could also identify and connect the components using a depth first search and no union find structure, but then you need to store the adjacency matrix.