Solutions and test data for UTICPC1997

Updated January 10, 1997

Here are David Neto's solutions for the Inaugural UTICPC. I've also included the test data used to judge the programs. In each case, these are a superset of the sample inputs and outputs.

I must emphasize that all the organizers worked hard to make this an enjoyable experience. In particular, I'd like to commend Wayne Hayes on the excellent job he did in managing the contest judging environment.

I wrote these programs as quickly as I could. Of course, I already knew the outline of the solution before I got down to coding. In most of these source files, I recorded the time I started typing in code as the first ``date'' line, and the time I finished debugging as the second ``date'' line. The text formatting question is an exception because after almost two hours of trying to solve my original question (format multiple paragraphs), I gave up and simplified the question instead to have only one paragraph per run.

You may want to use File-SaveAs-Text option for the test input/output, especially for the text formatting question. Then use od -a under UNIX.

The base names of the files do not all match the names of the question. But they are in the right order.

1. three.c -- The main trick is to notice that you don't have to perform the recursion all the way. Just do it once. The resulting number is no more than 10000.

Input: three.dat
Output: three.out

2. master.c -- Here's the O(n) solution. Scan from left to right, maintaining a stack of as-yet unclosed domains of mastery. To simplify things, I defined PINF as so-called positive infinity. (I never did need NINF which was negative infinity.)

Input master2.dat
Output master2.out

3. fact.c -- Count the number of times that the factor 5 appears in n!. This does it because there are always enough 2's to match up with the 5's.

Input fact.dat
Output fact.out

4. prime.c -- This is the Sieve of Eratosthenes. Keep a table of all the numbers from 2 to 100000 and mark off multiples of primes, where the multiplier is at least 2. Any unmarked position must be a prime. Be sure to build the entire table before processing any input, so that we don't waste time generating the primes multiple times for multiple inputs. Also, make sure that we count primes correctly. Program prime2.c is a minor ``optimization'' on prime.c.

Two teams wrote other programs that computed the primes, then printed them out and massaged that output to be a program which then was submitted. (In one case it was a 150K Turing program; in the other it was a similarly large C program.) Wayne and I discussed this for a while, and then decided that Rule 3 requires that all submitted code must be "typed" in during the contest, and that therefore these solutions were disqualified. This is the source of the starred entries in the score file. Sorry, but this kind of thing has a precedent: something similar happened to David Neto's team in an ACM regional contest in the fall of 1992. :(

Input prime.dat
Output prime.out

5. text.c -- This is all bookkeeping. :)

I also solved it in Turing, see text.t, just before the contest. (I hadn't written a Turing program in a long time...)

You don't know how many spaces to print until you know if you've hit the end of the input. So you have to buffer the output line in decomposed form. You must also copy each new word over, instead of just moving pointers, because sometimes the old data will get written over.

The number of spaces to be inserted in any particular gap can be computed very nicely by integer division and a remainder.

A common mistake was having extra spaces just before the final newline in the file. See the last line of the specification.

Input 2 text.dat was given
Output 2 text.out
Input 2 text2.dat was given
Output 2 text2.out
Input 3 text3.dat is a cleaned up version of the initial portion of /usr/dict/words
Output 3 text3.out
Input 4 text4.dat is an old version of the Latex file describing this question. In it, the output for the second sample case is incorrect. At that point I had a bug in my program. :)
Output 4 text4.out
Input 5 text5.dat is a single word. I apologize here because I had promised that c>10. But no rejections were made based on this alone.
Output 5 text5.out

6. worf.c -- The answer is always twice the least common multiple of n and k. I won't explain this fully until the next issue of MAT 007I appears.

Input worf.dat -- Note that the last line is not used because only 7 inputs are specified. I wanted to keep my promise that no answer would be more than 2 million, so that people who simulated the phaser blast would still have enough time if they weren't too inefficient in coding.
Output worf.out

Back to David Neto's Auxiliary UTICPC page