# 33 and Least Common Ancestor (LCA) Problem

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 {
public:
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;
(*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])
++j;
return LeastCommonAncestor(ancestors, depth, ancestors[u][j],
ancestors[v][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.
for (const auto& edge : edges) {
}
std::vector<int> depths(n, 0);
std::vector<int> parents(n, -1);
std::vector<int> xors = nums;
// ancestors[i][j] is the 2^j ancestor of node i.
std::vector<std::vector<int>> ancestors;
ancestors.reserve(n);
for (int i = 0; i < n; ++i) ancestors.push_back({parents[i]});
BuildAncestors(&ancestors);
// 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;
}
``````

# Fitness Goals of 2016

One of the better parts about working for Google is the office gym and the community and camaraderie of working out and striving towards fitness goals together with your coworkers. This past year, we had the GFit games. The friendly competition gave me the boost I needed to finally hit two longstanding goals of mine, to deadlift 4 plates (405 pounds) and squat 3 plates (315 pounds). In competition, I was able to hit exactly 405 pounds for the deadlift, and I smashed my goal for the squat with 345 pounds. Yay!

People often wonder why I lift. It's certainly not for the girls given my dating life. Despite my love of problem solving that I discussed in my previous article, there is something deeply unsatisfying about urban intellectual work. I'm apparently not alone in this. I recently read this wonderful article about French people leaving the city to farm, Life on the Farm Draws Some French Tired of Urban Rat Race. I often wonder how software engineering became such a male-dominated field because pressing buttons all day on a keyboard makes nursing look like the epitomy of masculinity since they do much more hard labor that we do.

I suppose that through some defect of evolution, there's some primitive vestige left in my brain from our caveman days that associates work with physical labor. I guess a lot of people are of the same mind given the strong grip that manufacturing industries have on the American pysche as shown in this past election cycle. For this reason, when I go to work in the morning, my first stop is the gym. It seems dumb and brutish of me, but I find a lot of satisfaction in picking heavy things up and putting them back down.

There is something spiritually fulfilling about working towards fitness goals, too. As I've gotten stronger and tested my limits, I've gained a new found appreciation for creation. Conquering fear to do a backflip was exhilirating. Working on my balance to do handstand pushups often helps me relax and focus. I can't really get on board with the fitness industry about how being in great shape will radically transform your life. No, despite my abs, girls do not flock to me. However, I do find a lot of joy in pushing myself physically. Hopefully, 2017 will be another great year.

Back in 2011, I started eating Paleo, and briefly became famous with my story Quitting Rice. While I was pretty hardcore at first, I've been more 80/20, now. Perhaps, the first thing you'll notice is that I've hardly any made any gains in 5 years ☹. Such is the sad life of a natty lifter. I'm actually significantly stronger, but it doesn't show. I'm actually about 15 lbs heavier in that July 2016 picture.

Now, on the plus side, I have achieved long-term weight loss. According to this article from the The American Journal of Clinical Nutrition, only about 20% of people that lose weight keep it off. It's not clear whether that's because the diets stop working, or people can't adhere to them long-term. Despite significant life changes, I've found this diet rather easy to maintain, however.

May 2013: doing some yard work

Since I've started Paleo, I've had 3 different jobs, earned a graduate degree, and lived in 3 different cities: Boston, Philadelphia, and Seattle. I've taken plenty of vacations, which include Vietnam, Thailand, and Australia. Even when I barely lifted one year, I managed to stay lean.

2014: at a beach in Australia

Thus, in my \$N = 1\$ experiment, I've decided that Paleo works long-term. Cooking is not so hard, and I find that I can pretty much each as much as I want and not even think about it. Despite availing myself of Google's limitless food, I haven't really gained weight, here, in Seattle.

Of course, there's the other problem of eating all that cholesterol and saturated fat. It would seem that I've headed towards coronary heart disease. And depending on how you interpret my lipid panel, you may be right.

From August 2016

While my triglycerides and HDL are great, that red LDL certainly doesn't look good. I'm not a doctor, so I don't really know what to make of it. There are some studies saying that LDL number may not even be correct because my triglycerides are so low (see: The impact of low serum triglyceride on LDL-cholesterol estimation). It's strange that eating lots of trigylcerides leads to very low trigylcerides. I probably get 60% of my calories from fat, with most of that fat being saturated.

Moreover, in Comparison of serum lipid values in patients with coronary artery disease at 70 years of age, they say that:

Triglycerides and ratio of triglycerides to HDL cholesterol were the most powerful, independent variables related to precocity of CAD.

According to their model, my risk of coronary artery disease should be very low, so who knows? Is it not common knowledge that lots of LDL is bad?

I guess my insulin levels are fine, too? Blood pressure was 110/72 for what it's worth.

Anyway, if you've never given Paleo a try. I highly recommend it. Besides the weight loss, there are plenty of other benefits like not being hungry as often and more stable energy levels. I'm not a medical professional or dietician, but I'd be happy to answer any questions about the lifestyle. Looking at all these pictures of myself, I've realized that the light plays cruel tricks on the eye.