Google Code Jam has always been a competition I have cherished, simply because the problems they post are brilliant and the closest to reality as compared to problems of other competitions. They’re always fun to read, disect & solve, more often than not, the solutions are reasonably trivial (especially for the qualifiers) yet extremely subtle & deceptive.
Today I want to share the solutions of 3 problems I was able to solve, the code should pretty much speak for itself because none of it is very complex.
Magic Trick
This one was the easiest of all, more of a warmup I suppose. Here’s the solution :
12345678910111213141516171819202122232425262728293031323334353637def get_ansgets.to_ienddef get_arrarr = []4.times doarr << gets.split.map(&:to_i)endarrenddef get_ans_arr[get_ans, get_arr]enddef pout(x, y)puts "Case ##{x}: #{y}"enddef solve(a1, arr1, a2, arr2)int = arr1[a1-1] & arr2[a2-1]case int.sizewhen 0'Volunteer cheated!'when 1int[0]when 2..4'Bad magician!'endendgets.to_i.times do |i|a1, arr1 = get_ans_arra2, arr2 = get_ans_arrpout(i+1, solve(a1, arr1, a2, arr2))endCookie Clicker Alpha
Based on Cookie Clicker game developed by Orteil, this one was slightly trickier, and required a little bit of math. I solved it with a recursive algorithm first, then optimized it into an iterative one to pass for the large input. Here’s my solution with both recursive and iterative parts :
1234567891011121314151617181920212223242526272829303132RATE = 2.0def trunc(y)return y.round(7)enddef pout(x, y)puts "Case ##{x}: #{trunc(y)}"enddef solve_rec(c, f, x, r, t)return t + (x/r) if x <= c || (t + c/r + x/(r+f)) >= (t + x/r)t += c/rr += fsolve_rec(c, f, x, r, t)enddef solve_itr(c, f, x)t, r = 0.0, RATEreturn x/r if x <= cwhile (t + c/r + x/(r+f)) < (t + x/r)t += c/rr += fendt + x/rendgets.to_i.times do |i|c, f, x= gets.split.map(&:to_f)# pout(i+1, solve_rec(c, f, x, RATE, 0.0))pout(i+1, solve_itr(c, f, x))endDeceitful War
This one was really subtle, easy enough to understand but hard to implement. It took me a while to put my understanding of how much being deceitful at the game called War translated to my points. Here too I solved both the normal game War and Deceitful War recursively first (it’s just easier to think recursively thanks to Lisp), then translated those to their iterative counterparts. Here is my solution with both recursive & iterative parts :
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061def pout(i, x, y)puts "Case ##{i}: #{x} #{y}"enddef pick_kn(kb, nbs)kb.find do |kbi|kbi > nbsend || kb.firstenddef solve_war_rec(nb, kb, s)return nb[0] > kb[0] ? s + 1 : s if nb.size == 1 && kb.size == 1nbs = nb.shiftkbs = kb.delete(pick_kn(kb, nbs))s += nbs > kbs ? 1 : 0solve_war_rec(nb, kb, s)enddef solve_war_itr(nb, kb)return nb[0] > kb[0] ? 1 : 0 if nb.size == 1 && kb.size == 1s = 0while nb.size > 0 && kb.size > 0nbs = nb.popkbs = kb.delete(pick_kn(kb, nbs))s += nbs > kbs ? 1 : 0endsenddef pick_dkn(kb, nbs)kb.select do |kbi|kbi < nbsend.last || kb.firstenddef solve_dwar_rec(nb, kb, s)return nb[0] > kb[0] ? s + 1 : s if nb.size == 1 && kb.size == 1nbs = nb.popkbs = kb.delete(pick_dkn(kb, nbs))s += nbs > kbs ? 1 : 0solve_dwar_rec(nb, kb, s)enddef solve_dwar_itr(nb, kb)return nb[0] > kb[0] ? 1 : 0 if nb.size == 1 && kb.size == 1s = 0while nb.size > 0 && kb.size > 0nbs = nb.popkbs = kb.delete(pick_dkn(kb, nbs))s += nbs > kbs ? 1 : 0endsendgets.to_i.times do |i|gets.to_inb = gets.split.map(&:to_f).sortkb = gets.split.map(&:to_f).sort# pout(i+1, solve_dwar_rec(nb.clone, kb.clone), solve_war_rec(nb.clone, kb.clone))pout(i+1, solve_dwar_itr(nb.clone, kb.clone), solve_war_itr(nb.clone, kb.clone))end