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.