Google Code Jam 2014 Qualifiers

dhruvasagar

2014-04-14

4 min read

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(1) (1)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 :

def get_ans
    gets.to_i
end

def get_arr
    arr = []
    4.times do
        arr << gets.split.map(&:to_i)
    end
    arr
end

def get_ans_arr
    [get_ans, get_arr]
end

def pout(x, y)
    puts "Case ##{x}: #{y}"
end

def solve(a1, arr1, a2, arr2)
    int = arr1[a1-1] & arr2[a2-1]
    case int.size
    when 0
        'Volunteer cheated!'
    when 1
        int[0]
    when 2..4
        'Bad magician!'
    end
end

gets.to_i.times do |i|
    a1, arr1 = get_ans_arr
    a2, arr2 = get_ans_arr
    pout(i+1, solve(a1, arr1, a2, arr2))
end

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 :

RATE = 2.0

def trunc(y)
    return y.round(7)
end

def pout(x, y)
    puts "Case ##{x}: #{trunc(y)}"
end

def 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/r
    r += f
    solve_rec(c, f, x, r, t)
end

def solve_itr(c, f, x)
    t, r = 0.0, RATE
    return x/r if x <= c

    while (t + c/r + x/(r+f)) &lt; (t + x/r)
        t += c/r
        r += f
    end
    t + x/r
end

gets.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))
end

Deceitful 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(2) (2)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 :

def pout(i, x, y)
    puts "Case ##{i}: #{x} #{y}"
end

def pick_kn(kb, nbs)
    kb.find do |kbi|
        kbi > nbs
    end || kb.first
end

def solve_war_rec(nb, kb, s)
    return nb[0] > kb[0] ? s + 1 : s if nb.size == 1 && kb.size == 1

    nbs = nb.shift
    kbs = kb.delete(pick_kn(kb, nbs))
    s += nbs > kbs ? 1 : 0
    solve_war_rec(nb, kb, s)
end

def solve_war_itr(nb, kb)
    return nb[0] > kb[0] ? 1 : 0 if nb.size == 1 && kb.size == 1

    s = 0
    while nb.size > 0 && kb.size > 0
        nbs = nb.pop
        kbs = kb.delete(pick_kn(kb, nbs))
        s += nbs > kbs ? 1 : 0
    end
    s
end

def pick_dkn(kb, nbs)
    kb.select do |kbi|
        kbi < nbs
    end.last || kb.first
end

def solve_dwar_rec(nb, kb, s)
    return nb[0] > kb[0] ? s + 1 : s if nb.size == 1 && kb.size == 1

    nbs = nb.pop
    kbs = kb.delete(pick_dkn(kb, nbs))
    s += nbs > kbs ? 1 : 0
    solve_dwar_rec(nb, kb, s)
end

def solve_dwar_itr(nb, kb)
    return nb[0] > kb[0] ? 1 : 0 if nb.size == 1 && kb.size == 1

    s = 0
    while nb.size > 0 && kb.size > 0
        nbs = nb.pop
        kbs = kb.delete(pick_dkn(kb, nbs))
        s += nbs > kbs ? 1 : 0
    end
    s
end

gets.to_i.times do |i|
    gets.to_i
    nb = gets.split.map(&:to_f).sort
    kb = 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

Google Code Jam 2014 Qualifiers

Magic Trick #

Cookie Clicker Alpha #

Deceitful War #