L1 Distance

Median

Given n points [{x}] on a line and a non-negative integer s, find an interval p..=(p+s) that minimize the total distance from every points to the interval.

[{ p = "argmin"_p F(p) = "argmin"_p sum_i f(i; p) " where " }] [{ f(i; p) = {(p - x_i, if x_i < p), (0, if p <= x <= p + s), (x_i - (p + s), if x_i > p + s) :} }]

Differentiate [{F(p)}]: [{ d/(dp) F(p) = sum_i d/(dp) f(p; i) = sum_i ({(+1, if x_i < p), (0, if p <= x <= p + s), (-1, if x_i > p + s) :}) }]

[{ F'(p) = 0 }] occurs when the number of [{x_i < p}] equals to the number of [{ x_i > p + s }]. That is, the [{p}] that makes the number of [{p > x_i}] equals to the number of [{ p < x_i - s }]. Which is [{ "median"([x_i] uu [x_i - s]) }].

ABC330F

Total Distance to Sorted Points

Given N points pts on number line and a query point x, find total L1 distance from x to pts. That is, [{ sum_i |pts[i] - x| }].

If the pts are sorted and the prefix sum are already computed, then it can be found in [{O(lg(n))}]. We simply binary search the position of x in pts to get p.

  1. The distance to the points at the left of p is [{ sum_i (x - pts[i]) }].
  2. The distance to the points at the right of p [{ sum_i (pts[i] - x) }].

Therefore by using the prefix sum, we get

fn total_l1_dist_to_sorted(x: i64, sorted: &Vec<i64>, pref: &Vec<i64>) -> i64 {
    let n = sorted.len();
    let p = sorted.partition_point(|xi| *xi <= x);
    let d1 = (p as i64) * x - query(&pref, 0, p);
    let d2 = query(&pref, p, n) - ((n - p) as i64) * x;
    d1 + d2
}

ABC366E

Pairwise L1 Distance

Given a sequence [{A}], find [{ sum_(i < j) |A_i - A_j| }]. Since L1 distance is commutative, we can sort the sequence.

fn f(mut arr: Vec<i64>) -> i64 {
    if arr.len() == 0 {
        return 0;
    }
    arr.sort();
    let mut ans = 0;
    let mut sum = arr[0];
    for i in 1..arr.len() {
        ans += i as i64 * arr[i] - sum;
        sum += arr[i];
    }
    ans
}

Prevent D

Given A[0..N], find the minimum number of element to remove to make A satisfy A[i] - A[j] ≠ D for all i ≠ j.

Observed that A[i] can only put constraints on A[i] - D and A[i] + D, we can split A into multiple chains. Each chain is an arithmetic sequence. For each chain, we can the following problems using dp: Given P[0..M], find the minium total sum if for any adjacent element we must pick at least one. ABC403D

2D Points

Given N points, find the maximum L1 distance between any pair of points.

Map the points from [{(x, y)}] to [{(u, v)}] where [{u = x + y, v = x - y}].

We first find the maximum L1 distance from a specified point [{i}]:

[{ max_(0 <= j < N) |x_i - x_j| + |y_i - y_j| }] [{ = max_j max {x_i - x_j, x_j - x_i} + max{y_i - y_j, y_j - y_i} }] [{ = max_j max { (x_i - x_j + y_i - y_j)"," (x_i - x_j + y_j - y_i), (x_j - x_i + y_i - y_j), (x_j - x_i + y_j - y_i) } }] [{ = max_j max { u_i - u_j, v_i - v_j, v_j - v_i, u_j - u_i } }] [{ = max {max_j ( u_i - u_j), max_j (v_i - v_j), max_j(v_j - v_i), max_j( u_j - u_i ) } }] [{ = max {(max_j u_i - min_j u_j) , (max_j v_i - min_j v_j) , (max_j v_j - min_j v_i) , (max_j u_j - min_j u_i) } }] [{ = max {u_i - u_min , v_i - v_min , v_max - v_i , u_max - u_i } }]

Typical90-036

If we are finding pairwise maximum L1 distance, we simply find the maximum for all [{i}]:

[{ max_(0 <= i < N) max {u_i - u_min , v_i - v_min , v_max - v_i , u_max - u_i } }] [{ = max {max_i (u_i - u_min) , max_i (v_i - v_min) , max_i (v_max - v_i) , max_i (u_max - u_i) } }] [{ = max {(max_i u_i) - u_min , (max_i v_i) - v_min , v_max - (min_i v_i) , u_max - (min_i u_i) } }] [{ = max {u_max - u_min , v_max - v_min , v_max - v_min , u_max - u_min } }] [{ = max {u_max - u_min , v_max - v_min } }]

ABC178E

Given N points, for each point, find the distance to its closest neighboring point.

For a point [{(x, y)}], if we want only the answer to its top-right points:

[{ min_(x_i >= x, y_i >= y) (x_i - x + y_i - y) = (min_(x_i >= x, y_i >= y) (x_i + y_i)) - (x + y)}]

It is similar to the 2D Poset Problem which can be solved using sweep line and SegTree. For top-left, bottom-right and bottom-left, we can simply flip the points (along x-axis or y-axis) and run the algorithm again.

ABC283F

Given N points, find the total distance of all pair of points. Distance is defined as the minimum number of moves: [{(x, y) -> (x + 1, y + 1), (x + 1, y - 1), (x - 1, y + 1), (x - 1, y - 1)}]

Map the points from [{(x, y)}] to [{(u, v)}] where [{u = x + y, v = x - y}]. A move in [{(x, y)}] is [{2}] unit of distance in [{(u, v)}] and [{u, v}] is independent of each other. This indicates that we can classify points into 2 groups via parity. For each group, the problem reduce to a pairwise L1 distance problem.

ABC351E

Given N points, find the number of lattice points [{ (x, y) }] in 2D plane ([{ |x| <= 10^6, |y| <= 10^6 }]) that satisfies [{ sum_i (|x - x_i| + |y - y_i|) <= D }].

By inspecting all the possible values of x, we transform the problem to a 1D version: Given the points pts in number line, find the number of integer x such that

sum([abs(x - pts[i]) for i in 0..n]) <= bound

The total distance function is a U-shaped (concave) function with minimum at the median of the points. We want to find range the function has value <= bound. It can be solved by binary searching the left border and the right border.

ABC366E