My good roommate Masato made donuts and left behind a bunch of dough (recipe). Clearly, I decided to turn the dough into cinnamon rolls!

It's pretty easy. Just roll out the dough and cover it with a cinnamon sugar-butter paste. The recipe for my paste is:

• 1/2 cup granulated sugar
• 1/2 cup brown sugar
• 3 tablespoons ground cinnamon
• 1/2 heaping teaspoon of nutmeg
• 1/2 heaping teaspoon of cloves
• 1/2 cup (1 stick) of unsalted butter

Just cream the butter and sugar together. Roll the dough so it's about 9 inches in height and 18 inches in width. Cover the dough with the paste. Cut into 2 inch vertical strips to give you 9 rolls. Roll them up and dip them in the remaining paste. Bake at 350 degrees Fahrenheit for 20 minutes. Serve with icing. I used this Ermine Icing. Yay!

In other news, life is okay. I just got back from visiting Duke, where I interviewed for the their Statistics PhD program. I thought it went well, but I'm often wrong about these things. In any case, it was great catching up with some old Duke friends. It was a particularly nice surprise to run into a friend from Boston.

The fact that I've been rejected at 2 schools so far gives me some anxiety, but I trust that things will turn all right no matter what happens.

When stuck inside because of the snow, what else is there to do but bake and code? I made these brownies here. They are amazingly moist, but I'll probably cut down on the sugar next time I make them.

On the algorithms side, I finally got to the Platinum Division on the USA Computing Olympiad. It's primarily for high school students, but I find it fun to participate anyway.

One of the competition's problems employs clever usage of binary search that I want to write about. Basically, there are times when the solution is very hard to compute, but it is not too costly to verify. If the solution is numerical and bounded, we can guess solutions with binary search. I've actually been quite familiar with this strategy for a year now, but somehow I missed it in this particular problem. Here, we use a two-dimensional binary search. Thankfully, I got enough points to get promoted to the next division anyway, anyway.

Angry Cows

Here's the problem statement:

Bessie the cow has designed what she thinks will be the next big hit video game: "Angry Cows". The premise, which she believes is completely original, is that the player shoots a cow with a slingshot into a one-dimensional scene consisting of a set of hay bales located at various points on a number line; the cow lands with sufficient force to detonate the hay bales in close proximity to her landing site, which in turn might set of a chain reaction that causes additional hay bales to explode. The goal is to use a single cow to start a chain reaction that detonates all the hay bales. There are $N$ hay bales located at distinct integer positions $x_1,x_2,\ldots,x_N$ on the number line. If a cow is launched with power $R$ landing at position $x$, this will causes a blast of "radius $R$", engulfing all hay bales within the range $x−R \ldots x+R$. These hay bales then themselves explode (all simultaneously), each with a blast radius of $R−1$. Any not-yet-exploded bales caught in these blasts then all explode (all simultaneously) with blast radius $R−2$, and so on.

Please determine the minimum amount of power $R$ with which a single cow may be launched so that, if it lands at an appropriate location, it will cause subsequent detonation of every single hay bale in the scene.

INPUT FORMAT (file angry.in):

The first line of input contains $R$ ($2 \leq N \leq 50,000$). The remaining $N$ lines all contain integers $x_1 \ldots x_N$ (each in the range $0 \ldots 1,000,000,000$).

OUTPUT FORMAT (file angry.out):

Please output the minimum power $R$ with which a cow must be launched in order to detonate all the hay bales. Answers should be rounded and printed to exactly $1$ decimal point.

So, if we assume the hay bales are sorted $x_1 \leq \cdots \leq x_N$. The minimum blast radius must be at most $(x_N - x_1)/2$ since we can just launch such a cow at the midpoint and destroy all the hay bales without the chain reaction. It's also worth noting that if the optimal blast radius is $R^*,$ then $2R^* \in \mathbb{Z}$, that is, twice the optimal blast radius is an integer. Since all the hay bales are located at integer coordinates, adding less than $0.5$ to the radius will never encompass another hay bale. Finally, the last observation is that we should fire the cow so that the very left of the blast lines up exactly with a hay bale since we would not gain anything by having the hay bale strictly inside the blast radius.

Let $L$ be the index of the leftmost hay bale hit by the initial blast. Thus, we could brute force by trying all $2R^* \in \{0,1,\ldots,x_N-x_1\}$ and $L \in \{1,2,\ldots,N\}$. To check if such values work, we can simulate the chain reaction which takes $O(N)$ time. Thus, brute force would take $O\left(N^2(x_N - x_1)\right)$ time. This is where binary search comes in.

During the contest, it was obvious to me that we should do a binary search to find $2R^*$ considering that $x_N - x_1$ could be as large as $10^9$. However, this is not fast enough, as that only gets us $O\left(N^2\log(x_N-x_1)\right)$ time, and $N^2$ can be as large as $2.5 \times 10^9$. After sleeping on it, I made the key insight that we can binary search on the index of the leftmost hay bale, too, so now we have $O\left(N\log(N)\log(x_N-x_1)\right)$ time, which is adequate.

To make this explicit, here's the code:

import java.io.*;
import java.util.*;

public class angry {

    /* check that all the hay bales to the left of idx explode 
     * if we throw cow of power T/2 at hayBales[idx] + T/2
     */
    public static boolean leftExplodes(int idx, int T, int[] hayBales) {
        double currentFloor = hayBales[idx];
        double currentR = T/2.0;
        int left; // leftmost exploded bale
        for (left = idx; left >= 0 && hayBales[left] >= currentFloor; --left) {
            if (left == 0 || hayBales[left - 1] >= currentFloor) continue;
            currentR -= 1.0;
            currentFloor = hayBales[left] - currentR;
        }
        return left == -1;
    }

    public static boolean isDiameterPossible(int T, int[] hayBales) {
        int N = hayBales.length;
        int leftMin = 0; // inclusive
        int leftMax = N; // exclusive         
        int leftIdx = leftMin + (leftMax - leftMin)/2;
        while (leftMin < leftMax) { // find smallest left such that this doesn't work
            if (leftExplodes(leftIdx, T, hayBales)) {
                leftMin = leftIdx + 1;
            } else {
                leftMax = leftIdx;
            }
            leftIdx = leftMin + (leftMax - leftMin)/2;            
        }        
        --leftIdx; // this works
        // now check that the right explodes
        double currentCeiling = hayBales[leftIdx] + T;
        double currentR = T/2.0;
        int right;
        for (right = leftIdx; right < N && hayBales[right] <= currentCeiling; ++right) {
            if (right == N - 1 || hayBales[right + 1] <= currentCeiling)  continue;
            currentR -= 1.0;
            currentCeiling = hayBales[right] + currentR;
        }        
        return right == N;        
    }        

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new FileReader("angry.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("angry.out")));
        int N = Integer.parseInt(in.readLine());
        int[] hayBales = new int[N];
        for (int n = 0; n < N; ++n) hayBales[n] = Integer.parseInt(in.readLine());
        Arrays.sort(hayBales);

        // search for T = 2R
        int minT = 0; int maxT = hayBales[N - 1] - hayBales[0];
        int T = minT + (maxT - minT)/2;       
        while (minT < maxT) { // find smallest T that works
            if (isDiameterPossible(T, hayBales)) {
                maxT = T;
            } else {
                minT = T + 1;
            }
            T = minT + (maxT - minT)/2;
        }
        out.printf("%.1f\n", T/2.0);
        in.close();
        out.close();
    }

}

Yesterday, I made a leg of lamb. I rather liked how it turned out, so I'll write some notes here for posterity.

Ingredients

• 3 lbs leg of lamb, preferably with the bone
• Spices
  • 1 teaspoon salt
  • 1/4 cup olive oil
  • 1/2 teaspoon black pepper
  • 1 lime/lemon
  • 3-4 sprigs of fresh rosemary
  • 1 teaspoon thyme
  • 4 cloves garlic
  • 1 teaspoon onion granules
• 2 cups chicken stock

Directions

1. Zest the lime and squeeze out the juice. Combine with all the spices. Make slits in the lamb and rub in the spice olive oil mixture. It looks like this.
2. Sear the leg of lamb in a dutch oven with lard. This takes about 3 minutes per side on medium-high heat. Add chicken stock to the dutch oven.
3. Braise it for about 45 minutes in the dutch oven with lid on at 325 degrees Farenheit. Remove the lid for and cook it another 30 minutes at 350 degrees. When done, it will look like this.
4. Slice and serve with reduced chicken stock. The bone marrow is an especially nice treat.

One of my favorite ways to bring people together, fellowship, and share a little bit about my culture is to cook a huge pot of phở (Vietnamese beef noodle soup for the uninitiated). It's fairly easy to make, and it's a novel experience for most people, who are accustomed to restaurant phở. I especially recommend making some during the cold winter months. After making it a few times I've come up with my own recipe. You'll need a stock pot that holds at least 16 quarts to proceed.

Ingredients

• Beef
  • 2-3 lbs leg bones
  • 2-3 lbs neck bones
  • 2-3 lbs oxtail
  • 5-7 lbs eye round roast, freeze and thinly slice, let it come to room temperature before serving
• Spices (you can opt to toast the spices over medium heat)
  • 5-10 whole star anise
  • 2 cardamom pods
  • 1 tablespoon whole coriander seeds
  • 1 tablespoon whole fennel seeds
  • 1 scant teaspon whole cloves
  • 2 sticks of cinnamon
• 2-4 nubs of ginger
• 2 medium-sized onions
• 1 dozen green onions also known as scallions
• 1 tablespoon salt
• 1/4-1/3 cups of a sweetener, sugar or syrup works
• 1 cup fish sauce, I recommend the Red Boat brand
• 6 lbs of fresh noodles, bánh phở tươi
• Condiments
  • Siracha
  • Hoison sauce
  • Thai chili peppers
  • Cilantro
  • Thai basil
  • Mung bean sprouts
  • Limes
  • Green onions

Steps

1. Ahead of time, freeze your eye round roasts and thinly slice them. This is easily the most labor-intensive part. Set aside and refrigerate. Let the slices sit for 2-3 hours at room temperature before serving.
2. Parboil the bones and oxtail for a cleaner broth. Bring water to a boil. Put the bones and oxtail in the water. Let the water return to a boil. After 5-10 minutes, dump the water, and wash the bones and oxtail. Return the bones and oxtail to the pot, fill it with water, and simmer.
3. Char the onions and ginger under the broiler. This usually takes about 10 minutes. Add the onions and ginger to the pot. Also, add the white part of the green onions.
4. Toast the spices and put them in a spice bag or tea infuser. Add the bag of spices or tea infuser to the pot.
5. Add fish sauce, salt, and sweetener. Back when I followed Paleo more strictly, I refused to use sugar, so I used maple syrup. In reality, sugar works just as well.
6. Now let the broth simmer. I find 8 hours is enough. You can go longer for a more intense flavor. If you serve it after just 8 hours, you can just add more water to make more broth. It's a little bit like making a second brew of tea.
7. Add more fish sauce, salt, or sugar to taste.

Serving

1. Bring the thinly sliced eye round roast out. Wash the vegetables. Remove the thick stems from cilantro. Cut the limes into eighths. Cut the Thai chili peppers and the green part of the scallions.
2. Filter out broth into a smaller pot. Skim excess fat. Don't skim all of it, though. The fat makes the broth more savory. Bring the smaller pot to a boil.
3. To cook the noodles, bring another pot of water to a boil. Add the noodles and stir them around for about 20 seconds. Drain with a colander.
4. Put the noodles in a bowl and add the raw meat to the bowl. Pour the boiling broth over the raw meat to cook the meat.
5. For your VIP guests, dig out some oxtail from the larger stock pot. The braised, fatty meat melts in your mouth.
6. Add condiments and enjoy!

After making a few bowls, I usually let guests make their own. This recipe may not be the most authentic, but it tastes pretty good in my opinion. Notice that most times and ingredients are given in ranges and are not exact. The recipe is pretty forgiving, and you can modify it according to your preference.

Over Halloween weekend, my roommate Masato and I decided to have another one of our cook offs and made donuts together. He made these Fluffy Yeasted Donuts, and I made these Apple Cider Doughnuts. I thought mine came out pretty well, but it was pretty much universally agreed upon that Masato's came out better.

I usually eat mostly Paleo, so working with flour and dough was a very novel experience. In this particular recipe, the dough was very sticky, so it required sprinkling a lot of extra flour when rolling and cutting the dough (thanks Masato for the pro tip!). In the end, I thought that the flavor was great, but the donuts were pretty dense. I really enjoyed the fluffiness of Masato's donuts more. Some future diabetics said that it could be sweeter, but that's just their opinion.

As for life, things are going pretty well. I'm finally no longer sick, so I've gotten some good workouts in. Sprinting this morning with Michael Vo was death. I lost every set except the first, and I only won probably because he got confused. Reapplying to graduate school is definitely stressful, but I'm learning to cope. Lately, I haven't had time to code too much, but hopefully I'll get back into that soon.

On a suggestion, I decided to procrastinate and make fried macaroni and cheese balls. There'e pretty easy to make. Make some macaroni and cheese. Refrigerate it. Pack them into balls, triple bread them, and then, fry them in a wok. Serve with marinara sauce.

Some suggestions from my brother:

• Make the cheese more liquid so it oozes cheese
• Use more seasoning in the breading

As for life, I'm currently a little sick and getting lots of nose bleeds. I probably don't sleep enough and don't wear enough clothing for this cold October weather. Other than these physical ailments, I'm learning to enjoy life despite the anxiety of not having the faintest idea of where I will be next year. I find my classes pretty interesting for one. I'm either becoming more apathetic or learning to let things happen.

One of my favorite characters in literature is Sydney Carton from Charles Dickens' A Tale of Two Cities because his self-sacrificing, unselfish love for Lucie indulges my romantic and idealistic nature. There's always the danger of become too like him, though. This quote best describes his predicament:

Sadly, sadly, the sun rose; it rose upon no sadder sight than the man of good abilities and good emotions, incapable of their directed exercise, incapable of his own help and his own happiness, sensible of the blight on him, and resigning himself to let it eat him away.

Continuing with the cooking for a 7-year-old series, I made mozzarella sticks tonight. Learning to cook for my brother, I've developed the skill set to be the dad of a picky eater (hint, hint).

I made my own tomato sauce and triple breaded these mozzarella sticks: flour, egg, flour, egg, and bread crumbs. Next, I deep fried them in a wok. I thought that they came out pretty good. They are definitely better than North Penn High School max sticks in any case.

In other news, school hasn't been too busy so far, which has given me some time to get back in the gym. I've also been sleeping a lot, perhaps, too much. Sometimes I wonder if I'm running away from life by sleeping. I have actually been somewhat social, though. My cousin had an engagement part last weekend, and I've been spending a lot of time with roommmates.

For me, cooking is a hobby that serves many purposes. It's a way to relax, and it can be pure fun to make something new. I also use it show my love for others, for I've never been good with words. Lately, I've been cooking as a way to challenge myself: I like to attempt to make people's favorite foods. Perhaps, there's a people-pleaser part of me, too, that seeks approval.

In any case, since Philadelphia still remains a relatively new city for me, I don't have many people to cook for except my brother, Christopher Pham. For those of you that know him, he eats simple foods that you would expect a 7-year-old child to enjoy. That leaves me cooking decidedly non-Paleo fare. A couple of weeks ago, I made orange sherbet for instance.

One of his favorite foods is macaroni and cheese. This particular version is extremely creamy featuring lots of butter, evaporated milk, and a mix of chedder and gruyère cheese. To add some crispyness, I topped it with toasted bread crumbs. Thankfully, he thought it was pretty good, perhaps, slightly better than his usual Kraft variety.

After some more iterations, I've settled on this recipe, The Best Macaroni and Cheese. It's not quite the best when followed literally, though. First, I use a blend of 1/2 cheddar and 1/2 Monterey Jack cheese. Also, the baking time needs to be modified. Proceed with the first 5 minutes according to the recipe. After the second 5 minutes, add the remaining milk and cheese. It's done after another 5 minutes. All in all, the baking time is cut in half.