Skip to content

There is some truths in this

between the ages of 10 and 20,
people who are most envied are those with beauty;

between the ages of 20 and 30,
people who are most envied are those who’ve found love;

between the ages of 30 and 40,
people who are most envied are those whose children are ones they can be proud of;

between the ages of 40 and 50,
people who are most envied are those who are successful;

between the ages of 50 and 60,
people who are most envied are those whose children are successful;

between the ages of 60 and 70,
people who are most envied are those who have happily married children and beautiful grandchildren;

between the ages of 70 and 80,
people who are most envied are those who have their health;

between the ages of 80 and beyond,
people who are most envied are those who die painlessly.

Life passes us so quickly.
In what should we invest our time?

Facebook Hacker Cup Round 1A

I stayed up till 7AM today for this, because I’m going to be busy all weekend. Too bad the submissions were all invalidated and pushed back a week, though. Here are the solutions, in Ruby as usual:

After the Dance Battle: (note: I used Dijkstra’s to search paths, but in reality, you just need BFS. That’s not the slow part, though. It takes way longer to draw out the graph than to actually calculate the path. An extra VLog(V) isn’t THAT bad.)

class Graph
  def initialize
    @graph = {}
    @nodes = Array.new
    @INFINITY = 1 << 64    
  end        
  def add_edge(s,t,w=1)     
    @graph.has_key?(s) ? @graph[s][t] = w : @graph[s] = {t=>w}
    @graph.has_key?(t) ? @graph[t][s] = w : @graph[t] = {s=>w}
    @nodes << s unless @nodes.include?(s)
    @nodes << t unless @nodes.include?(t)   
  end   
  def dijkstra(s)     
    @d = {}
    @prev = {} 
    @nodes.each do |i| 
      @d[i] = @INFINITY 
      @prev[i] = -1 
    end 
    @d[s] = 0     
    q = @nodes.compact     
    while (q.size > 0)
      u = nil;
      q.each do |min|
        if (not u) or (@d[min] and @d[min] < @d[u])
          u = min
        end
      end
      if (@d[u] == @INFINITY)
        break
      end
      q = q - [u]
      @graph[u].keys.each do |v|
        alt = @d[u] + @graph[u][v]
        if (alt < @d[v])
          @d[v] = alt
          @prev[v]  = u
        end
      end
    end
  end

  def run_alg(startpoint, endpoint)
    dijkstra startpoint
    puts "#{@d[endpoint]}" if @d[endpoint] != @INFINITY
  end
end

def run_line(data)
  gr = Graph.new

  data_arr = data.split(" ")
  height = data_arr.shift.to_i
  width = data_arr.shift.to_i

  portals = {}
  board = data_arr.map{|r| r.split("")}

  startpoint = "0,#{board[0].index("S")}"
  endpoint = "#{height-1},#{board[height-1].index("E").to_s}"

  board.each_index do |i|
    board[i].each_index do |j|
      current = board[i][j]
      if current != "W"
        gr.add_edge("#{i},#{j}", "#{i-1},#{j}") if board[i-1][j] != "W" && i != 0
        gr.add_edge("#{i},#{j}", "#{i},#{j-1}") if board[i][j-1] != "W" && j != 0
        gr.add_edge("#{i},#{j}", "#{i+1},#{j}") if i != height - 1 && board[i+1][j] != "W"
        gr.add_edge("#{i},#{j}", "#{i},#{j+1}") if j != width - 1 && board[i][j+1] != "W"

        if 1 <= current.to_i && current.to_i <= 9
          if portals[current]
            portals[current].each do |p|
              gr.add_edge("#{i},#{j}", "#{p[0]},#{p[1]}")
            end
            portals[current] << [i,j]
          else
            portals[current] = [[i,j]]
          end
        end
      end
    end
  end

  gr.run_alg(startpoint, endpoint)
end

f=File.open("input.txt", "r")
total = f.readline.to_i
(0..total-1).each do |i|
  run_line(f.readline)
end
f.close

Power Overwhelming

I can’t exactly come up with elegant code for this, so I am not going even going to bother pasting my semi-bruteforce method here. But here’s the jist:

It’s a simple high school math problem – two functions, one to maximize, one as constraint:
f(x) = maximization = total damage = X * Y
g(x) = constraint => C1*X + C2*Y = C3
C1 = G as given, C2 = W as given, C3 = M as given, X = number of warriors, Y = number of shields

After some substitution and derivative, we end up with X0 = C3/(2*C1), Y <= (C3 – C1*X)/C2
So, we just solve for X0. Here’s the tricky part… Facebook wanted an integer solution to X0, the optimal number of warriors to create, but the true optimum is not an integer. Using the true optimum as a center, I bruteforced the rest of the results. It took a while because sometimes Facebook’s solution and mine differ by over 20,000.

First or Last

I didn’t bother doing it. The explanations looked way too complicated.

Facebook Hacker Cup Qualifications Round

Waking up late because of last night’s crazy party, I decided to check out the problems of Facebook Hacker Cup. I spent 30 minutes on the first problem (Double Squares) before realizing the obvious solution. It’s actually really easy – four lines of ruby code excluding the method definition lines. I didn’t know about the 6 minute limits from generating input file to submitting the output file, so I couldn’t submit my solutions to the first problem. Seeing that I had another half an hour before I should start being productive, I did problem 3 (Studious Students) really quickly. Contrary to Facebook’s suggestions of using dynamic programming instead of brute-force, I coded up a brute-force algorithm (Permute + minimum); simple and runs fairly fast.

Solution to Question 1: Double Squares (Ruby)

def fun(n)
total = 0.0
(0..(Math.sqrt(n).floor)).each { |i| (total += 1) if is_int(Math.sqrt(n-(i**2.0))) }
return (total/2).ceil
end

def is_int(n)
n.to_i == n
end

%w(1048039120
1816371419
1215306625
).each{|i| puts fun(i.to_i)}

Solution to Question 3: Studious Students (Ruby)

def fun(str)
h=[]
arr = str.split(” “)
arr.shift
arr.map{|a| a + “{“}.sort.map{|a| a[0,a.length-1]} #{ is z’s charcode + 1. This ensures “a” to be sorted after “az”.
end

f=File.open(“input.txt”, “r”)
total = f.readline.to_i
(0..total).each do |i|
puts fun(f.readline)
end
f.close

As we go on, we remember all the times we had together.

And as our lives change, we will still be friends forever.

My first oversea trip since my arrival at Hong Kong ferried to Macau the 13 people I would later grow very fond of. The combination of cramming into two hotel rooms and Chanrith’s special talents, our travel group got cozy almost overnight. Throughout the semester, the group stayed mostly in tact – traveling to Shenzhen, Shanghai, Guilin, Singapore, and Bali. I will gladly talk about what I learned from traveling between underdeveloped (Indonesia), developing (China), and developed (Singapore) countries, but I’d like to keep this personal.

The highlight of this semester wasn’t the food I’ve tried, the places I shopped at, the handicrafts I bargained for, the clubs I partied at, the islands I visited, or the spa I chilled at. It was the never-ending mimicking of Mel’s British accent, Lisa and Chanith’s repetitions of MTR lady’s “tsing mat kao geng ce mun; qing bu yao kao jing che men; please stand back from the doors. De-de-de-de-de….”, Nima and Stephan’s retardedness when drunk, Michael’s “holy shit… Caaarsonn”, Carson’s fake cries, Bell’s scary Thai mafia connections, Adam’s bottomless stomach, Helen’s hoochi-mama talk, Ian’s random cold jokes, Vinny’s horrible attempt of being non-Cantonese at the spa, Julius’s German engineering genius (to which he would say “yah yah”), and Amy’s hilariously inappropriate comments. I have never hung out with a group so diverse yet so friendly despite our differences. You all made my semester better than everything I had hoped for.

I thank you all for a wonderful 123 days. To those in Europe – the Californians will hopefully see you all in 2012! To Bell – good luck in your graduate school applications!

The Last Supper

The Last Supper

P.S. Asians are fine with taking photos with strangers in the background.

Repulse Bay looks like Morocco

What better way to spend Christmas than to shop for souvenirs at Stanley Market and walking on a nice beach? I shopped for a bunch of gifts and Hong Kong trinkets at the Stanley Market. The prices at some stores are all right, but most stores in the front are total rip-offs. I really enjoyed Repulse Bay. It reminded me of Sentosa of Singapore, a white, sandy beach enclosed by an arch of ridiculously nice and probably wallet-breaking hotels. I would get a room and relax on the beach if it were summer.

Doesn't this look like Morocco?

Doesn't this look like Morocco?

Sharp Island feels like Bali, except it is three miles away from HKUST

HKUST is built on the side of a mountain next to the sea, overlooking most of Sai Kung minor outlying islands. I have been wanting to go on one of those deserted islands for a long time, and letting an opportunity like this pass is like not selling your Tech stocks in 1999 when you could. Adam, Bell, Carson, Michael, and I bargained for a boat to take us to Sharp Island for only $35 HK per person round trip.

Sharp Island has maybe one or two houses, and besides the dock, there are no other man-made structures. We took a few Titanic photos on the dock, then realized there was a natural rock paved bridge to the nearby Kiu Tau Island. Skipping along the rocks like we skipped stones over the water, we arrived at the entrance of the island. Walking up some more stairs, we found the top of the island, featuring a view of most nearby islands and HKUST. Our way back rivaled the Long March. The natural bridge was being covered quickly by the rising tide. It was a race against time and separation, because we either run faster, or get our shoes wet, or not able to cross back to the island and reach the dock at all, which means spending the entire day on the island!

The waters of Sai Kung. Look how clear it is!

The waters of Sai Kung. Look how clear it is!

We spent Christmas Eve dining at Tsui Wah’s, looking for Christmas trees, and waiting for the Christmas countdown, which we eventually gave up waiting for. Tonight bids farewell to Central; and I was just starting to get accustomed to it!

We just can't get enough of each other

We just can't get enough of each other

International Finance Centre, Bird Market, and Flower Market

Trying to pack as much events as possible in our last days in Hong Kong, we visited the International Finance Centre (IFC) in Central in the morning. The MTR took us right inside IFC One, the shorter brother of the more iconic IFC Two. Since the observatory in IFC Two had a long wait-time, we just walked around and shopped in the high class stores inside. Security was really tight. Stephan, who was pretty much temporarily crippled, couldn’t lean against the wall to rest up, and I couldn’t take any photos of the insides of the tower. According to the information booth, there is “absolutely nothing” to do for tourists in IFC One. We did get to see a truck do the wheelie when picking up a cargo bay that’s heavier than itself, though.

Look! It's where Batman jumped off of!

Look! It's where Batman jumped off of!

Our night time activity was going to a bird and flower market. It’s nothing too exciting because I’m not too much into flowers.

Master Shifu deeply calculating the possible moves in a pagoda surrounded by chirping birds.

Master Shifu deeply calculating the possible moves in a pagoda surrounded by chirping birds.

The highest point in Hong Kong is not the tip of a skyscraper

It’s actually Victoria Peak! I woke up really early in the morning to grab amazing views of the Hong Kong skyline before it gets too crowded. A short tram ride and some walking later, we arrived at a set of lions guarding a stone arch. Passing through the arches, I was dazed by what stood beneath me – the entire Victoria Harbor, Tsim Sha Tsui, and Central (yes, that’s both sides of the harbor) gleamed in sky-scraping glory. We each took a bunch of photos with the different permutations of all the people we had before greeting this magnificent pagoda and the large influx of tourists good bye.

Lion overlooking Victoria Peak, with the IFC in the distance.

Lion overlooking Victoria Peak, with the IFC in the distance.

Everything will come around in the end, including having Seafood at Sai Kung

One of the earliest places we dined in HK was at Chuen Kee Seafood. Today, we revisited the place for old time’s sake, even though we lost Candace and her friends. We ordered the twelve people set dish, which came with twelve delicious dishes. Combined with Ian’s three vegetarian dishes and six bottles of beer, the dinner foreshadowed the imminent end of our Hong Kong trip.

Super tasty giant clams!

Super tasty giant clams!

Sawadee Thailand is a standard Thai food place in Sai Kung

In the midst of studying for finals, Bell wants to release some steam by having Thai food. She’s been eying that Thai place in the middle of an alley for a long time. I admit it offers some exotic dishes, but most of them start to taste the same after a few minutes. My tongue was having a massive flavor overdose from the spices and leaves. Next time I’m in Thailand, I’m ordering Pad Thai.

Sawadee Thailand - Sour and Spicy salad

Sawadee Thailand - Sour and Spicy salad