Skip to content

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

Your email is never published nor shared. Required fields are marked *
*
*