Photo URL is broken

I finally did it! The one-armed pull up. There's a bit of a kip, but I'll take it.

Despite my best years being behind me, it's still good to see progress. I have somewhat dispensed with the fake humility. As I find myself getting older, I appreciate clarity and directness more and being honest with myself. I am proud of this whether anyone else cares or not, so I am going to share it. Now, if I could only actually climb.

A lot of taking myself less seriously comes from the daily humiliations brought about by life as 30-something bachelor in NYC. Being stood up and ghosted is just par for the week now. But I am learning to understand that some people just need space to deal with their problems, and some people are just terrible, too.

Another area where I've grown in is how I write code. In Minimum Spanning Trees and the Least Common Ancestor Problem, I described a binary lifting algorithm to find the least common ancestor. I tried way too hard to impress and now I can't figure out what I wrote.

I recently needed this algorithm again in 2322. Minimum Score After Removals on a Tree . If I had a simple implementation that I could understand and reuse, I may have been able to solve it during the contest, so now, I rewrote it.

#include <algorithm>
#include <limits>
#include <vector>

class Solution {
  int minimumScore(const std::vector<int>& nums,
                   const std::vector<std::vector<int>>& edges);

namespace {

void RootTree(const std::vector<std::vector<int>>& adjacency_list, int root,
              std::vector<int>* depths, std::vector<int>* parents,
              std::vector<int>* xors) {
  for (auto child : adjacency_list[root]) {
    if (child == (*parents)[root]) continue;
    (*depths)[child] = (*depths)[root] + 1;
    (*parents)[child] = root;
    RootTree(adjacency_list, child, depths, parents, xors);
    (*xors)[root] ^= (*xors)[child];

void BuildAncestors(std::vector<std::vector<int>>* ancestors) {
  bool built = true;
  for (auto& as : *ancestors) {
    const int a = as.back();
    if (a == -1) continue;
    const int j = as.size() - 1;
    as.push_back(j < (*ancestors)[a].size() ? (*ancestors)[a][j] : -1);
    built = false;
  if (!built) BuildAncestors(ancestors);

int LeastCommonAncestor(const std::vector<std::vector<int>>& ancestors,
                        const std::vector<int>& depth, int u, int v) {
  if (u == v) return u;
  int delta = depth[v] - depth[u];
  if (delta == 0) {
    int j = 0;
    while (ancestors[u][j + 1] != -1 &&
           ancestors[u][j + 1] != ancestors[v][j + 1])
    return LeastCommonAncestor(ancestors, depth, ancestors[u][j],
  if (delta < 0) {
    std::swap(u, v);
    delta = -delta;
  int j = 0;
  while (1 << (j + 1) <= delta) ++j;
  return LeastCommonAncestor(ancestors, depth, u, ancestors[v][j]);

}  // namespace

int Solution::minimumScore(const std::vector<int>& nums,
                           const std::vector<std::vector<int>>& edges) {
  const int n = nums.size();
  // Root the tree at 0 and compute properties based on that.
  std::vector<std::vector<int>> adjacency_list(n);
  for (const auto& edge : edges) {
  std::vector<int> depths(n, 0);
  std::vector<int> parents(n, -1);
  std::vector<int> xors = nums;
  RootTree(adjacency_list, 0, &depths, &parents, &xors);
  // ancestors[i][j] is the 2^j ancestor of node i.
  std::vector<std::vector<int>> ancestors;
  for (int i = 0; i < n; ++i) ancestors.push_back({parents[i]});
  // Determine minimum score by looping over all pairs of edges.
  int min_score = std::numeric_limits<int>::max();
  for (int i = 1; i < n - 1; ++i) {
    for (int j = i + 1; j < n; ++j) {
      const int u = depths[i] <= depths[j] ? i : j;
      const int v = depths[i] <= depths[j] ? j : i;
      const int ancestor = LeastCommonAncestor(ancestors, depths, u, v);
      const int xor0 =
          ancestor == u ? xors[0] ^ xors[u] : xors[0] ^ xors[u] ^ xors[v];
      const int xor1 = ancestor == u ? xors[u] ^ xors[v] : xors[u];
      const int xor2 = xors[v];
      min_score = std::min(min_score, std::max(xor0, std::max(xor1, xor2)) -
                                          std::min(xor0, std::min(xor1, xor2)));
  return min_score;

New Comment


No comments have been posted yet. You can be the first!