Match Editorial

In only 12 minutes, ante joined 99 other coders in securing his spot in the Collegiate Challenge. Although the easy problem was cake for most coders, only 23 were able to solve a mildly difficult level two problem. Most everyone who solved the level two did it through brute force, but there turns out to be a quick polynomial time algorithm to solve it. Since there isn't much to tell in a play by play, I'll get right to the problems.

The Problems

Value	250
Submission Rate	124 / 132 (93.94%)
Success Rate	107 / 124 (86.29%)
High Score	cnettel for 245.73 points (3 mins 0 secs)
Average Score	203.97 (for 107 correct submissions)

In this problem, you are to aim a large gun at incoming targets, which can only be destroyed at specific coordinates at specific times. Your job is to shoot them down in order, returning the first target that you are not able to shoot down. Of course, you can't skip any of them either.

The distance between two coordinates is what is called the "manhattan distance", and seems to be a regular theme in recent problems. This is the sum of the distance between the x coordinate and the distance between the y coordinate, similar to the distance required to travel between two intersections in a large city laid out on a grid. In any case, the best method to solve this problem is to keep track of the current time and x/y coordinates of the turret, check to see if it can be moved to the next target. If the target cannot be reached, return that target's index. If the target can be reached, move the turret to those coordinates, and wait there until the target arrives. This amounts to setting the turret coordinates and the current time to the target's parameters.

Value	550
Submission Rate	52 / 132 (39.39%)
Success Rate	23 / 52 (44.23%)
High Score	ante for 495.34 points (7 mins 43 secs)
Average Score	302.29 (for 23 correct submissions)

In this problem, we are given sets of numbers, which we must use with union and complement operations to form as many sets as possible. The limits in this problem give us a saving grace -- there are only 10 possible elements in a set. If we treat the presence of any element in U as a bit in an integer, we have at most 2¹⁰, or 1024 sets. Therefore, we can process each set in the order it was added to see if more sets can be added.

The first stage of the code is to process the input parameters. Use your favorite tokenizing function (strtok, istringstream, StringTokenizer, etc.) and split each element into individual numbers. Each set can be represented by an integer, where bit N is set if the value N+1 is present in the set. It is important to subtract one from the values, because we want all the lower order bits to be used. After this, we add all the input sets to a queue.

The second stage is processing the queue, and using a BFS to find all the sets. For each value that is in the queue, we try its complement first. Then we try a union between it and every element that was in the queue before it. This way, we only will process O(2²ⁿ) iterations. For n = 10, this is about a million iterations. For each union and the complement, we check if the new set has been seen before, and if it hasn't, mark it as seen and add it at the end of the queue. Another method is to repeatedly process all sets currently in the field, taking the union against all other sets in the field, stopping when no new sets can be formed. This has a much larger run time, but still works because of the low constraint size. See ante's solution for an example.

The above algorithm works for a small number of sets, but there is also an algorithm which can solve the problem in O(n*m) time, where n is the number of values, and m is the number of input sets. First, we can observe that with ANY set input, we can always acheive the empty set. If we have set A, we know U = A union ~A (where ~ denotes complement). We can acheive the empty set with ~U.

We also can prove that the intersection of two sets A and B (the set of elements which are in both A and B) is acheivable through only union and complement operations using De Morgan's law:
A intersect B = ~(~A union ~B)

Now, we will define the minimal subset of i to be the smallest set of values for which i ALWAYS appears with in any of the input sets. This could be simply i by itself, or it could have other elements. For each element in the input, if the input contains the element i, we use it, otherwise we use the complement. Using these sets, we can repeatedly intersect all of them together until we get the minimal subset. This set of minimal subsets have no elements in common, because if they did, there would be a case where some of the original input elements intersected together formed a smaller minimal set. In addition, we have a minimal subset for every single value in U. Using these minimal subsets, we can form all the original input sets, and using the original input sets, we can form all of the minimal subsets, making it equivalent to substitute the minimal sets as the input. Using the minimal sets, it is possible to use the method above to form the empty set. Then, if we treat each set as a bit in a bit-field, we can form 2ⁿ sets using the union operation, were n is the number of minimal subsets. Using complement doesn't matter because the complement of one set of minimal sets is the same as using union for all the minimal sets that weren't used. Therefore, there are exactly 2ⁿ sets that can be formed from these minimal sets using only union and complement. Therefore, the answer to the problem at hand is 2ⁿ. We can determine the minimal subsets in O(n*m) time (n is the size of U, and m is the number of input sets), and then determine the answer in constant time.

Thanks to Ryan for help on writing this proof