Once again many volunteers put this together. I commend Evelyn Hsia for coordinating the rest of us, Albert Lai for his judging and his calm and effective handling of the contest software, and Susan Sim and Charles Clarke for their willingness to be recruited on-the-spot for debugging my questions and manually rejudging some of the submissions.
Java poses an interesting problem for judges because its libraries make certain things very easy in comparison to other languages. I'll let you figure that out what those things are... :-)
Of course, it still means teams were unfairly penalized and lost time chasing down my bugs. That's unfortunate, and I apologize. However, this kind of thing has happened at the ACM contest at the regional level. (Just ask.) At least the stakes at the UTICPC are lower. :-)
ACM contest is to vodka as UTICPC is to strawberry daquiri.
Here are my solutions and non-solutions, together with their descriptions.
utopia.c -- my C solution.
input 0 and
output 0 -- the sample input
input 1 and
output 1 -- the sample input with permuted
searchers
input 2 and
output 2 -- the sample input reflected in the
origin
input 3 and
output 3 -- nobody sees Utopia; the output
is an empty file
Yes, I was trying to specify that the points always lie on a convex hull, and that you were to give counter-clockwise convex hull ordering with the origin first. I just didn't want to say those words. Besides, even if I did, I'd have to define a convex hull anyway...
Even with all the problems in the question, most of the solutions judged as wrong were clearly wrong, e.g. repeating the origin or not specifying the origin first, or giving the wrong number of numbers, or giving coordinates that were not in the input.
My C solution works as follows. Find a westernmost point, w. Now find the angle above eastward that each of the other points make with w. (Use atan2 or related functions for this.) These values lie between -PI/2 and PI/2. Sort the points by this angle (taking w's angle as -200 radians). Then print out the points, making sure the origin comes first.
Some solutions used an interior point of the hull. That's ok, but you must watch out for the domain of atan2. I don't know if those people got caught by this.
input 0 and
output 0 -- a unit square
input 1 and
output 1 -- a very thin triangle on an angle
input 2 and
output 2 -- the sample input
input 3 and
output 3 -- six points on a thin convex angled
hull
input 4 and
output 4 -- another very thin triangle, testing
input boundaries
The program is much shorter than the specification, but the devil is in the details. That's why the spec is so long. Even so, I had to clarify during the contest that if a transition has an accepting ``next state'' but also would force the head off the left end of the tape, then the machine rejects. I went back to my source to see what it would do -- the test data doesn't test exercise this detail.
Turing machines can be specified in many different ways. The one specified here is slightly simpler than the one usually taught to unsuspecting undergrads in CSC 364 (that one is infinite in both directions) and uses any finite tape alphabet. If you remove the limit on the tape length, then the Turing machines specified in this question are as powerful as any other.
My C source is rather short because it uses a fixed-length character array as the tape. For the most part, the variable names match the symbols in the spec.
input 0 and
output 0 -- sample input 0; div4 accept case
input 1 and
output 1 -- sample input 1; div4 reject case
input 2 and
output 2 -- div4 accept on a longer input
input 3 and
output 3 -- div4 reject on a longer input
input 4 and
output 4 -- scan and bump by 1 modulo d and
always accept, d = 3
input 5 and
output 5 -- step left right away (and therefore
reject immediately). Notice the input to the machine has four digits, and
they must be printed out, even if the head didn't pass over some of
them.
input 6 and
output 6 -- recognize palindromes over 0 1 2;
even length accept
input 7 and
output 7 -- recognize palindromes over 0 1 2;
odd length accept
input 8 and
output 8 -- recognize palindromes over 0 1 2;
even length reject
input 9 and
output 9 -- recognize palindromes over 0 1 2;
odd length reject
The question asked here is very closely related to the NP-complete partitioning and bin packing NP-complete. But we're saved here because the answer is bounded over all inputs. So, technically speaking, the dynamic programming solution runs in linear time. :-).
A free lunch goes to to the first person who tells me why my Perl (non)solution is buggy. (Wait! See below.) I've left in the debugging output. Unfortunately, I used it to generate the test output...
After receiving many solutions that disagreed with mine, I wrote the solution again, this time in C. Again, its debugging output is enabled. It's easier to understand than the Perl program (are you surprised?), and it works as follows. Entry m[i] is true if and only if there is a way to sum up to value i using municipal values only, and false otherwise. Array p is the corresponding array for provincial values. Initially, only entries 0 are true. For each new value on the input, we update the appropriate array by scanning from the high indicies to low indices, marking all sums that use the current value and together with an old sum. You have to go from high indices to low indices, otherwise you will use a value multiple times. Once the arrays are built, scan for the largest sum that is enabled in both.
Yes, I don't check the bounds on the array updates, but I had to do it fast, and I knew what the data looked like. :-)
input 0 and
correct output 0 and
my Perl output 0 -- sample input
input 1 and
correct output 1 and
my Perl output 1 -- delay scores from
first UTICPC, with names mangled; I thought this would force an answer of
0
input 2 and
correct output 2 and
my Perl output 2 -- delay scores from
first UTICPC, with names mangled and padders; I thought this would force a
non-trivial result
input 3 and
correct output 3 and
my Perl output 3 -- like input 2, but with
permuted lines
Stop the presses! (September 21, 1997) I figured out what was going on. It turns out my Perl script is basically right, but that my test data was bad. Instead of EpsilonO, I originally had Epsilon0. For the sharp-eyed, that's a zero (0) on the end of the original line instead of a capital Oh (O). The spec says the names of the responsibilites are alphabetic-only, and so the Perl script rejects the line. The C program doesn't check, and accepts the line. That accounts for the discrepancy between the answers provided by the two programs.
So, I apologize for using bad data... The Perl script on the corrected data gives the same answers as the C programs. So what should the answers really have been? You tell me. Oh, and now I get to take myself out to lunch.
During the contest I stipulated that there would be at most 50 substitutions in a ligature table.
I sort of ``cheated'' because my solution is in Perl. I used Perl's associative arrays to look up substitutions. Notice that a ligature can't span a newline, so we may as well go line by line. Each line is broken up into characters and we treat it as a minimal stack. We pop two items off the stack, see if they form a left-hand side of a substution, and if so, push the corresponding right-hand side onto the stack. Otherwise, print the first item and push the second item back onto the stack.
input 0 and
output 0 -- sample input 0
input 1 and
output 1 -- no substitutions made
input 2 and
output 2 -- a cheeky message. This example
demonstrates that quite general substitions are possible with this ligature
mechanism
My Perl solution is a scanline algorithm, working as follows. Simulate the tractor, remembering its current position. Record the positions of north-south sections of fence in bins indexed by the y coordinate. At the end of a run, we process each of the bins (scanlines) as follows. Sort the vertical (north-south) sections of fence in a bin by x coordinate. Now, sum up the horizontal distances between consecutive pairs of fence sections in that bin. Do the same for all the bins and add up the results. This works in roughly O(n log n) time, slowed down by the sorting.
There was an ingenious early submission for this question. I looked at the source code and said to myself ``That's too short to be right'' and was amazed when it did work. It's very short and works in linear time (counting an arithmetic operation on an integer as constant time). (I'll post if I get the team's permission.)
For this question, all the test data fits in one file. The first two are the sample inputs. The next three are a few of the first iterations in Moore's space-filling curve, a ``cyclic'' variant of Hilbert's space-filling curve; see the book Space Filling Curves by Hans Sagan. It's in the Sig Sam library. I manually checked the solutions to all but the last one.
And remember, the ACM Programming Contest is coming up. The wheels are turning. Charles Clarke is the faculty advisor.