Solving Problems Help Sat Dec 23 02:10:02 EST 2006 This help file is for contestants who have been given an account, or for contestants using their own accounts with the tools described in the email_unix_tools help file. Contestants using their own accounts without the tools just mentioned should read the email_solving help file instead of this help file. What Problems? -------------- When you first log in, there are no problems. You have to get the problems with the `hpcm_get' command. To get the demonstration problems before the contest starts, you can just type the command hpcm_get The demonstration problems are put in the `demos' subdi- rectory of your home directory (you can always get to this with the `cd ~/demos' UNIX command, where `~' de- notes your home directory). In a formal contest, you need to REPEAT the above `hpcm_get' command again, JUST ONCE, AFTER the contest starts, to get all the problems. In some informal contests you need to get each problem one at a time, using the command hpcm_get problems/pppp to get the problem named `pppp'. In other contests, the first `hpcm_get' gets ALL the problems, not just the demonstration problems. The contest problems are put in the `problems' subdirec- tory of your home directory (you can always get to this with the `cd ~/problems' UNIX command). Each problem has its own subdirectory in the `problems' subdirectory. Thus a problem named `pppp' would have a problem directory named `~/problems/pppp'. You can display an index of the problems and sometimes an estimate of their relative difficulty by using the command: help problems Asking Questions: ---------------- You may think that a problem description is ambiguous, and ask the judges for clarification, though you should be careful to think the situation through thoroughly first. You may e-mail such questions to the judges, but the method to do this from an account provide to you is a little weird. First, edit your email into a file of your own choosing. If your first line has the form Subject: .... and the next line is completely empty (no spaces), then the first line will be the subject line of the message. Then hpcm_sendmail < filename to send the file as email to the judges. Note that the subject must NOT begin with the words `submit' or `get'. If you ask for a clarification by e-mail, and a signifi- cant answer is given, that answer will be given by post- ing it on the scoreboard so everyone can see it. You will not receive email back in this case. Working on a Problem -------------------- For a problem named `pppp' you should write a file named `pppp.c', `pppp.cc', `pppp.java', or `pppp.lsp' in your `problems/pppp' directory. The suffix of the file you write determines the programming language you are using: .c for C .cc for C++ .java for JAVA .lsp for COMMONLISP You must write only ONE of these files; you CANNOT have a solution in two different languages at once. The description of a problem named `pppp' is in a file named `pppp.txt', `pppp.html', `pppp.htm', `pppp.ps', or or similar printable file. This file may or many not be given to you electronically. In a formal contest, it is not, but instead a printout of the file is given to you at the start of the contest. In informal contests, the problem description file is gotten into the problem directory by hpcm_get, and you must print it yourself or look at it with an editor, browser, or postscript dis- play program. In untimed contests, the problem de- scription file is typically a subpage of the contest web page, although the file may also appear in the problem directory. Your program should be written to take input from the terminal and put output to the terminal. In C this means using functions such as `gets', `scanf', and `printf' that implicitly use `stdin' for input and `stdout' for output. In C++ this means using `cin' and `cout'. In JAVA this means using `System.in' and `System.out'. In COMMONLISP this means using `*standard-input*' and `*standard-output*'. You should NOT, repeat NOT, write output to the standard error output, `stderr', `cerr', `System.err', or `*standard-error*'. Such output will result in a `Program Crashed' or `Cpu Time Limit Exceeded' score. You should NOT under any circumstances open a file in your code. In the judge's program execution environ- ment, output operations on opened files fail, in order to protect the judge's software from wayward submis- sions. Since you will likely not be checking for output failures in your code, your code will mysteriously pro- duce no output in the judge's environment if you open an output file, and will be scored `Program Crashed' if your program terminates, or `Cpu Time Limit Exceeded' if your program fails to terminate because all your input instructions have become no-operations. When the autojudge executes your program, it will be called with NO program arguments. You can use this fact to write out debugging information to the standard out- put IF your program is called with one or more program arguments. If you edit an input file named `pppp.in' in the problem directory, then the following UNIX commands can be exe- cuted in the problem directory. You can try them out using the demonstration problem in the `~/demos/count' directory. You can try `make submit' in this directory, and the judges will `judge' the demo submission, though of course it will not count. See the README file in this directory for more instructions. make Same as `make pppp.out' (see below). make pppp Makes the binary program file `pppp' by running gcc on pppp.c, or g++ on pppp.cc, javac on pppp.java, or a commonlisp compiler on pppp.lsp, depending upon which of pppp.c, pppp.cc, pppp.java, or pppp.lsp exist. Does nothing if `pppp' is more up to date than pppp.c, pppp.cc, etc. In addition to making `pppp', other files may be made for some languages, such as pppp.class which is made from pppp.java, or pppp.fas which is made from pppp.lsp. make pppp.out Makes `pppp' as above and then runs it with standard input coming from the file pppp.in. Puts the standard output in the file pppp.out, and then copies that to the screen. Puts any standard error output to the screen before the standard output from pppp.out. Does nothing, however, if pppp.out is more recent than both pppp.in and pppp. make pppp.debug Ditto but runs `pppp debug' instead of `pppp' and puts the standard output in the file `pppp.debug' instead of `pppp.out'. You should write your program to output debugging information to the standard output if the program is given any arguments. make debug Same as `make pppp.debug'. make submit Makes `pppp.out' just to be sure that nothing crashes, and then e-mails pppp.c, pppp.cc, ppp.java, or pppp.lsp to the judges. Note the pppp.in file MUST exist to submit, to make pppp.out, but pppp.in can be the minimum needed to keep your program from crashing (often pppp.in can be empty). There are alternative forms of this command used in untimed contests: see `Submission Alternatives' below. make clean Removes `pppp' and pppp.out. The `make' UNIX commands work because of the way the `Makefile' file in the problem directory is written. It is this file that causes `pppp.in' to be presented to your program as if it were input from a terminal, and causes output your program writes to a terminal to be stored in `pppp.out' instead. The `Makefile' file contains some oddities resulting from the fact that judges, who use the same `Makefile' as contestants, run solutions in a sandbox account that has permission problems accessing judge's files. Any file, directory, or program that must be accessed from the sandbox account may need permissions making it accessible to everyone. Common Mistakes ------ -------- If you get a `Program Crashed' or `Cpu Time Limit Ex- ceeded' score, check that you DO NOT OPEN any files. You should just read the standard input and write the standard output. If you open .in and .out files, it will work for you, but not for the judge. The judge runs your program in a protected mode in which opening a file fails because you do not have permissions. Assuming you do not check for opening or input/output errors, all your input and output operations may turn into no-operations. If because input operations are no-operations you loop infinitely, you will get the score `Cpu Time Limit Exceeded'. Otherwise you will get the score `Program Crashed', either because your program wrote no output since output operations are no-ops, or because JAVA checks for errors automatically and you get an uncaught input/output exception. If `make submit' tells you it cannot make a .in file, that is because you must edit a pppp.in file in order to keep `make submit' happy. The pppp.in file can be the minimum needed to keep your program from crashing (often pppp.in can be empty). It is important to run your program on the Sample Input and carefully check that the output produced matches the Sample Output. In particular, be sure any lines that begin or separate test cases are correct. Submission Alternatives ---------- ------------ In some contests, particularly untimed contests with `feedback' scoring, there are alternative ways of sub- mitting a problem: make submit Returns just score. make in-submit Returns score, and when practi- cal, returns the judge's input for the first failed test case. make inout-submit Ditto but returns both judge's input and judge's output for the first failed test case. make solution-submit Returns score, and if the score is `Completely Correct', also returns the judge's solu- tion to the problem. The scoreboard in a `feedback scored' contest is not based on time, but is instead based on the kinds of submission you do when your solution is still incorrect. Using `make submit' to submit an incorrect solution invokes the least penalty, using `make in-submit' a greater penalty, and using `make inout-submit' the greatest penalty. There is no penalty for a correct submission, and `make solution-submit' behaves like `make submit' for an incorrect submission. Timed contests and some other contests disallow most of these kinds of submit, in which case the disallowed submis- sions behave like `make submit' (but also return a note saying they are not allowed). If you have already submitted a correct solution, you can resubmit with a `solution' qualifier to get the judge's solution, without any affect on your score. Timed contests and some other contests disallow most submission qualifiers, in which case the submissions with disallowed qualifiers behave as if they had no qualifier (except they also return a note saying the qualifier was disallowed). Resource Limits -------- ------ If you look at the `Makefile' in the problem directory you will see that it contains memory and time resource limits which constrain your problem. Memory limits are typically several megabytes and time limits are typically 10 to 60 seconds. Harder problems require care to be sure you stay within these limits. Most problems are such that solutions in C or C++ will run in a few seconds. If you have long running times, you may have chosen an algorithm too inefficient to avoid the time limit. Debugging --------- The best way to debug is to include code that prints extra debugging information to the standard output if your program is passed any arguments. For C, such code might look like: int debug; #define dprintf if ( debug ) printf int main ( int argc ) { debug = ( argc > 1 ); // # arguments = argc-1. . . . dprintf ( ... ); } See the C++, java, and commonlisp help files for debug- ging in other languages. The `make debug' command (see above) calls your program with one argument and puts the output in `pppp.debug'. For program crashes and infinite loops, it is quickest to use a debugger, if you have minimal familiarity with one of the available debuggers. A typical usage is gdb pppp run < pppp.in ... program crashes, or control-C is pressed ... ... to get out of an infinite loop ... back [this lists frames] frame # [# is number of correct frame] list [lists code near crash] p EXP [print value of expression EXP] To debug, you do not have to use pppp.in and make pppp.out. You can just make pppp and run it as a UNIX command, typing input at it. BUT, to submit you must have some pppp.in file, though it can be the minimum needed to keep your program from crashing (often it can be a zero length file). Also, the resource limits will not be applied if you do not use pppp.in and `make'. The contest staff will answer questions about debuggers and editors as best they can. Other Issues ----- ------ The following help commands may be useful for: Printing files: help print Understanding problem scores: help scores Understanding the scoreboard: help scoreboard File: solving Author: Bob Walton Date: See top of file. The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2006/12/23 07:09:23 $ $RCSfile: solving,v $ $Revision: 1.20 $