USACO FEBRUARY 2005 CONTEST *********************************** NEWS ********************************** THREE DIVISIONS FOR THIS CONTEST, TWO BY INVITATION Anyone may enter the BRONZE division; GOLD and SILVER are by invitation only. Those who qualified for GOLD and SILVER should have been notified by e-mail. CONTEST LENGTH IS THREE HOURS Contestants should devote THREE hours in a row (no breaks) to the contest. DON'T CHEAT Do not use another login id to read the problems and thus cheat. Do not collaborate with others. IF YOU ARE CAUGHT CHEATING, YOU ARE BANNED FOR LIFE FROM ALL USACO ACTIVITIES. DON'T CHEAT. THERE ARE NO SECOND CHANCES. CONTACTING THE CONTEST ORGANIZERS MAIL: If you send contest email to questions@ace.delos.com, please make sure the subject contains the word 'USACO' so it shows up in the mailbox prominently and is not classified as spam. USING CODE FROM OTHER SOURCES If you use code from a book or other source during this contest, insert a comment in the code telling the source or you will be disqualified and banned. JAVA Java is available! It's GNU Java and relatively untested, but the sample programs work. Let us know if you have trouble with it. Note that Java might tell you it suffered a signal instead of a timeout. In either case, the Java program is not correct. Note that you must put your entire Java program in a single file. GNU Java does not support 'split'. We are working to test Sun's Java implementation, but did not complete the testing in time for this contest. ****************** SPECIFIC INFORMATION FOR THIS CONTEST ****************** NAME: USACO February 2005 Contest DATES: 08h00 GMT Friday 11 Feb - 15h00 GMT Tuesday 15 Feb 01:00 MST Friday 11 Feb - 08:00 MST Tuesday 15 Feb Note that you must start the contest hours before the end time if you wish to have enough time to solve the problems. TIMELIMIT: Three consecutive hours to solve all problems. STYLE: Individuals; no team work. SOLUTIONSTO: http://ace.delos.com/contestgate DIRECTOR: Rob Kolstad () QUESTIONDUDE: Be sure to include 'USACO' in the subject to avoid spam filters! GRADER: Rob Kolstad () HOTLINE: In the USA and Canada, call the USACO Contest Hotline at +1 877-753-3567 toll-free with problems during the contest (0700-2300 MST only, please). COMPILELIMIT: Your program must compile in 30 seconds or less RUNTIMELIMIT: 0.300 second max per test case (unless otherwise stated) NOTE: Java users get 5x the normal runtime limit, since Java code runs more slowly. The judges reserve the right to change this constant at any time for any reason. Java times are scaled and reported as 0.. 0.3 seconds, though. JUDGECOMP: 700 MHz Duron COMPILERS: gcc version 2.96 20000731 (Red Hat Linux 7.0) Free Pascal Compiler version 1.0.10 [2003/06/26] for i386 gcj based upon gcc 3.3.2 GRADING_OS: Linux version 2.2.16-22smp PROCTORING: Not required for any division. ASSISTANCE: Books, websites, old files, and any other non-human assistance is OK. Add an explanatory comment to any code that is copied from a book or from an old file (failure to do so will lead to disqualification). Do not search for exact solutions on the web or use solutions posted at the USACO or similar sites. DIVISIONS: Three divisions: GOLD, SILVER, and BRONZE. GOLD and SILVER division entry is by invitation only. ANALYSIS MODE: 'Analysis mode' will be available when the contest ends. You can re-test your programs to see how they would do with various changes. You can also see the other division problems and solve them. **************** GENERAL INFORMATION FOR ALL USACO CONTESTS *************** These details have not changed since the first 2003-2004 contest. WHAT: This USA Computer Olympiad Contest is a computer programming contest open to all pre-college students throughout the world. Several problems are presented for solution in each of two divisions. Results of this contest and other contests will be among the data used to choose USA delegates to the USA training camp and potentially to the IOI. Winners in each division will receive certificates. WHO: All pre-college students, world-wide, are eligible to compete. This is an individual contest, not a team contest. Visitors/observers/"for fun" entries will be scored and reported separately. WHEN: See the schedule above for the contest dates. All work must be performed in a single session. WHERE: For non-proctored contests: Students can work on problem solutions anywhere they wish. Proctored contests require supervision by the proctor, of course. HOW: Solutions must be written in GNU C, GNU C++, FreePascal, or GNU JAVA and must be submitted to the web before the contest completion deadline. As soon as the grading machine receives your program, it will compile the program and run it against a small number of very simple test cases. The results will be returned to you very quickly. This should enable you to fix incompatibilities, misspelled filenames, and the like. This means that the judges will rarely, if ever, make changes to your program during grading. Be sure to send in questions if you think the compilers are misbehaving. PRIZES: Each North American winner will receive a handsome certificate, and all winners be immortalized on the USACO Web Pages. The policy for more distant winners is not determined at this time. FEES: No entry fees are charged. RULES: Consultation with people other than the contest director is prohibited. Work by yourself, not in a team environment. Submit questions (one question per email, please) to the QUESTIONDUDE (see above) who will try to fathom an appropriate answer for you (and post it to the hs-computing or the web page message-of-the-day if required). Unless otherwise stated, your program must run no longer than the default time limit for any test case on the judge's computer. Unless otherwise specified, it is NOT guaranteed that all possible legal datasets will be solvable within the time limit. Likewise, unless specified it is NOT guaranteed that answers will fit in a traditional computer data type (i.e., integer answers might require more than 32 bits to represent). The judges reserve the right to increase time limits during grading. Decision of the judges is final. Do not cheat; it's no fun for anyone. Cheaters are often disqualified and banned for life. Do not access the contest using more than one signon. Do not use inline assembler statements. Do not submit programs that use data files that aren't supplied by the contest coordinators. Read only the specified input files and write only the specified output files. Do not submit programs longer than 1,000,000 bytes. Do not use `temporary' data files. Do not submit programs you wrote in the past in collaboration with others. 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. Unless otherwise stated, programs must be deterministic in nature and produce identical answers each time they are run with identical input(s). Programs that are not deterministic will be disqualified. Note that random-number based programs can still be entered -- they should use a fixed seed so they get the same answer each time. Problems are intended to be algorithmic in nature, thus clever algorithms and/or data structures might be necessary to solve all test cases correctly and within the time limits. All problem statements are intended to be straightforward (yet challenging); no problems are intended to have `hidden tricks' in the problem statement. Legal but complex datasets are fair game for testing. If you find a problem has poor wording or an ambiguity, document your assumptions carefully and move on. Send e-mail; we'll reply if we can. NOTES: Submit your solutions via the web at the address listed above. Register for the contest at the website, as well. If you have ever registered before, your registration should still be valid. You can ask the web site to send you your old id and password to the email address with which you registered. Please use the same login for each contest so we can keep track of everyone's progress. The problem description information at the front of each solution should be in precisely the format as requested below. Programs that consist of essentially nothing more than print statements will not be graded. Programs must compute the requested answers. Do not use precomputation to solve these problems. The C/C++ compiler uses 32 bits for an int. C/C++ programmers: Make sure you exit (0); when your program has completed. The grading program wants your program to compile error-free. You must remove all errors for your program to be graded. You do not need to remove all compiler warnings. Submitters of programs that attempt to thwart grading procedures will be forever disqualified from USACO contests. Do not join this elite club! All programs read their input from a file named in the problem statement (e.g., `cow.in'). Do not specify a complete path name in your `open' statement, just `cow.in'. Note that filenames are case-sensitive. If the problem says `cow.in' then you must use `cow.in' since `CoW.In' and 'COW.IN' will not work. All programs write their output to a file named in the problem statement (e.g., `cow.out'); do not specify a path name in your `open' statement, just `cow.out'. Like the input filenames, output filenames are case-sensitive. Virtually every program's output is in the form of "lines". A line ends with newline character ('\n' in C; use writeln in pascal). If your output does not contain a newline at the end of every line, it will be graded as incorrect. Small amounts of output you write to stdout or stderr are ignored by the judging procedure. They are returned to you during the initial compile/test phase, though, if errors occur. Note that test data run by the judges for grading will surely be more challenging than both the example data supplied with each problem and the data used to check that your program is submitted correctly. The scorer will assess scoring penalties when certain rules are abused. Unless otherwise stated, your programs will be limited to about 16MB of total memory use. This encompasses a stack size limit of 2MB and a (global) datasize limit of about 15MB. That means you can't put really large data structures on the stack, which is where all local variables are allocated. Note that all the examples are intended to be correct and helpful. If you find an apparent error, please contact the `QUESTIONDUDE' so he can correct the problem. Some of the examples have only been double-checked, not triple-checked. The scorer will compile your program with optimization turned on. For C/C++ programmers, the #pragma -fhandle-exceptions is handled correctly. C programmers: #include if you use math functions #include for srandom/random #include for srandom/random #include for srandom/random which are called like this: srandom(seed); randominteger = random(); where the randominteger will be between 0..2^31-1. Note that random()%N will be a random integer in the range 0..N-1. It is unlikely you want to use a seed other than a constant as that would cause your program to produce results which potentially differ from run to run. If, over time, you submit more than one solution for a single problem, only the last one submitted will be graded. That means if you find a bug after your submission, you can re-submit. There is no penalty for re-submitting -- in fact, you can use the technique to make sure our compiler likes your program(s) or even to run timing tests. Try not to submit more than 25 solutions this way so the server will always available to everyone. Measuring the Intermediate CPU Usage of a Program - Pascal Users The grading system will observe your program's execution time from outside. If you want to check intermediate execution times during test execution or submission execution, you may include this line in your code: {$i extime.inc} to include the execution function called "exectime". This function has no parameters and looks just like a scalar. Its value is the number of milliseconds of execution used so far. Here's a sample program to demonstrate its use: program timetest; {$i extime.inc} var i, j, k:longint; begin for i := 1 to 100 do begin for j:=1 to 1000000 do begin k := i + j + k; end; end; writeln (exectime); end. This facility is only available for test executions and submission executions. Measuring the Intermediate CPU Usage of a Program - C/C++ Users The grading system will observe your program's execution time from outside. If you want to check intermediate execution times during test execution or submission execution, you may use the `exectime' function, which returns the number of milliseconds your program has used so far. Here is a sample program to demonstrate its use: int exectime(); main() { long i, j, k; for (i = 0; i < 100; i++) for (j=0; j < 1000000; j++) k = i + j + k; printf ("%d ms\n", exectime()); } This facility is only available for test executions and submission executions. Measuring the Intermediate CPU Usage of a Program - Java Users Sorry, this facility is not available: ************************* HOW TO USE WEB SUBMISSION ******************** Add identification lines like these to the beginning of your program's source file (omit the explanations shown on the right in parentheses): For C, C++, JAVA: /* PROG: cowfun (whatever the problem name is) LANG: C++ (Choose one: C, C++, JAVA) */ Don't use //-style comments for these headers; they won't work. For Pascal: { PROG: cowfun (whatever the problem name is) LANG: PASCAL } Then, type the filename into the obvious browser form and click "Send It In". Your results will be displayed shortly thereafter. You can submit solutions to a simple problem before starting the contest timer in order to ensure that all mechanisms work. The program name is `test' and the files are `test.in' and `test.out'. The input file contains two integers on a single line. Sum them and print the sum to a single line in the file named `test.out'.