## 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

## Post a Comment