Match Editorial

Match summary

The TopCoder Open 2007 started for Algorithm competitors with Qualification Round 1. This round -- the first of three chances to qualify for Online Round 1 -- attracted several very high-rated competitors who were ineligible for a bye. Thanks to a great challenge phase, SuperMutant won this tough competition. bjoeris, thanks to the fastest hard problem, finished second. cyfra, TopCoder Open 2006 finalist, finished third, followed by Crush and TopCoder veteran dgarthur, who rounded out the top five.

The Problems

Value	250
Submission Rate	996 / 1058 (94.14%)
Success Rate	753 / 996 (75.60%)
High Score	anikov for 248.50 points (2 mins 12 secs)
Average Score	215.54 (for 753 correct submissions)

Since the segments are horizontal or vertical and not adjacent to other segments, the fact that the drawing shows one connected snake may be nice for the snake but is no help in finding the longest segment. We just need to find the longest horizontal or vertical sequence of 'x's.

One brute force approach is to consider every position in the picture as a possible starting point of the longest segment (leftmost or topmost) and count in that direction until the edge of the picture is reached or a '.' is encountered. Then return the maximum among all those counts.

Another approach is to check each row for consecutive sequences of 'x'. Do the same thing for each column and report the biggest result. Here is pseudocode for checking each row that handles all horizontal segments (whether or not they start/end at the boundary).

max=0
for each row r
         count = 0
         for each column c
             if snake[r][c] is '.'
                 count=0
             else
                 count++
                 max = maximum(max,count)

Value	500
Submission Rate	807 / 1058 (76.28%)
Success Rate	727 / 807 (90.09%)
High Score	murphydog for 474.12 points (6 mins 42 secs)
Average Score	331.15 (for 727 correct submissions)

I really do have a friend with this clock, but power usage is not really much of an issue.

This problem is easiest to do by simply walking through each time from tStart to tEnd. For each time we count the number of bulbs that are on and keep track of the sum.

To walk through all the times we can keep track of hour, minute, and second in variables. To advance to the next time just add one to second. If that results in 60, set second to 0 and add one to minute. If that results in 60, set minute to 0 and add 1 to hour. If that results in 13 set hour to 1.

int[] bulb = {0,1,1,2,1,2,2,3,1,2} captures all the information needed to count the bulbs for any digit. At each time increase the sum by bulb[hour%10]+bulb[hour/10]+ ... Stop when hour, minute and second match tEnd. Finally, multiply the sum by the appropriate conversion factor ( 1.0 / 3,600,000 ).

Value	1000
Submission Rate	133 / 1058 (12.57%)
Success Rate	35 / 133 (26.32%)
High Score	bjoeris for 681.25 points (21 mins 41 secs)
Average Score	461.57 (for 35 correct submissions)

For any noise level A, each sensor has a circular region into which the intruder cannot go. There is a path from the entrance to the exit if and only if there is NO chain of overlapping circles that goes from the east side of the room (including the southeast and northeast) to the west side of the room.

Since the bigger A is the bigger of the circles, we can do the problem by bisection. The critical value of A must lie between 0 and 100*100*10,000 based on the constraints. When a value for A has circles big enough to form a chain that value becomes the upper limit; otherwise it becomes the lower limit for the critical value of A.

So we just need to solve the sub-problem of finding whether there is a chain of circles from east to west for a given value of A. For each of the n sensors the radius of detection is square_root(A/ threshold[i]). We can solve this with a breadth-first search. First find all the sensors whose circles overlap the east/northeast/southeast wall and mark them. Then mark all circles that overlap a marked circle. Continue until no more progress is made. If any of the marked circles overlap the west/northwest/southwest wall then there IS a chain.