UTICPC Take 2 Judge's solutions (and non-solutions)

Updated September 21, 1997
New (September 21, 1997): I solved the mystery of question 4.



Well, wasn't that exhilirating! Twenty-nine teams competed in the second (and increasingly inaccurately named) University of Toronto Inter-Campus Programming Contest. That's more than twice the number involved in the first UTICPC.

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.


Most of the solutions were presented in C or C++. However, newbie Java and oldie Turing had their own significant ``market'' share of solutions. Again, nobody used Pascal. (We've been keeping Pascal because the ACM contest keeps it.)

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... :-)


There were technical problems with the contest this time around. Question 2 (From My Canoe to You) was underspecified, and my solution for question 4 (Balance the Books) was wrong. (Well, not quite: see below.) Both problems were fixed during the contest. Prior submissions for question 2 were rejudged manually, and I believe the same was done for question 4. (Honestly, I was too busy to tell if all the question 4's were rejudged.)

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. :-)

Solutions (and non-solutions)

The consensus at the contest appeared to be that this UTICPC was more difficult than the first one. I guess so. On the mailing list I objected to the statement that the UTICPC was a watered down version of the ACM contest, even though I'm probably the one who first said it last fall. Instead I now make the comparison:
ACM contest is to vodka as UTICPC is to strawberry daquiri.

Here are my solutions and non-solutions, together with their descriptions.

  1. Finding utopia

    This question requires a small piece of analytic geometry. It requires no data structures to speak of. I think the C source speaks for itself.

    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

  2. From My Canoe to You

    I underspecified the question. There is more than one solution to the sample input. Things are fixed if we add the condition that the path not cross itself, or if we say that one full traversal of the path (and return to home base) does not turn left more than 360 degrees. Both extra conditions were broadcast during the contest, and previous submissions judged incorrect were rejudged manually.

    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

  3. Turing (yes Turing!)

    Wayne Hayes suggested this question. I balked at the idea until I looked the Turing program he wrote a few years back to solve the problem. It looked reasonable enough, so I simplified the specs slightly and wrote my own program to solve the new problem.

    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

  4. Balance the books

    Perhaps I cursed myself by being a bit too cheeky with this one. You see, there is some dispute in real life over the neutrality of the exchange of governmental responsibilites. I guess we all have to think twice (or ten times maybe).

    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.

  5. Ligature processing

    Back to normality. This is essentially the scheme Donald Knuth used for ligatures in TeX, up until about 1989. He then extended it for easier support of more languages. To find out more, see pages 316--317 of The MetafontBook, the source code for TeX in TeX: The Program, or his invited talk Theory and Practice.

    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

  6. Farmer Bill's FenceBuilder98

    This question is inspired by some clever data structures used in graphics programs. In paticular, Knuth's Metafont, and Bill Atkinson's QuickDraw implementation for the first Macintosh use the vertical strut idea to represent and manipulate two-dimensional monochrome images in less space and time than you might expect.

    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.

    input 0 and output 0


Well, that's all, folks. I hope everybody had a good time. See you in January? We're taking applications for question-makers, question-checkers, and judges... :-)

And remember, the ACM Programming Contest is coming up. The wheels are turning. Charles Clarke is the faculty advisor.

David Neto / neto at cs utoronto dot ca