Match Editorial

The final round of the TopCoder Charity Challenge saw a number of TopCoder's best vying for one of the 4 spots at the CRPF ball. The 300 point problem proved to be little trouble for many members, with John Dethridge submitting first, after about 8 minutes. But, his lead was short lived as po submitted the 575 pointer first. Going down the stretch though, hamster was in the lead, submitting all 3 problems first. However, a bug forced him to resubmit his 1000 pointer, and jms137, despite a slow start on the 300 and 575, came roaring back with a dominant 1000 score. The challenge phase was pretty dull, as only one problem was successfully challenged. However, that was not for lack of bugs, as the system tests wiped out many of the 575 and 1000 point submissions. At the end of the match, it was jms137 who won by over 100 points, thanks to his impressive 1000 score. Congratulations to jms137, John Dethridge, po and hamster.

The Problems

Value	300
Submission Rate	37 / 42 (88.10%)
Success Rate	37 / 37 (100.00%)
High Score	John Dethridge for 279.87 points (7 mins 43 secs)
Average Score	216.33 (for 37 correct submissions)

TopCoder's always been on the cutting edge, and this week they unveiled their brand new, 3D monitors complete with 3,145,728 lasers. Well, not quite, the 3D monitors are still in the simulation stage. We are given a number of points in 3D space, and asked to determine first if it is possible to have only those points lit up, and if it is possible, how many lasers are required to be turned on. The first step in this problem is to create 3 sets of lasers, one set for lasers orthogonal to the XY plane, another for the YZ plane, and a third for the XZ plane. Then, for each point, we can add a laser to each of the 3 sets, one with the same X and Y coordinates, one with the same Y and Z coordinates and one with the same X and Z coordinates. Then, we have to check and make sure all those lasers wouldn't light up any points not in the input. To do this, we basically just check all triples of lasers, each of which is from a different plane:

    foreach laser (X1,Y1) in XY
        foreach laser (Y2,Z1) in YZ
            foreach laser (X2,Z2) in XZ
                if(X1==X2 && Y1==Y2 && Z1==Z2 && (X1,Y1,Z1 is not in the input)
                    return -1;
                end if
            end for
        end for
    end for
    return XY.size()+YZ.size()+XZ.size();

Value	575
Submission Rate	18 / 42 (42.86%)
Success Rate	9 / 18 (50.00%)
High Score	po for 456.24 points (15 mins 21 secs)
Average Score	383.70 (for 9 correct submissions)

A* is a classic AI search method that uses a heuristic to improve upon the standard Djikstra's algorithm. It turns out that as long as the heuristic is optimistic, meaning that its estimate is less than or equal to the actual distance to the goal, A* will find the optimal path. The most standard way to implement A*, and other breadth first search methods, is to use a heap. A heap allows you to insert, update and remove locations in O(lg n) time, which is usually pretty fast. Each language has some class which will do most of the work for you, though you will probably have to at least write a comparator method. In C++, you can use the priority queue template, and Java's TreeSet can be easily adapted.

However, in this problem, the input was small enough that you didn't really need to have fast operations. In fact, you could probably search over each location to find the one with the lowest estimate, and then expand that one, and repeat. Since there are at most 2500 locations, this means that you need to look at 2500 locations in the search, and you have to do this 2500 times. 2500^2 = 6,250,000, which is getting close to the 8 second time limit, but usually is small enough. Another method that you could use, without a priority queue, and that would be pretty fast is to maintain a set of locations for each possible estimate (The worst case estimate is 7500). So, in pseudocode, we'd do this as:

    set s[7500];
    s[manhattan(goal,start)].add(start);
    int est[2500][2500]={0};
    int actual[2500][2500]={0};
    for(int i = 0; i<=est[goal_x][goal_y]; i++){
        for each location loc in s[i]{
            for each location adj adjacent to loc{
                if(est[adj_x][adj_y] != 0){
                    s[est[adj_x][adj_y]].remove(adj);
                }else{
                    est[adj_x][adj_y] = INF;
                    actual[adj_x][adj_y] = INF;
                }
est[adj_x][adj_y] = min(est[adj_x][adj_y], est[loc_x][lox_y]+dist(loc,adj)+manhattan(adj,goal));
                actual[adj_x][adj_y] = min(est[adj_x][adj_y], est[loc_x][lox_y]+dist(loc,adj));
                s[est[adj_x][adj_y]].add(adj);
            }
        }
    }

Value	1000
Submission Rate	14 / 42 (33.33%)
Success Rate	8 / 14 (57.14%)
High Score	jms137 for 800.95 points (14 mins 57 secs)
Average Score	500.62 (for 8 correct submissions)

Most coders who solved this one did so by using some sort of object to represent their sets. All of the languages have some sort of set utilities built in, and if you are familiar with these, they can make your life a lot easier in this problem. The first task is to parse the input string, which can be done using a standard recursive decent parser. Once you're done parsing, you really only need to be able to tell if something is an element of a set, and all of the other functions are pretty simple from there. So, in the following code, we will assume that we have two sets, A and B, and that we have a contains function, a size function, and that we can retrieve all of the members of a set easily.

    boolean isEquivalent(A,B){
        return isSubset(A,B) && isSubset(B,A);
    }
    boolean isSubset(A,B){
        foreach element elem of A{
            if(!B.contains(elem))return false;
        }
        return true;
    }
    boolean isProperSubset(A,B){
        return isSubset(A,B) && !isSubset(B,A);
    }
    boolean isPowerSet(A,B){
        if(A.size()==(1<<B.size())){
            foreach element elem of A{
                if(elem is atom || !subset(elem,B))return false;
            }
            return true;
        }
        return false;
    }
    boolean isEquipotent(A,B){
        return A.size()==B.size();
    }