Anhang's Contemplations

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.