Match Editorial

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

Value	250
Submission Rate	160 / 191 (83.77%)
Success Rate	98 / 160 (61.25%)
High Score	ColinMacLeod 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

Value	500
Submission Rate	89 / 191 (55.28%)
Success Rate	46 / 89 (51.69%)
High Score	niteneb 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)
sort(all)
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]

Value	1000
Submission Rate	20 / 191 (10.47%)
Success Rate	12 / 20 (60.00%)
High Score	dgarthur 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;
                    cntused++;
                    continue outer;
                }
                cntunused++;
            }
            if (cntused+cntunused==size && cntunused < ret) ret = cntunused;
        }
    }
    return ret;
}
}