About Me
Posts tagged life
I haven't really been writing much since I left grad school, but I figured it would be a shame not to capture this year, even if all I can muster is a brain dump and bulleted lists. It was my first year in NYC after all.
The biggest challenge for me has been finding my voice and asserting myself. The sheer number of people and small amount of space turns everything into a competition here. Upon moving here, I moused about always feeling like I was in everyone's way, but I am slowly learning to exercise my right to take up space. Everyone's attention is being pulled in different directions. Another challenge was having enough self-esteem to handled being constantly ghosted 👻 and not taking it personally.
Algorithms
I am ending the year with my Leetcode rating at 2164. Apparently that makes me top 1.25%. I've been aiming for 2300+, but I admittedly don't work too hard at this. I try my luck at a competition maybe once per week. Let me dump some new algorithms I wrote if I need to reuse them later.
Segment Tree
See 2407. Longest Increasing Subsequence II.
#include <algorithm>
#include <memory>
#include <utility>
#include <vector>
class Solution {
public:
int lengthOfLIS(const std::vector<int>& nums, int k);
};
namespace {
template <typename T>
struct Max {
constexpr T operator()(const T& a, const T& b) const {
return std::max(a, b);
}
};
template <typename K, typename V, typename Reducer = Max<V>>
class SegmentTree {
public:
// Disable default constructor.
SegmentTree() = delete;
// Disable copy (and move) semantics.
SegmentTree(const SegmentTree&) = delete;
SegmentTree<K, V, Reducer>& operator=(const SegmentTree&) = delete;
const std::pair<K, K>& segment() const { return segment_; }
const V& value() const { return value_; }
const SegmentTree<K, V, Reducer>& left() const { return *left_; }
const SegmentTree<K, V, Reducer>& right() const { return *right_; }
void Update(K key, V value) {
if (key < segment_.first || segment_.second < key) return;
if (segment_.first == segment_.second) {
value_ = value;
return;
}
left_->Update(key, value);
right_->Update(key, value);
value_ = reducer_(left_->value(), right_->value());
}
V Query(const std::pair<K, K>& segment, V out_of_range_value) {
if (segment.second < segment_.first || segment.first > segment_.second)
return out_of_range_value;
if (segment.first <= segment_.first && segment_.second <= segment.second) {
return value();
}
if (segment.second <= left_->segment().second)
return left_->Query(segment, out_of_range_value);
if (right_->segment().first <= segment.first)
return right_->Query(segment, out_of_range_value);
return reducer_(left_->Query(segment, out_of_range_value),
right_->Query(segment, out_of_range_value));
}
// Makes a segment tree from a range with `value` for leaf nodes.
template <typename It>
static std::unique_ptr<SegmentTree<K, V, Reducer>> Make(It begin, It end,
V value) {
std::pair<int, int> segment{*begin, *end};
if (begin == end)
return std::unique_ptr<SegmentTree<K, V, Reducer>>(
new SegmentTree<K, V, Reducer>(segment, value));
const auto mid = begin + (end - begin) / 2;
std::unique_ptr<SegmentTree<K, V, Reducer>> left =
SegmentTree<K, V, Reducer>::Make(begin, mid, value);
std::unique_ptr<SegmentTree<K, V, Reducer>> right =
SegmentTree<K, V, Reducer>::Make(std::next(mid), end, value);
return std::unique_ptr<SegmentTree<K, V, Reducer>>(
new SegmentTree<K, V, Reducer>(segment, std::move(left),
std::move(right)));
}
private:
// Leaf node.
SegmentTree(std::pair<K, K> segment, V value)
: segment_(segment), value_(value) {}
// Internal node.
SegmentTree(std::pair<K, K> segment,
std::unique_ptr<SegmentTree<K, V, Reducer>> left,
std::unique_ptr<SegmentTree<K, V, Reducer>> right)
: segment_(segment),
left_(std::move(left)),
right_(std::move(right)),
value_(reducer_(left_->value(), right_->value())) {}
const std::pair<K, K> segment_;
const std::unique_ptr<SegmentTree<K, V, Reducer>> left_;
const std::unique_ptr<SegmentTree<K, V, Reducer>> right_;
const Reducer reducer_;
V value_;
};
} // namespace
int Solution::lengthOfLIS(const std::vector<int>& nums, int k) {
std::vector<int> sorted_nums = nums;
std::sort(sorted_nums.begin(), sorted_nums.end());
sorted_nums.erase(std::unique(sorted_nums.begin(), sorted_nums.end()),
sorted_nums.end());
const std::unique_ptr<SegmentTree<int, int>> tree =
SegmentTree<int, int>::Make(sorted_nums.begin(), --sorted_nums.end(), 0);
for (int x : nums)
tree->Update(x, tree->Query(std::make_pair(x - k, x - 1), 0) + 1);
return tree->value();
}
Disjoint Set Forest
See 2421. Number of Good Paths.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <memory>
#include <numeric>
#include <unordered_map>
#include <vector>
class Solution {
public:
int numberOfGoodPaths(const std::vector<int>& vals,
const std::vector<std::vector<int>>& edges);
};
namespace phillypham {
class DisjointSetForest {
public:
explicit DisjointSetForest(size_t size) : parent_(size), rank_(size, 0) {
std::iota(parent_.begin(), parent_.end(), 0);
}
void Union(size_t x, size_t y) {
auto i = Find(x);
auto j = Find(y);
if (i == j) return;
if (rank_[i] > rank_[j]) {
parent_[j] = i;
} else {
parent_[i] = j;
if (rank_[i] == rank_[j]) rank_[j] = rank_[j] + 1;
}
}
size_t Find(size_t x) {
while (parent_[x] != x) {
auto parent = parent_[x];
parent_[x] = parent_[parent];
x = parent;
}
return x;
}
size_t size() const { return parent_.size(); }
private:
std::vector<size_t> parent_;
std::vector<size_t> rank_;
};
} // namespace phillypham
int Solution::numberOfGoodPaths(const std::vector<int>& vals,
const std::vector<std::vector<int>>& edges) {
const int n = vals.size();
std::vector<int> ordered_nodes(n);
std::iota(ordered_nodes.begin(), ordered_nodes.end(), 0);
std::sort(ordered_nodes.begin(), ordered_nodes.end(),
[&vals](int i, int j) -> bool { return vals[i] < vals[j]; });
std::vector<std::vector<int>> adjacency_list(n);
for (const auto& edge : edges)
if (vals[edge[0]] < vals[edge[1]])
adjacency_list[edge[1]].push_back(edge[0]);
else
adjacency_list[edge[0]].push_back(edge[1]);
phillypham::DisjointSetForest disjoint_set_forest(n);
int num_good_paths = 0;
for (int i = 0; i < n;) {
const int value = vals[ordered_nodes[i]];
int j = i;
for (; j < n && vals[ordered_nodes[j]] == value; ++j)
for (int k : adjacency_list[ordered_nodes[j]])
disjoint_set_forest.Union(ordered_nodes[j], k);
std::unordered_map<int, int> component_sizes;
for (int k = i; k < j; ++k)
++component_sizes[disjoint_set_forest.Find(ordered_nodes[k])];
for (const auto& [_, size] : component_sizes)
num_good_paths += size * (size + 1) / 2;
i = j;
}
return num_good_paths;
}
Books
I managed to read 12 books this year. Not too bad. Unfortunately, I didn't manage to capture what I took away in the moment, so I will try to dump it here with a few sentences for each book.
Sex and Vanity by Kevin Kwan
This was a fun novel in the Crazy Rich Asians universe. It's like a modern day society novel with social media. In classic Kevin Kwan style, it's filled with over-the-top descriptions of wealth. While mostly light-hearted and silly, the protagonist grapples with an identity crisis familiar to many Asian Americans.
Yolk by Mary H. K. Choi
This novel centers on two Korean-American sisters coming of age in NYC. They are foils: one went to Columbia and works at a hedge fund and the other studies art and dates losers. Both sisters are rather flawed and unlikeable and antiheroes in some sense. The description of the eating disorder is especially disturbing. Probably the most memorable quote for me was this gem:
Because I'm not built for this. I tried it. I did all that Tinder shit. Raya. Bumble. Whatever the fuck, Hinge. I thought maybe it was a good idea. I've had a girlfriend from the time I was fifteen. It's like in high school, Asian dudes were one thing, but a decade later it's like suddenly we're all hot. It was ridiculous. I felt like such a trope, like one of those tech bros who gets allcut up and gets Lasik and acts like a totally different person.
I've never been so accurately dragged in my life. Actually, who I am kidding, I was never hot enough to be having sex with strangers on dating apps.
House of Sticks by Ly Tran
As a child of Vietnamese war refugees, I thought this would be more relatable. It really wasn't at all, but it was still very good. Ly's family came over in different circumstances than mine and her parents never had the opportunity to get an education. I appreciated the different perspective of her life in Queens versus my Pennsylvania suburb. The complex relationship with her father who clearly suffers from PTSD and never really adjusts to life in America is most interesting. He wants to be a strong patriarchical figure for his family, but ultimately, he ends up alienating and hurting his daughter.
The Sympathizer by Viet Thanh Nguyen
I really enjoyed this piece of historical fiction. I have only really ever learned about the Vietnam war from the American perspective which has either been that it was necessary to stem communism or that it was a tragic mistake that killed millions of Vietnamese. But the narrator remarks:
Now that we are the powerful, we don’t need the French or the Americans to fuck us over. We can fuck ourselves just fine.
His experience of moving to America as an adult is also interesting. I was born here and the primary emotions about Vietnamese for me were shame and embarassement. The narrator arrives as an adult and while he has moments of shame and embarassement, he lets himself feel righteous anger.
I felt the ending and the focus on the idea of nothing captures how powerful and yet empty the ideals of communism and the war are.
The Committed by Viet Thanh Nguyen
The sequel to The Sympathizer takes place in France. I don't know if this novel really touches on any new themes. There is the contrast between the Asians and Arabs? But it is very funny, thrilling, and suspenseful as the narrator has to deal with consequences of his lies. Who doesn't enjoy poking fun at the hypocrisy of the French, too?
A Gentleman in Moscow by Amor Towles
This story is seemingly mundane as it takes place almost entirely in the confines of a hotel. But the Count's humor and descriptions of the dining experiences make this novel great fun. The Count teams up with loveable friends like his lover Anna and the barber to undermine the Bishop and the Party. I enjoyed the history lesson of this tumultuous period in Russia, too.
Being somewhat a student of the Russian greats like Tolstoy and Dostoevsky, I appreciated that he would occasionally make references to that body of work.
...the Russian masters could not compute up with a better plot device than two central characters resolving a matter of conscience by means of pistols at thirty-two paces...
Rules of Civility by Amor Towles
I've always enjoyed fiction from this era via Fitzgerald, Hemingway, and Edith Wharton. The modern take on the American society novel is refreshing. Old New York City and the old courtship rituals never fail to capture my imagination. There seems to be a lot to say about a women's place in society when marrying rich was the only option. The men seem to be yearning for a higher purpose than preserving dynastic wealth, too.
The Lincoln Highway by Amor Towles
A really charming coming of age story, where the imagination of teenage boys is brought to its logical conclusion. There is some story about redemption for past mistakes here. The headstrong Sally who has disgressions about doing thing the hard way and her supposed duty to make herself fit for marriage might be my favorite character, and I wish more was done with her. Abacus Abernathe lectures on the magic of New York City (it's just the right size) and deems this adventure worthy of the legends of the old world like Achilles.
I couldn't help but be touched and feeling like I am in on the joke with references to Chelsea Market (where I work) and characters in his previous novels.
Dune by Frank Herbert
I read this one because of the movie, but I didn't really enjoy it. Science fiction has never been of favorite of mine. I didn't like the messiah narrative and found Paul to be arrogant and unlikeable. But maybe that's the reality of playing politics.
The Left Hand of Darkness by Ursula K. Le Guin
This one was an interesting thought experiment about what would the world be like if we didn't have a concept of sex and gender. It makes you think how we immediately classify everyone we meet into a gender. The protagonist struggles with his need to feel masculine in a population with no concept of masculinity.
Bluebeard by Kurt Vonnegut
Rabo is a cranky old man. I wasn't able to identify any larger themes, but it's funny and Rabo's journey to make a meaningful work of art with soul is interesting itself. Abstract art is just too easy an target with its ridiculousness.
Maybe one useful tidbit is that motivation to write can be found by having an audience.
Travel
Somehow, I traveled to countries with breakout World Cup teams.
Croatia
Honestly, I don't know if I could have found Croatia on the map before I went there. It was surprisingly awesome. A beautiful country with great food. The people were proud and enjoyed opening up and sharing their country with us. I'll be back here to climb sometime, I hope.
Congratulations to them for their World Cup performance and adopting the euro.
Morocco
I don't know if I really enjoyed this one. There didn't seem to be much to do beyond shopping at the markets and seeing the historical sights. I liked the food, but I wasn't crazy about it.
Washington
The Enchantments were just breathtaking. The hike took us over 14 hours. Late in the night, I did begin to wonder if were going to make it, though, but it was worth it.
I also did my first multipitch (3 pitches!), here. Thanks Kyle for leading!
I'll wake you up with some breakfast in bed
I'll bring you coffee
With a kiss on your head
- Excerpt from "Say You Won't Let Go" orginally by James Arthur
After a few attempts, I created a Croque Madame that I'm quite happy with. I improved on Croque-Madame by replacing the ham with slices of thinly cut pork belly that I cooked on a skillet. I, then, used all that pork fat to cook my eggs. For those that prefer exact recipies, I also used sourdough bread, 3/8 tsp salt, and 1/8 tsp of ground nutmeg.
Also, I think the blog might give people the false idea that I'm pretty much good at everything. It's time to pull back the facade of perfection that social media projects. After many hours of practice on the guitar, I mustered this effort of singing "Say You Won't Let Go". Here's an excerpt. I hope you enjoy my embarassing myself.
One of the coolest benefits of working for Google is we have guitars lying around the office for impromptu jam sessions. This was filmed in the Seattle office, with a Google guitar, and a Google laptop. Now, I'm done being a shill for Google.
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.
Happy New Year, everyone! Let me tell you about the epic New Year's Eve that I had. I got into a fight with the last problem from the December 2016 USA Computing Olympiad contest. I struggled mightily, felt beaten down at times, lost all hope, but I finally overcame. It was a marathon. We started sparring around noon, and I did not vanquish my foe until the final hour of 2017.
Having a long weekend in a strange new city, I've had to get creative with things to do. I decided to tackle some olympiad problems. For those who are not familiar with the competitive math or programming scene, the USAMO and USACO are math and programming contests targeted towards high school students.
So, as an old man, what am I doing whittling away precious hours tackling these problems? I wish that I could say that I was reliving my glory days from high school. But truth be told, I've always been a lackluster student, who did the minimal effort necessary. I can't recall ever having written a single line of code in high school, and I maybe solved 2 or 3 AIME problems (10 years later, I can usually do the first 10 with some consistency, the rest are a toss-up). Of course, I never trained for the competitions, so who knows if I could have potentially have done well.
We all have regrets from our youth. For me, I have all the familiar ones: mistreating people, lost friends, not having the best relationship with my parents, losing tennis matches, quitting the violin, and of course, the one girl that got away. However, what I really regret the most was not having pursued math and computer science earlier. I'm not sure why. Even now, 10 years older, it's quite clear that I am not talented enough to have competed in the IMO or IOI: I couldn't really hack it as a mathematician, and you can scroll to the very bottom to see my score of 33.
Despite the lack of talent, I just really love problem solving. In many ways it's become an escape for me when I feel lonely and can't make sense of the world. I can get lost in my own abstract world and forget about my physical needs like sleep or food. On solving a problem, I wake up from my stupor, realize that the world has left me behind, and find everyone suddenly married with kids.
There is such triumph in solving a hard problem. Of course, there are times of struggle and hopelessness. Such is my fledging sense of self-worth that it depends on my ability to solve abstract problems that have no basis in reality. Thus, I want to write up my solution to Robotic Cow Herd and 2013 USAMO Problem 2
Robotic Cow Herd
In the Platinum Division December 2016 contest, there were 3 problems. In contest, I was completely stuck on Lots of Triangles and never had a chance to look at the other 2 problems. This past Friday, I did Team Building in my own time. It took me maybe 3 hours, so I suspect if I started with that problem instead, I could have gotten a decent amount of points on the board.
Yesterday, I attempted Robotic Cow Herd. I was actually able to solve this problem on my own, but I worked on it on and off over a period of 12 hours, so I definitely wouldn't have scored anything in this case.
My solution is quite different than the given solution, which uses binary search. I did actually consider such a solution, but only gave it 5 minutes of though before abandoning it, far too little time to work out the details. Instead, my solution is quite similar to the one that they describe using priority queue before saying such a solution wouldn't be feasible. However, if we are careful about how we fill our queue it can work.
We are charged with assembling $K$ different cows that consist of $N$ components, where each component will have $M$ different types. Each type of component has an associated cost, and cow $A$ is different than cow $B$ if at least one of the components is of a different type.
Of course, we aren't going to try all $M^N$ different cows. It's clear right away that we can take greedy approach, start with the cheapest cow, and get the next cheapest cow by varying a single component. Since each new cow that we make is based on a previous cow, it's only necessary to store the deltas rather than all $N$ components. Naturally, this gives way to a tree representation shown in the title picture.
Each node is a cow prototype. We start with the cheapest cow as the root, and each child consists of a single delta. The cost of a cow can be had by summing the deltas from the root to the node. Now every prototype gives way to $N$ new possible prototypes. $NK$ is just too much to fit in a priority queue. Hence, the official solution says this approach isn't feasible.
However, if we sort our components in the proper order, we know the next two cheapest cows based off this prototype. Moreover, we have to handle a special case, where instead of a cow just generating children, it also generates a sibling. We sort by increasing deltas. In the given sample data, our base cost is $4$, and our delta matrix (not a true matrix) looks like $$ \begin{pmatrix} 1 & 0 \\ 2 & 1 & 2 & 2\\ 2 & 2 & 5 \end{pmatrix}. $$
Also, we add our microcontrollers in increasing order to avoid double counting. Now, if we have just added microcontroller $(i,j)$, the cheapest thing to do is to change it to $(i + 1, 0)$ or $(i, j + 1)$. But what about the case, where we want to skip $(i+1,0)$ and add $(i + 2, 0), (i+3,0),\ldots$? Since we're lazy about pushing into our priority queue and only add one child at a time, when a child is removed, we add its sibling in this special case where $j = 0$.
Parent-child relationships are marked with solid lines. Creation of a node is marked with a red arrow. Nodes still in the queue are blue. The number before the colon denotes the rank of the cow. In this case, the cost for 10 cows is $$4 + 5 + 5 + 6 + 6 + 7 + 7 + 7 + 7 + 7 = 61.$$
Dashed lines represent the special case of creating a sibling. The tuple $(1,-,0)$ means we used microcontrollers $(0,1)$ and $(2,0)$. For component $1$, we decided to just use cheapest one. Here's the code.
import java.io.*;
import java.util.*;
public class roboherd {
/**
* Microcontrollers are stored in a matrix-like structure with rows and columns.
* Use row-first ordering.
*/
private static class Position implements Comparable<Position> {
private int row;
private int column;
public Position(int row, int column) {
this.row = row; this.column = column;
}
public int getRow() { return this.row; }
public int getColumn() { return this.column; }
public int compareTo(Position other) {
if (this.getRow() != other.getRow()) return this.getRow() - other.getRow();
return this.getColumn() - other.getColumn();
}
@Override
public String toString() {
return "{" + this.getRow() + ", " + this.getColumn() + "}";
}
}
/**
* Stores the current cost of a cow along with the last microcontroller added. To save space,
* states only store the last delta and obscures the rest of the state in the cost variable.
*/
private static class MicrocontrollerState implements Comparable<MicrocontrollerState> {
private long cost;
private Position position; // the position of the last microcontroller added
public MicrocontrollerState(long cost, Position position) {
this.cost = cost;
this.position = position;
}
public long getCost() { return this.cost; }
public Position getPosition() { return this.position; }
public int compareTo(MicrocontrollerState other) {
if (this.getCost() != other.getCost()) return (int) Math.signum(this.getCost() - other.getCost());
return this.position.compareTo(other.position);
}
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new FileReader("roboherd.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("roboherd.out")));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken()); // number of microcontrollers per cow
int K = Integer.parseInt(st.nextToken()); // number of cows to make
assert 1 <= N && N <= 100000 : N;
assert 1 <= K && K <= 100000 : K;
ArrayList<int[]> P = new ArrayList<int[]>(N); // microcontroller cost deltas
long minCost = 0; // min cost to make all the cows wanted
for (int i = 0; i < N; ++i) {
st = new StringTokenizer(in.readLine());
int M = Integer.parseInt(st.nextToken());
assert 1 <= M && M <= 10 : M;
int[] costs = new int[M];
for (int j = 0; j < M; ++j) {
costs[j] = Integer.parseInt(st.nextToken());
assert 1 <= costs[j] && costs[j] <= 100000000 : costs[j];
}
Arrays.sort(costs);
minCost += costs[0];
// Store deltas, which will only exist if there is more than one type of microcontroller.
if (M > 1) {
int[] costDeltas = new int[M - 1];
for (int j = M - 2; j >= 0; --j) costDeltas[j] = costs[j + 1] - costs[j];
P.add(costDeltas);
}
}
in.close();
N = P.size(); // redefine N to exclude microcontrollers of only 1 type
--K; // we already have our first cow
// Identify the next best configuration in log(K) time.
PriorityQueue<MicrocontrollerState> pq = new PriorityQueue<MicrocontrollerState>(3*K);
// Order the microcontrollers in such a way that if we were to vary the prototype by only 1,
// the best way to do would be to pick microcontrollers in the order
// (0,0), (0,1),...,(0,M_0-2),(1,0),...,(1,M_1-2),...,(N-1,0),...,(N-1,M_{N-1}-2)
Collections.sort(P, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
for (int j = 0; j < Math.min(a.length, b.length); ++j)
if (a[j] != b[j]) return a[j] - b[j];
return a.length - b.length;
}
});
pq.add(new MicrocontrollerState(minCost + P.get(0)[0], new Position(0, 0)));
// Imagine constructing a tree with K nodes, where the root is the cheapest cow. Each node contains
// the delta from its parent. The next cheapest cow can always be had by taking an existing node on
// the tree and varying a single microcontroller.
for (; K > 0; --K) {
MicrocontrollerState currentState = pq.remove(); // get the next best cow prototype.
long currentCost = currentState.getCost();
minCost += currentCost;
int i = currentState.getPosition().getRow();
int j = currentState.getPosition().getColumn();
// Our invariant to avoid double counting is to only add microcontrollers with "greater" position.
// Given a prototype, from our ordering, the best way to vary a single microcontroller is replace
// it with (i,j + 1) or add (i + 1, 0).
if (j + 1 < P.get(i).length) {
pq.add(new MicrocontrollerState(currentCost + P.get(i)[j + 1], new Position(i, j + 1)));
}
if (i + 1 < N) {
// Account for the special case, where we just use the cheapest version of type i microcontrollers.
// Thus, we remove i and add i + 1. This is better than preemptively filling the priority queue.
if (j == 0) pq.add(new MicrocontrollerState(
currentCost - P.get(i)[j] + P.get(i + 1)[0], new Position(i + 1, 0)));
pq.add(new MicrocontrollerState(currentCost + P.get(i + 1)[0], new Position(i + 1, 0)));
}
}
out.println(minCost);
out.close();
}
}
Sorting is $O(NM\log N)$. Polling from the priority queue is $O(K\log K)$ since each node will at most generate 3 additional nodes to put in the priority queue. So, total running time is $O(NM\log N + K\log K)$.
2013 USAMO Problem 2
Math has become a bit painful for me. While it was my first love, I have to admit that a bachelor's and master's degree later, I'm a failed mathematician. I've recently overcome my disappointment and decided to persist in learning and practicing math despite my lack of talent. This is the first USAMO problem that I've been able to solve, which I did on Friday. Here's the problem.
For a positive integer $n\geq 3$ plot $n$ equally spaced points around a circle. Label one of them $A$, and place a marker at $A$. One may move the marker forward in a clockwise direction to either the next point or the point after that. Hence there are a total of $2n$ distinct moves available; two from each point. Let $a_n$ count the number of ways to advance around the circle exactly twice, beginning and ending at $A$, without repeating a move. Prove that $a_{n-1}+a_n=2^n$ for all $n\geq 4$.
The solution on the AOPS wiki uses tiling. I use a different strategy that leads to the same result.
Let the points on the cricle be $P_1,P_2, \ldots,P_n$. First, we prove that each point on the circle is visited either $1$ or $2$ times, except for $A = P_1$, which can be visited $3$ times since it's our starting and ending point. It's clear that $2$ times is upper bound for the other points. Suppose a point is never visited, though. We can only move in increments of $1$ and $2$, so if $P_k$ was never visited, we have made a move of $2$ steps from $P_{k-1}$ twice, which is not allowed.
In this way, we can index our different paths by tuples $(m_1,m_2,\ldots,m_n)$, where $m_i$ is which move we make the first time that we visit $P_i$, so $m_i \in \{1,2\}$. Since moves have to be distinct, the second move is determined by the first move. Thus, we have $2^n$ possible paths.
Here are examples of such paths.
Both paths are valid in the sense that no move is repeated. However, we only count the one on the left since after two cycles we must return to $P_1$.
The path on the left is $(1,2,2,2,1)$, which is valid since we end up at $A = P_1$. The path on the right is $(1,1,1,1,1)$, which is invalid, since miss $A = P_1$ the second time. The first step from a point is black, and the second step is blue. The edge labels are the order in which the edges are traversed.Now, given all the possible paths with distinct moves for a circle with $n - 1$ points, we can generate all the possible paths for a circle with $n$ points by appending a $1$ or a $2$ to the $n - 1$ paths if we consider their representation as a vector of length $n - 1$ of $1$s and $2$s. In this way, the previous $2^{n-1}$ paths become $2^n$ paths.
Now, we can attack the problem in a case-wise manner.
- Consider an invalid path, $(m_1,m_2,\ldots,m_{n-1})$. All these paths must land at $P_1$ after the first cycle around the circle. Why? Since the path is invalid, that means we touch $P_{n-1}$ in the second cycle and make a jump over $P_1$ by moving $2$ steps. Thus, if we previously touched $P_{n-1},$ we moved to $P_1$ since moves must be distinct. If the first time that we touch $P_{n-1}$ is the second cycle, then, we jumped over it in first cycle by going moving $P_{n-2} \rightarrow P_1$.
- Make it $(m_1,m_2,\ldots,m_{n-1}, 1)$. This path is now valid. $P_n$ is now where $P_1$ would have been in the first cycle, so we hit $P_n$ and move to $P_1$. Then, we continue as we normally did. Instead of ending like $P_{n-1} \rightarrow P_2$ by jumping over $P_1$, we jump over $P_n$ instead, so we end up making the move $P_{n-1} \rightarrow P_1$ at the end.
- Make it $(m_1,m_2,\ldots,m_{n-1}, 2)$. This path is now valid. This case is easier. We again touch $P_n$ in the first cycle. Thus, next time we hit $P_n$, we'll make the move $P_n \rightarrow P_1$ since we must make distinct moves. If we don't hit $P_n$ again, that means we jumped $2$ from $P_{n-1}$, which means that we made the move $P_{n - 1} \rightarrow P_1$.
Consider an existing valid path, now, $(m_1,m_2,\ldots,m_{n-1})$. There are $a_{n-1}$ of these.
- Let it be a path where we touch $P_1$ $3$ times.
- Make it $(m_1,m_2,\ldots,m_{n-1}, 1)$. This path is invalid. $P_n$ will be where $P_1$ was in the first cycle. So, we'll make the move $P_n \rightarrow P_1$ and continue with the same sequence of moves as before. But instead of landing at $P_1$ when the second cycle ends, we'll land at $P_n$, and jump over $P_1$ by making the move $P_n \rightarrow P_2$.
- Make it $(m_1,m_2,\ldots,m_{n-1}, 2)$. This path is valid. Again, we'll touch $P_n$ in the first cycle, so the next time that we hit $P_n$, we'll move to $P_1$. If we don't touch $P_n$ again, we jump over it onto $P_1$, anyway, by moving $P_{n-1} \rightarrow P_1$.
Let it be a path where we touch $P_1$ $2$ times.
- Make it $(m_1,m_2,\ldots,m_{n-1}, 1)$. This path is valid. Instead of jumping over $P_1$ at the end of the first cycle, we'll be jumping over $P_n$. We must touch $P_n$, eventually, so from there, we'll make the move $P_n \rightarrow P_1$.
- Make it $(m_1,m_2,\ldots,m_{n-1}, 2)$. This path is invalid. We have the same situation where we skip $P_n$ the first time. Then, we'll have to end up at $P_n$ the second time and make the move $P_{n} \rightarrow P_2$.
In either case, old valid paths lead to $1$ new valid path and $1$ new invalid path.
- Let it be a path where we touch $P_1$ $3$ times.
Thus, we have that $a_n = 2^n - a_{n-1} \Rightarrow \boxed{a_{n - 1} + a_n = 2^n}$ for $n \geq 4$ since old invalid paths lead to $2$ new valid paths and old valid paths lead to $1$ new valid path. And actually, this proof works when $n \geq 3$ even though the problem only asks for $n \geq 4$. Since we have $P_{n-2} \rightarrow P_1$ at one point in the proof, anything with smaller $n$ is nonsense.
Yay, 2017!
It's been a long time since I posted anything. Mostly because I haven't been up to anything interesting, lately. I don't really cook anymore, but I did manage to bake these Double Chocolate Cookies. I love chocolate, but I think these were too much for me.
For Thanksgiving, I got to see my older cousin Daniel Pham. When I was younger, I thought that he was the coolest guy ever. He played high school football and went to Stanford. Still a pretty cool guy, but I guess through no fault of his own, he could never live up to the "colossal vitality of [my] illusion." Or I guess life just gets more boring once you have kids. By the way, recognize the quote?
I remade my Apple Pie for the holiday. It was definitely easier and came out better this time around. There's still some work that I could do to make the crust flakier. Maybe I really need the vodka? Given enough opportunities I hope to figure it out.
Recently, I was back in Philly for the first time since I moved to Seattle. It was great to see family again. Amish and I don't really agree on foods very much, for he hates fish sauce, a staple of Vietnamese cuisine. However, we both like Mozzarella Sticks. I guess it might be a tradition to make these with him when I'm back in Philly
Anyway, it's New Year's Eve. Given that I'm in a strange new city, instead of ringing in the new year with loved ones, I have a quiet night and extended weekend to reflect on this new chapter of my life in Seattle.
Since I moved here for work, perhaps it's no surprise that I spend most of my time here working, and admittedly, I quite enjoy my job. It seems that software engineering rather suits me. Given a problem, I often find myself obsessed with solving it and unable to put it aside. Then, there's that rush of dopamine when your code passes the tests and everything changes from red to green. Admittedly, most of these problems are rather meaningless, but living "with the bearing of one who was going to give his days and nights to Ecclesiastes for ever", these bugs and math problems have become a kind of escape for me.
We all imagine ourselves as heroes of our personal story. Lost in the abstract world of code and math, I seem to have forgotten that everyone else has a story, too, not just me. I read something of that sort in a book once, where we always expect everyone around us to stay as static characters while we, personally, plow on with our story and overcome many obstacles. Perhaps, this is why mothers cry when their children go to college, or every family gathering, we're shocked how old are nieces and nephews are. When I was in college, I remember we would joke about certain friends, saying "I could never see him/her married", or "could you imagine so-and-so as a doctor?" Not in a sexist or racist way, but they were such jokesters or so irresponsible, it was hard to imagine that scenario.
Seeing my cousin Daniel and visiting Philly, I've started to see this lack of imagination in myself. Everyone has rich and varied lives that proceed with or without me, and to be honest, I'm mostly a nonfactor in their stories. I guess there's a selfish part of me that makes it hard to accept changes that I wasn't directly part of. Buried under work, I've finally emerged into a new world where everyone is getting married, having kids, and moving to new cities.
We sort of imagine a life for ourselves evolving as a person by forming new relationships, getting new hobbies, or advancing our career, yet for some reason, we're often taken aback when others' lives evolve in the same way. I guess that's because we often describe our loved ones as our rocks that we rely on when times are tough. Unfotunately, these rocks are quite amorphous, and we can't exactly expect that person to fit into the neat little box that we made for them in our mind.
In some ways, this is a good thing. I'm continually amazed by what others accomplish. I might remember them as a struggling college student or socially awkward. It's great to see people exceed expectations. In other ways, it's disappointing. People that you thought were close friends will go ghost and disappear.
Anyway, I'm not sure if there's any point to this rambling. I don't really have any resolutions for 2017. I guess that I'm just becoming more cognizant of how little that I understand about the world around me.
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.
Go West, young man, go West and grow up with the country.
- Horace Greeley
Despite being said in 1865, there has never been so many people heeding Mr. Greeley's advice as there are now. Every week, I find that one of my college classmate's has decided to go West. And why not? There's riches to be made thanks to a booming tech industry, and the weather is good. Unlike the olden days, where you had to suffer the Oregon Trail, there's not much risk at all.
As it turns out, when your hobbies consist of math, reading, and picking heaving things up and putting them down, every city is virtually the same. Despite Seattle being colder and cloudier and having nice mountains like Mount Shuskan picture above, I don't feel markedly different than I did in Philadelphia.
The biggest change in my life has been going from living in a house with 6 guys to having my own bedroom with only 1 roommate. With the quiet, I definitely find myself getting more work done, but I'll miss having the guys around for sure.
Some mint chocolate chip ice cream that I made with Masato before I left. See The Only Ice Cream Recipe You’ll Ever Need for the recipe.
Now, that I've moved several times in my life (Hatfield, PA $\rightarrow$ Durham, NC $\rightarrow$ Cambridge, MA $\rightarrow$ Philadelphia, PA $\rightarrow$ Seattle, WA), I've started to reflect on any regrets and what I miss. Certainly, there are all those restaurants and eats that I forgot to try. I never did eat at Craigie on Main or try a cheesesteak from Pat's or Gino's. There are missed opportunities like never having gone to the top of the Chapel or taking a certain class. However, what always haunts me the most are the people that I wish that I had gotten to know better. It always seemed that so many connections were missed. People were just busy, feelings were misinterpreted, or the timing was just bad, and as a result, nothing ever happened. Of course, there's the very real possibility that the people that I wanted to get to know better had no interest in getting to know me, so maybe, I'm just talking nonsense.
There was some part of me that did want to stay in Philadelphia, but no opportunity ever came up to do so. It's probably best that I left, though. While I was comfortable, my life did seem to be stagnating in some respects. In the month leading up to my going away, I found myself mostly just watching Korean dramas with my brother. That is to say, I wasn't accomplishing much of anything useful with my time, and with the exception of the guys in the house, I didn't have much other community. Essentially, I was a ghost. Perhaps, moving to a new city will reinvigorate me.
A couple of weeks ago, Michael Vo needed to cook for a Renewal College Fellowship (RCF) potluck, and I decided to help out a bit. Mike is mostly known for his famous chicken alfredo, so it was no surprise at all when his spaghetti and meatballs turned out to be the best spaghetti and meatballs ever according to my brother.
We based it off of the recipe Spaghetti and Drop Meatballs With Tomato Sauce. Now, there are a couple of modifications needed for this recipe. First to serve 4, you'll need at least 24 ounces of meat, not 12, and therefore, an extra egg. We also thought that it would be a good idea to use the scrapings from the bottom of the skillet and the oil from searing the meatballs and mix it into the sauce. Mike always goes big, and we ended up quadrupling the recipe and using 7 pounds of ground beef. Now, this massive quantity required special techniques to preserve the oil and scrapings at the bottom of the skillet. After every batch of meatballs, we needed to scrape the skillets and run the oil through a sieve.
Here is a picture of the second part, where we cooked the meatballs in the sauce.
The only complaint that some people had about the recipe was the mixing in of the cheese into the meatballs. It was a matter of opinion whether this tasted good or bad. I personally like it.
Anyway, if you ever find yourself in the deserts of West Philly, you should do yourself a favor a stop by the BAD house to get some of Michael Vo's Spaghetti and Meatballs for nourishment.
Before I left Philly, we took a short road trip down to Baltimore to visit Tim Wu. When we got there, the first thing we did was get some Korean BBQ at 1:30 AM at Honey Pig. We don't do so well with alcohol, so we only had 1 bottle of Soju between the 5 of us. Despite having to sleep on the floor with only substandard air conditioning, I ended up sleeping quite well that night.
The next day, we went fishing and crabbing. Unfortunately, this was not a success. With the exception of Dan Wu's fish, we did not catch anything despite spending nearly 5 hours.
Dan Wu's catch
As Tim and I took a walk around Fort Smallwood Park, we found a beach and an approximately 7-year-old kid that told us we could find clams by digging into the sand with our feet. Desperate to catch anything, I heeded his advice and waded into Chesapeake Bay and attuned myself to the sensations of my feet. At first, I thought that they were nothing more than smooth rocks, but after 5 minutes or so, I took a dive and had my first clam. Within the next half hour, I had about a dozen more.
As you can see in the title picture, I ended up steaming those clams and eating them with butter. They were a bit sandy, but otherwise, they were great. After descaling and cleaning the fish, I steamed him or her, too, for maybe 6 ounces of meat? All told, we got 1 solid meal for a single person for 5 hours of effort from 7 people. It's probably the most Paleo thing that I've ever made since I not only cooked but also caught those clams by hand. It doesn't look like we'd survive in Paleolithic times, though, with our fishing skills.
Steamed fish
Since we couldn't catch enough to eat, we ended our fishing trip with some crab cakes from G & M. Usually, I think of crab cakes as pretty poor value propositions since they tend to be small without much crab meat. Here, I was proven wrong as these crab cakes were huge and full of protein. I don't think any of us left hungry. Finally, we had a nice romantic walk along the harbor. Well, in my brother's case, it was more of a Poké Walk.
Friends at the harbor. Photo Credits: Masato Sugeno
After my good friend Han Zhang introduced me Lion's Head meatballs at Yaso Tangbao in Downtown Brooklyn, I decided that I had to figure out how to cook these. It took me nearly a year before I got around to doing so, but I finally got the chance to make them with Liz Liang when visiting the Washington, D.C. area.
We used the recipe How to Make Shanghai Lion's Head Meatballs from Serious Eats. Fortunately, it doesn't take that long, so we didn't miss out on too many Pokémon.
Sizzling Lion's head meatballs
Overall, I found it to be a very good recipe, but the proportion of meat and noodles could be adjusted. The woman that made it lives in some strange world where 12 ounces of ground pork feeds 4. We ended up using a little over 2 pounds of ground pork, which resulted in 10 huge meatballs, each about 2.5 inches in diameter. You could double the vermicelli, too, but I like a high meat-to-noodle ratio. The water chestnuts were an interesting twist that might not be for everyone, but they add a nice crunchy texture to the meatballs.
For dessert, Liz was kind enough to make us some blueberry bread pudding, too!
I only helped make the custard. The recipe is blueberry bread and butter pudding. I thought it turned out great, and I like how it wasn't it all that sweet.
Anyway, there's only a week left until I move to Seattle. I'll be saying my goodbyes to Philly soon.