
Match Editorial 
2007 TopCoder Open
Qualification Round 1 Thursday, March 29, 2007
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 highrated 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
Snaky Used as: Division One  Level One:
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)
Bigital Used as: Division One  Level Two:
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 ).
Alarmed Used as: Division One  Level Three:
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 subproblem 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 breadthfirst 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.
By
dgoodman
TopCoder Member