


ploh wins Room 2 by lbackstrom,
Im2Good, the only Java coder in the round, started out fastest submitting the first two problems in 25 minutes. He was also the first to submit the third problem, but ploh and overwise were faster, and overtook Im2Good when they submitted. John Dethridge, the favorite to win, ended up in fourth place going into the challenge phase. During the challenge phase, no one was able to find any bugs, so ploh retained the lead going into the system tests. As the tests rolled out, overwise and AdrianKuegel failed their hard problems, while Im2Good failed the medium. ploh's submissions all survived though, and he beat second place John Dethridge by a wide margin. Im2Good was the only other coder to solve the hard problem, so he will also move on to the wildcard round.
ShoutingFor a given shouting distance, we can compute whether everyone can reach everyone else in O(N^3) with FloydWarshall. There are N*(N1)/2 pairwise distances between the different points. Trying each of those distances as the shouting distance will result in an O(N^5) algorithm, which should run in time for N=50.SwitchingTo compute the fewest switches that could occur overall, you can solve the subproblem of determining the fewest switches that could occur up to the end of a particular tick, given that a particular process is running at the end of the tick. To compute this you can use dynamic programming. For a particular tick, compute the number of processes that recorded that tick. Then, if process i is going to be the process that runs last at the current tick there are three cases to consider:
ChartErrorOne way to compute the minimum chart error is to try bar_values that minimize the error between a pair of bars of particular sizes. The bar_value that gives the overall minimum will be one of the bar_values that minimizes the error for a pair of bars. If we pick a bar_value of x, the error for a particular bar is abs(x*cval[i]), where c is the number of 'X's in the bar. To find the values of x and c, you simply iterate over the the total number of 'X's in the pair of bars. The value of x is (val[i]+val[j])/k, where k is the number of bars in the pair of bars. See ploh's solution for a simple implementation of this. 
