1. Euphoria Programming Contest...
Hi all,
I am forwarding a message from Dr. Rob Kolstad <kolstad at bsdi.com> (without
askin
g for his permission) about a programming contest. He asked for solutions in Bor
land's Pascal or C++. The deadline has not passed yet (there is still a day or s
o). Dr. Kolstad has about five programming contests per year ( http://usaco.uwp.
edu/ ).
Really, I enjoy these kind of programming contests, and I would like to see one
that allows Euphoria solutions! 
As for the prizes, I am sure RDS can make a new webpage at their FilesEu webpage
about these contests and winners, and ship a copy of the registered Euphoria 2.
0 (or the last release) dual-platform release to the topscorer(s), along with th
e things that normally accompany it (e.g. the printed manual), for free. In retu
rn, this should make Euphoria more well-known to the world, and hopefully we wil
l soon have more than (insert maximum number of Euphoria's integer here) Euphori
a users. Of course, that means more people will subscribe this mailing list and
we will have more idea to discuss, so it would be a good idea to have the mailin
g list digest processor spit out digests every 6 hours instead of 24 (i.e. 4 dig
ests per day) or maybe more frequent
PS: If you have a nice solution for the following three problems in
Euphoria-for-DOS32 (that fits the time limit of 5 sec in 75 MHz Pentium
that translates to 2.82 sec in my 133 MHz Pentium), you can discuss it
with me or the list *after* the deadline of the contest, 0800 am US
Mountain Daylight Time (1400 GMT) Monday, April 13, 1998. I will not
score them but someone else might (The testcases are usually sent
to participants within 2 weeks after the deadline, so I will receive a
copy.) Note that no include file should be needed.
Forwarded message follows...
--
Return-Path: <owner-hs-computing at services.BSDI.COM>
Received: from services.BSDI.COM (services.BSDI.COM [205.230.225.19])
by play.gamerz.net (8.8.5/8.8.5) with ESMTP id BAA03442
for <akur at gamerz.net>; Thu, 9 Apr 1998 01:40:07 -0400
Received: (from root@localhost)
by services.BSDI.COM (8.8.7/8.8.8) id XAA29438;
Wed, 8 Apr 1998 23:38:36 -0600 (MDT)
Received: (from root@localhost)
by services.BSDI.COM (8.8.7/8.8.8) id XAA29378
Date: Wed, 8 Apr 1998 23:38:02 -0600 (MDT)
From: Rob Kolstad <kolstad at BSDI.COM>
Message-Id: <199804090538.XAA12090 at ace.BSDI.COM>
To: hs-computing at delos.com
Subject: US Open -- International Division
Sender: owner-hs-computing at BSDI.COM
Precedence: bulk
X-UIDL: 0d15ade580914528b81807d98a1dbcd3
USACO US Open -- International Division
April 9-13, 1998
Rules changes from 1996-1997 and other recent contests:
* C/C++ compiler will be Borland C/C++ 3.1 -- not 4.0
* Don't forget: input from INPUT.TXT; output to OUTPUT.TXT.
* Compiler options specified as {} for Pascal and #pragma for C
* Five consecutive hours for this contest -- one session only!
* No assistance: no books, no people, no e-mail, no internet
* For this contest, what-you-see-is-what-you-get
All the examples are intended to be correct and helpful.
These instructions and rules have not been proofread by a large number
of individuals. Please forgive typographical errors.
--------------------------------------------------------------------------
The international divison of the US Open is for `honor'. While we'll
award a plaque to the winner(s) and announce them on the web page, the
international division will be scored separately and reported separately
than the USA division, since it is a non-proctored event.
--------------------------------------------------------------------------
WHAT: The USA Computer Olympiad 1998 US Open International Division
is a computer programming contest open to all non-US resident
pre-college students throughout the world who have access to
the hs-computing at delos.com mailing list. Three problems are
presented for solution.
WHO: All non-US resident pre-college students who have access to the
hs-computing mailing list are eligible. This is an individual
contest, not a team contest.
WHEN: Problems will be posted to the mailing list just before
midnight April 9, 1998 US Mountain Daylight Time. All results
are due by 0800 am US Mountain Daylight Time (1400 GMT) Monday,
April 13, 1998. Late solutions will not be accepted.
WHERE: Students can work on problem solutions anywhere they wish,
including school or home.
HOW: Problems and rules are posted to the hs-computing mailing
list. Solutions must be written in Borland C/C++ or Turbo Pascal
and must be returned via e-mail by the contest completion
deadline.
Choosing a non-Borland Pascal compiler will probably cause a
solution to not compile on the judges' machines. After you have
completed the contest, feel free to take your final solution to
a Borland Pascal equipped machine to ensure it will work. Do
not charge this `repair' time against your coding time limit.
Choosing a non-Borland C/C++ compiler has a greater chance of
working out okay: make sure you use no library functions other
than those provided by the following header files (i.e., don't
#include anything but these files -- not all of which are
usually needed, of course):
assert.h io.h mem.h string.h
ctype.h iostream.h stdio.h values.h
fstream.h math.h stdlib.h
If you use an ANSI compiler and use (at most) only these headers,
your program should compile fine under our compilers. Remember
that we are running the judging under MS-DOS and are thus subject
to its memory requirements.
The specific compilers used are as follows.
* Turbo Pascal 7.0
* Borland C/C++ 3.1
PRIZES: Winner(s) will receive a handsome plaque and have their names
immortalized on the USACO Web Pages.
FEES: No entry fees are charged.
RULES: * No consultation with people is allowed.
* Do not work in a team environment.
* No consultation with written materials (such as programming
books) is allowed.
* No use of the internet for research or consultation is allowed.
* Solve all three problems in a single, contiguous five hour
session. No time-outs, no breaks: five straight hours, one
time only.
* Submit source code for the problems to the contest coordinators
via e-mail to usopen98 at delos.com (see below for format).
* Solutions will be judged for correctness by running them against
several (usually 6-15) different sets of input data. Points are
accrued for correct solutions. Some datasets for a problem will be
worth more points than others. Solutions to some problems will be
worth more points. Judging will be performed expeditiously but
could easily take two weeks to complete.
* Unless otherwise stated, your program must run no longer than
5 seconds for any test case on the judge's computer
(approximately 75 MHz Pentium).
* It is NOT guaranteed that all possible legal datasets will be
solvable within the time limit.
* The judges reserve the right to increase time limits during grading.
* Judges will not test all datasets against a program that crashes
the computer for initial datasets.
* Decision of the judges is final.
* Do not cheat; it's no fun for anyone.
* Do not use inline assembler statements.
* Don't submit programs that use data files that aren't supplied by
the contest coordinators.
* Don't use `temporary' data files.
* Keep in mind that this is neither a `tricky input' nor a
`tricky output' contest, in general. Input and output formats
are straightforward, though the input values may cause your
program difficulty.
* All problems are intended to be straightforward; no problems
are intended to have `tricks' in them. Some of them are,
however, challenging.
NOTES: * We will be using automated grading procedures.
* The registration information at the front of the solution
should be in precisely the same format as requested below.
Otherwise, your solution could be lost. Be sure that
each program has the same registration information.
* Programs that consist of essentially nothing more than print
statements will not be graded.
* Submitters of programs that attempt to thwart grading procedures
will be forever disqualified from USACO contests.
* Don Piele <piele at cs.uwp.edu> is this contest's director.
* Russ Cox is this contest's grader.
* All programs read their input from file INPUT.TXT; do not
specify a path name in your `open' statement.
* All programs write their output to file OUTPUT.TXT; do not
specify a path name in your `open' statement.
* DO NOT USE conio.h (in C) or `uses crt;' in Pascal -- just output
your answer straight to file OUTPUT.TXT as if it were a
standard teletype-style printer (using no screen manipulation
or cursor positioning commands). Do not clear the screen.
* Note that test data run by the judges will almost surely be
more challenging than the test data supplied with each problem.
* We will assess scoring penalties when certain rules are abused.
* There will be no leniency in grading this contest.
ACKNOWLEDGMENTS:
* Thanks to Greg Galperin for developing the problems and USACO
coaches for critiquing them.
* Thanks in advance to Russ Cox for creating grading procedures and
performing them for the contest entrants.
-----------------------------------------------------------------------------
No special registration form is required. Each problem solution has, within
its submission, an entry form (see below). You enter when you send in
your solution.
-----------------------------------------------------------------------------
Submit your answers to problems via e-mail to usopen98 at delos.com. Please
send precisely one problem's solution program per e-mail (i.e., send
three separate e-mails for three problems, etc.). Submit only one
solution per problem. If you submit more than one solution for a problem,
only the last one received by our automatic mail reader will be graded.
That means if you find a bug after your submission, you can re-submit.
This is dangerous ground, of course, since your newer program might, in
fact, be worse than the previous one.
Every e-mail is acknowledged almost instantly by an automated mail
reader. If you do not receive an acknowledgment, double-check the
address. Note that some networks connect to the Internet only
occasionally.
Each solution e-mail submission should have the following format for
the e-mail message. PLEASE SEND ASCII MESSAGES. DO NOT USE ATTACHMENTS,
MIME ENCODING, fancy mail options, or anything else. MIME-encoded
messages are discarded without decoding. The programs that read the
mail are looking for just plain old ASCII. Submissions that use some
format other than ASCII might not be graded. Your acknowledgment
tells what problem number was detected if you formatted your header
mostly correctly.
Submissions must have special comments separating sections of the mail;
you must insert the three `#'s and the word that follows them. These
comment lines are surrounded by a single blank line. Here is the exact
format for submitting solutions so the grading programs can read them:
### Program
... [header -- see below for format] ...
... [text of program in C or Pascal] ...
### End
NOTES: * Put comments precisely like the ones below at the front of each and
every solution (after the `### Program' marker).
* These messages are read by a program; do not change the format.
* Be sure your email address and name are always spelled precisely
the same way. We use the combination of email address and name as
a unique identifier for you.
* Data after `### End' are ignored (e.g., signatures)
* All registration lines (below) are required; your program won't
be graded until they are filled in.
* Do not insert any extra blanks or blank lines.
* Put compiler directives just before the header (as shown below)
but nevertheless after the `### Program' marker. Choose your
directives based on your own experience.
Here is the C/C++ header (with compiler options) filled out for Rob
Kolstad (my comments on far right -- do not include them). Do not remove
any blank lines -- the automatic grader uses them. You should fill out
a header out for each problem with your own data (why not save it in a
file on your computer for easy inclusion on later submissions):
#pragma option -3 -f287 -G -O2 -Ot
/*
Problem: 1 (single digit problem number)
Name: Rob Kolstad (first name then last name)
Email: kolstad at bsdi.com (email address)
School: Norman High School
Grade: 12 (grade in school, numerical: 7, 8, 9, ..., 13)
Age: 18
CityState: Norman, OK
Country: USA (three letters: CAN, COL, DEU, ROM, USA, etc.)
*/
If you live somewhere that has a city but no state, please omit the
state. If your school system uses a notation like `Form 6' for older
students, please pro-rate your `Grade' by calculating the equivalent
USA school grade. In the USA: grade 10 students begin around age 15;
grade 11 students begin around age 16; grade 12 students begin around
age 17.
Here is the PASCAL header (with compiler options) filled out for Rob
Kolstad (my comments on far right -- do not include them). Do not remove
any blank lines -- the automatic grader uses them. You should fill out
a header for each problem with your own data (why not save it in a file
on your computer for easy inclusion on later submissions):
{$G+,N+}
{
Problem: 1 (single digit problem number)
Name: Rob Kolstad (first name then last name)
Email: kolstad at bsdi.com (email address)
School: Norman High School
Grade: 12 (grade in school, numerical: 7, 8, 9, ..., 13)
Age: 18
CityState: Norman, OK
Country: USA (three letters: CAN, COL, DEU, ROM, USA, etc.)
}
Watch your mailbox for a quick (automatically-generated) reply. If you
don't see one fairly soon (i.e., 15 minutes) after sending in your
solution, send another e-mail to kolstad at bsdi.com explaining the situation
(including which problem you submitted, when you sent it).
Notes on compiling:
If your source code does not compile without changes, your program
will not be graded. The only exception to this is: we will fix source
codes mangled by mail agents' treatment of line wraps and the like.
Don't use C's ``bool'' type. That is specific to Borland C/C++ 5.0.
If you can compile your code under ANSI C, you're more than safe.
The scorer will not compile with any command-line compiler options.
You must set any relevant options using the appropriate method in the
source file, as illustrated above. Note that not all command-line
options are compiler options. In particular, don't bother specifying
"-P" or "-P-" on the "#pragma option" line, as the compiler will not
accept it.
=============================================================================
=============================================================================
Contest Problems
1997-98 USA Computing Olympiad
US Open -- International Division
April 9-13, 1998
=============================================================================
1. YOUR RIDE IS HERE
It is a well-known fact that behind every good comet is a UFO. These
UFOs often come to collect loyal supporters from here on Earth.
Unfortunately, they only have room to pick up one group of followers on
each trip. They do, however, let the groups know ahead of time which
will be picked up for each comet by a clever scheme: they pick a name
for the comet which, along with the name of the group, can be used to
determine if it is a particular group's turn to go (who do you think
names the comets?). The details of the matching scheme are given below;
your job is to write a program which takes the names of a group and a
comet and then determines whether the group should go with the UFO behind
that comet.
Both the name of the group and the name of the comet are converted into
a number in the following manner: the final number is just the product
of all the letters in the name, where "A" is 1 and "Z" is 26. For
instance, the group "USACO" would be 21 * 19 * 1 * 3 * 15 = 17955. If
the group's number mod 47 is the same as the comet's number mod 47, then
you need to tell the group to get ready! (Remember that "a mod b" is
the remainder left over after dividing a by b; 34 mod 10 is 4.)
Write a program which reads in the name of the comet and the name of
the group and figures out whether according to the above scheme the
names are a match, printing "GO" if they match and "STAY" if not. The
names of the groups and the comets will be a string of capital letters
with no spaces or punctuation, up to 80 characters long.
Examples -----
Input: (file INPUT.TXT)
COMETHALEBOPP
HEAVENSGATE
Output: (file OUTPUT.TXT)
;
Input: (file INPUT.TXT)
SHOEMAKERLEVY
USACO
Output: (file OUTPUT.TXT)
STAY
=============================================================================
2. AVOIDING LES ENTARTEURS
Billy Goats, Chairman and CEO of industry giant Mycowsoft, is visiting
his European branch offices. But alas, the notorious Le Gloupier is at
it still, and has placed his agents (the entarteurs) in the streets of
Europe, waiting to throw cream pies in celebrities' faces. Luckily,
Mycowsoft Corporate Intelligence has determined how many entarteurs lie
in wait along each of the routes between offices, and has asked you to
plan Billy's visits so as to minimize the number of pies Billy has to
wipe off his face.
The first line of the input file will contain N, the number of corporate
offices which must be visited, 1 <= N <= 50. Each of the next N lines
is a space-separated list of N integers between 0 and 1000 inclusive,
where on the i-th line in the block the j-th number indicates the number
of cream-pie-throwing pranksters who are waiting along the route from
office i to office j. (Restated, this number is on the i-th row and
j-th column of the NxN grid of numbers, where the i-th row in the block
is on the i+1-st line of the file.)
Billy needs to visit all N of Mycowsoft's corporate offices, each one
exactly once, starting from any of them and ending in any other. You
should create such a route and print the office numbers visited in order
on the first line of the output file separated by spaces (there should
be N of them), and on the second line of the file print the total number
of entarteurs encountered on that route. Your solution will be scored
based on how many entarteurs were encountered; the better (smaller) that
number is, the more points you get for that test case.
Note that you will almost certainly not be able to find the optimum
answer for some of the test cases within the short run time limit (5
seconds, as for all problems); you should try to get as good a solution
as you can in time, making sure your program outputs it and exits before
time runs out. In the Note below, we suggest how your program can keep
track of its run time.
Example -----
Input: (file INPUT.TXT) (annotated here, but not in the real data file)
4 -- N, the number of offices to visit
0 50 60 40 -- 60 entarteurs are on the way from 1->3, etc.
80 0 10 30
20 60 0 90
60 70 40 0
Output: (file OUTPUT.TXT) (again, you should not include annotations)
2 3 1 4 -- which offices to visit, in order
70 -- Billy encounters 70 entarteurs on this route.
** There are other valid answers, and any valid solution will receive
some points; this is the optimal answer, and will receive the most points **
NOTE:
You can use code like that suggested below to allow your program to keep
track of its run time, so it can exit within the time limit.
In C, at the top of your file, put:
#include <time.h>
then, to check the time used by your program so far,
if (clock() >= 5*CLK_TCK) {
printBestAnswerSoFarAndExit();
}
In Pascal, at the top of your program:
uses dos;
declare the following global variables:
hour, min, sec, centisec, timeStart : Word;
as the first thing your program does:
GetTime(hour, min, sec, centisec);
timeStart := (((hour*60)+min)*60+sec)*100+centisec;
and whenever you want to check time:
GetTime(hour, min, sec, centisec);
If (((hour*60)+min)*60+sec)*100+centisec - timeStart >= 500 Then
printBestAnswerSoFarAndExit();
=============================================================================
3. SCORE INFLATION
The more points students score in our contests, the happier we here at
the USACO are. We try to design our contests so that people can score
as many points as possible, and would like your assistance.
We have several categories from which problems can be chosen, where a
"category" is an unlimited set of contest problems which all require
the same amount of time to solve and deserve the same number of points
for a correct solution. Your task is write a program which tells the
USACO staff how many problems from each category to include in a contest
so as to maximize the total number of points in the chosen problems
while keeping the total solution time within the length of the contest.
The first line of the input file contains the length of the contest in
minutes M, 1 <= M <= 10,000 (don't worry, you won't have to compete in
the longer contests until training camp). The second line contains N,
the number of problem categories, where 1 <= N <= 10,000. Each of the
next N lines gives two integers describing a category: first, the number
of points a problem from that category is worth (between 1 and 10,000),
and second, the number of minutes a problem from that category takes to
solve (also between 1 and 10,000).
Your program should determine the number of problems we should take from
each category to make the highest-scoring contest solvable within the
length of the contest. Remember, the number from any category can be
any nonnegative integer (0, one, or many). Output on a line by itself
only the maximum number of possible points.
EXAMPLE:
Input:(file INPUT.TXT) (annotated here, but not in real life)
300 -- M, number of minutes in the contest
4 -- N, number of problem classes
100 60 -- class 1: worth 100 points, takes 60 mins.
250 120 -- class 2: worth 250 points, takes 120 mins.
120 100 -- class 3: worth 120 points, takes 100 mins.
35 20 -- class 4: each problem from this class
is worth 35 points and takes 20 mins to solve.
Output:(file OUTPUT.TXT) (again, we annotated here, but you shouldn't)
605 -- you can get 605 points: take 2 of #2 and 3 of #4
=============================================================================
====================================================================
/\ Rob Kolstad Berkeley Software Design, Inc.
/\/ \ kolstad at bsdi.com 5575 Tech Center Dr. #110
/ \ \ 719-593-9445 Colorado Springs, CO 80919
====================================================================
2. Re: Euphoria Programming Contest...
At 03:23 PM 4/12/98 +0700, you wrote:
>Hi all,
>
>I am forwarding a message from Dr. Rob Kolstad >kolstad at bsdi.com> (without
asking for his permission)
>about a programming contest.
>He asked for solutions in Borland's Pascal or C++.
....
<snip several hundred lines of rules that must have been
written by an IRS person laid off for over-zealousness)
....
He forgot to mention it's only for vers. 1.2.4 of C++
bought in Albania during a full moon...
Surely you don't expect them to consider Euphoria?
Irv
----------------------------------------------------------
--Visit my Euphoria programming web site:--
--http://www.mindspring.com/~mountains --
----------------------------------------------------------
3. Re: Euphoria Programming Contest...
>Surely you don't expect them to consider Euphoria?
But is it a great iniciative! Even better if it's aimed to young people. I
didn't understabd quite well the run-time limit. How can you convert a
maximun runtime from P75 to P166MMX or PII233? It depends on other factors
besides CPU clock speed... how about cache size, instruccion piping, etc..?
Regards,
Daniel Berstein.
PD: I'm sending this by my other email account because
danielbersteib at usa.net SMTP server is down right now.
4. Re: Euphoria Programming Contest...
Andy Kurnia writes:
> Really, I enjoy these kind of programming contests,
> and I would like to see one that allows Euphoria solutions!
David Gay has been running a contest for the past while,
and so far no one has entered. He says he's going to
give a Euphoria Complete Edition as a prize.
Surf over to his contest page:
Regards,
Rob Craig
Rapid Deployment Software
5. Re: Euphoria Programming Contest...
At Mon, 13 Apr 1998 01:36:04 -0400, Robert Craig <rds at EMAIL.MSN.COM> wrote:
>Andy Kurnia writes:
>> Really, I enjoy these kind of programming contests,
>> and I would like to see one that allows Euphoria solutions!
>
>David Gay has been running a contest for the past while,
>and so far no one has entered. He says he's going to
Robert, you misunderstood. I prefer informatics problems (read the problems
I re-posted), i.e. the solutions process some data; it doesn't do artworks
(no clear screen; no screen output; no keyboard input; NO GRAPHICS nor
mouse nor sound nor anything "attractive"). (Solutions are supposed to read
'raw' data from a file, process it, and write the 'cooked' output to
another file.) The solvers are supposed to use their intellectual skills
instead of their sense of art. The judgement of the correctness is
objective, not based on such a subjective criteria as "the most creative
cyberpostcard".
Anyone to start such a contest? Please???
>give a Euphoria Complete Edition as a prize.
Sure, but will it be the dual-platform one? 
>Surf over to his contest page:
6. Re: Euphoria Programming Contest...
- Posted by MAP <ddhinc at ALA.NET>
Apr 16, 1998
-
Last edited Apr 17, 1998
Andy,
A little over a month ago we had a little contest going to write
a program that could generate primes faster than the benchmark
RDS uses, and Arthur Adamsomson graciously served as host and
timekeeper for it. There were no prizes, it was just for fun,
but many people still participated. If you or anyone else would
like to start another contest, I'm sure you'd find plenty of
willing participants. I think we could do without a huge list
of rules and deadlines though... contests for fun should be
just that, fun.
Christopher D. Hickman
Btw, How are you Arthur? Haven't seen you on the list for a while.
7. Re: Euphoria Programming Contest...
>A little over a month ago we had a little contest going to write
>a program that could generate primes faster than the benchmark
>RDS uses, and Arthur Adamsomson graciously served as host and
>timekeeper for it. There were no prizes, it was just for fun,
>but many people still participated. If you or anyone else would
>like to start another contest, I'm sure you'd find plenty of
>willing participants. I think we could do without a huge list
>of rules and deadlines though... contests for fun should be
>just that, fun.
>
>Christopher D. Hickman
>
>Btw, How are you Arthur? Haven't seen you on the list for a while.
Chris and friends, I am fine. I worked hard on a further improvement
for primes, then gave up at least temporarily.
I am working on a Euphoria version of the Ternary Tree as in DJJ
April, '98. The first part, the tree builder, just today started to work. If
I can get the read portion going, I will post it all as a suitable vehicle
for a further improvement project such as you suggest.
The DJJ article, page 20, is very interesting and probably available
on line at http://www.ddj.com (and with more background at
http://www.cs.princeton.edu/~rs/strings/ )
Cheers!
Art Adamson
Arthur P. Adamson, The Engine Man, euclid at isoc.net
