Get Time
statistics_w  Match Editorial
2003 TopCoder Collegiate Challenge
Round 1 - NE and SE Regional

Tuesday, February 18, 2003


The first problem set of the collegiate challenge turned out to be a little bit trickier than previous first round problem sets have been, though still easier than the average division 1 problem set. Only 191 people competed from the two regions, and of those only 113 ended up with positive points - 78 from the northeast, and 35 from the southeast. dgarthur was able to complete all three of the problems in an impressive 35 minutes, and with 50 points from the challenge phase, he easily took first. In second, 160 points behind, is insomnia, with 4 successful challenges. Good luck to everyone in the next round!

The Problems

NameSort  discuss it
Used as: Level 1:
Submission Rate160 / 191 (83.77%)
Success Rate98 / 160 (61.25%)
High ScoreColinMacLeod for 239.72 points

Sorting can be done in a variety of ways. The simplest way to implement it in this case, where runtime is not an issue, is probably to simply use two loops:

for i = 1 to n
    for j = 1 to i-1
        if(element i should come before element j)
            swap elements i and j
To tell if one element should come before another, you simply have to tokenize each element, and compare the final tokens, ignoring case. If there is a tie, you need to know the original index, so you should probably keep track of the indices and swap them along with the elements.

RoadWork  discuss it
Used as: Level 2:
Submission Rate89 / 191 (55.28%)
Success Rate46 / 89 (51.69%)
High Scoreniteneb for 471.50 points

If the roads were shorter, it would be easy to iterate through each one foot section of road, and check to see if it is included in multiple contracts. However, since the roads are up to 2 billions feet long, this is clearly not an option. Instead, we should divide the roads into a number of segments, and then determine if each segment is contained within multiple contracts, and then add the length of the whole segment, if it is all covered by multiple contracts. The trick is to pick the segments so that the whole segment is guaranteed to be covered by the same number of contracts. One simple way to do this is to add all of the points in start and end into one array, and sort that array. The segments of interest will now be defined as the region between adjacent elements in the array. It should be clear that there is no way for only part of one of these segments to be covered by multiple contracts. Now that way have defined our segments, it is simple to test each of the segments to see if it's covered:

all = union(start,end)
ret = 0
for i = 0 to all.size-2
    count = 0
    for j = 0 to start.size-1
        if(start[j]<=all[i] && end[j] >= all[i+1])
            count = count + 1
    if(count > 1)ret = ret + all[i+1]-all[i]

TupleLine  discuss it
Used as: Level 3:
Submission Rate20 / 191 (10.47%)
Success Rate12 / 20 (60.00%)
High Scoredgarthur for 708.62 points

Like any line, a line here is defined by two points. As a result, the simplest way to do this is to pick two points, and examine the line defined by those two points. The first thing to check is that the line is maximal. This is probably the hardest part of the problem, but it is not very algorithmically difficult. First, you should find the distance tuple between the two points. Each non-zero element of distance tuple should have the same absolute value. If this is not the case, then the two points cannot lie along a maximal line. For example, (0,0) and (1,2) cannot lie along a maximal line because the slope of the line is 2, and thus when the line traverses an n by n box, it will hit only n/2 cells. Once you have done this, you still have to check that the length of the line is the same as the size of the box. For example, if the size of the box is 3, and two points are (0,1) and (1,2), the line through them does not include 3 points, only 2. One way to do this is to generate all of the points along the line, and count them. There are other ways to do this too, but generating the points is probably a good way to do it, since this lets you count the total points easily. Once you have generated the points along the line, you simply iterate through all of the points and count how many were given to you. AdminBrett wrote the shortest solution I have seen, though it takes a minute to see how it works:

public class TupleLine {
public int quickLine(int size, String[] chosen) {
    int ret = size-1;
    for (int i = 0; i < chosen.length; i++) {
        for (int j = i+1; j < chosen.length; j++) {
            int[] curri = new int[chosen[j].length()], currj = new int[curri.length], diff = new int[curri.length];
            int div = 1000, cntused = 0, cntunused = 0;
            for (int x = 0; x < diff.length; x++) {
                curri[x] = chosen[i].charAt(x)-'0';
                currj[x] = chosen[j].charAt(x)-'0';
                diff[x] = curri[x]-currj[x];
                while (diff[x]%div!=0) div--;
            } for (int x = 0; x < diff.length; x++) diff[x] /= div;
        outer:   for (int x = -10; x <= 10; x++) {
                int[] temp = (int[])diff.clone();
                for (int y = 0; y < temp.length; y++) {
                    temp[y] = curri[y]+x*temp[y];
                    if (temp[y] >= size || temp[y] < 0) continue outer;
            outer2:   for (int y = 0; y < chosen.length; y++) {
                    for (int k = 0; k < temp.length; k++)
                        if (chosen[y].charAt(k)-'0'!=temp[k]) continue outer2;
                    continue outer;
            if (cntused+cntunused==size && cntunused < ret) ret = cntunused;
    return ret;
By lbackstrom
TopCoder Member