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.
Post a Comment