ploh wins Room 2

by lbackstrom,
TopCoder Member
Thursday, March 10, 2005

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.

Shouting

For a given shouting distance, we can compute whether everyone can reach everyone else in O(N^3) with Floyd-Warshall. There are N*(N-1)/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.

Switching

To 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:

• Process i was running at the end of the previous tick
• A process that recorded the current tick was running at the end of the previous tick
• A process that did not record the current tick was running at the end of the previous tick.

These three cases require n, n-1 and n switches, respectively, where n is the number of processes that record the tick. There is a special case when there is only one process that runs during the current tick, and it was also the last process running during the previous tick.

ChartError

One 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*c-val[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.