Contest Chapter

Topics on This Page


General Tips

Contest Tips
How to Approach a Programing Contest
Reference Books & Webs for Contest
Easy ACM.UVA.ES Problem

 

Tips for Beginners to do well in contest

General Tips

Some of these "tips" might seem unreasonable or impractical at first. But, they help reduce the amount of "unnecessary" errors. After a little time they become second nature and will save headaches during contests. Remember that these tips are for programming contests ONLY. They do not necessarily represent good programming style.

Know the details of your IO routines This may seem obvious, but it is important. You don't want to spend what limited time you have during the contest figuring out how to do IO. What you don't know here will hurt you. Recall that the Java number formatter added a comma to the number by default. We were nice in judging this because it should be a learning exercise. But in a "real" contest the programs would not have been excepted.

Always use doubles OK, don't always use them, but NEVER use floats. Carrying operations to a higher precision inside a program will never make an answer wrong, but not using the doubles can cause problems sometimes. If you always use them you will never have that problem.

End you output with a newline Note: This does not mean put an extra blank line at the end of your output, it just means that EVERY line your program produces should end with a '\n'. There are a number of reasons for this, but the easiest to understand is "You ended every other line in your output with a newline, what makes the last line any different?"

Don't use exceptions -- even in Java Exceptions are just that, exceptions. They are used when there is a problem, NOT in the normal course of execution. If, for example, you are expecting a file to end CHECK FOR IT. Don't let an end of file exception, or any other side effect exception (like null pointer) get thrown. Along the same lines, DON'T catch any exceptions. Exceptions are BAD. They indicate a problem with YOUR code. The judges will guarantee that all the input is valid, so if you program functions correctly it should not generate any exceptions. This means if you get a "run-time error" result back from the judge you know there is a bug with your code that reads / access the test data, NOT an error in your algorithm. This also means that when you get a "wrong answer" you know that there is an error in your algorithm, NOT some other error that threw an exception that caused the output to be incorrect. Another motivation for NOT using exceptions is that they introduce many more paths of execution through your code. And the additional paths are not always obvious. So if you don't use exceptions you will reduce the complexity of your code, making it easier to code correctly the first time, and easier to debug.

Don't write ANYTHING to standard error Assume that the judging scripts will capture BOTH standard out and standard error. Anything written to standard error will cause your program to be rejected with a "wrong answer".

Test your program before you submit it Run the version of the program you are about to submit. This helps you catch problems like not taking out debug code, and provides a last sanity check. Remember programs that are bounced add 20 minutes per bounce to your final score.

Read the problem carefully Again this may seem obvious, but there is a lot of important information that is IMPLIED in the problem statement. It is also possible to skip over important information because you are racing the clock. Take the extra minute to read and understand the problem. And then reread it before you submit your solution to double check.

Test your solution Use more than the sample data. The judges have their own hidden tests that they use to test your solutions. These hidden tests will test every legal aspect of the problem, including boundary conditions and large cases. Remember that the judges data will never be invalid. The sample data provided in the problem description will not test these boundary conditions. Test them. If you are working in a team try to have a person who didn't code up the solution generate the test cases. Usually a fresh mind sees things differently and can find problems quicker.

Know one language well This is another one that seems obvious, but it is worth mentioning. Don't spend time figuring out all the languages the contest is offering. Make sure you know ONE of the well. The judges will guarantee that all problems are solvable in all languages. Having the ability to "select the best language for the problem" do not buy you much, unless you know and are comfortable with all the languages.

Additional tips

Read all the questions before you start solving any of them; we may have stashed all the easy ones at the end. Tackle the easy ones first; because of the scoring algorithm, solving easy ones fast and first gives you an advantage. Before you submit and after you think you are done, reread the question carefully and be sure you solved the right problem, named the files correctly, formatted the output correctly, etc. Test the boundary conditions. If n can go from 0 to 10000, we will probably try 0 and 10000 and lots in between. Don't get stuck on one problem for too long; if you feel you aren't making progress, try another one.

reference: http://www-cse.ucsd.edu/users/calder/UCSDProgramContest/tips.html

*for more programming related topics be a member of developer_ustc group at yahoo groups.
Go to the top

Contest Tips Article by ACM

Contest Tips

Submitted by acm on Mon, 2006-03-06 14:41.

How Programming Contests Work

Teams of 2-3 people compete against each other to solve the most number of
problems in the least amount of time. At the beginning of the contest, a number
(usually 5 to 9) of programming problems are handed out. These programming
problems have an English description, sample input, and sample output. Problems
may be done in any order, and each problem has equal scoring regardless of its
difficulty. Each team tries to write programs to solve the problems. Once a program is
done, it is submitted to the judges to determine if it's correct or not. If the
program is deemed correct, then that team scores a point. Otherwise, the
judges will send a response back with a single reason why the program is wrong
(although it's quite possible that there are multiple things wrong with the
program). If the team resubmits a correct program, then for each incorrect
solution submitted for that problem, a twenty minute penalty is applied.
There is no time penalty if the team never submits a correct solution. While coding programs, teams may use hardcopy references (books, printouts,
notes). But teams may >not use electronics (calculators, PDAs, etc.) or
network references (the Internet, personal home directories). The winning team is the team with the most points. If there is more than one
team with the most points, then the total time taken to solve the problems is
taken into account. The total time is determined by adding up, for each
problem, the time since the beginning of the contest to the time the correct
solution was submitted, plus any 20 minute penalties for incorrect solutions.
The winning team is then the team with the least total time.

Tips

Please also note the excellent comment
by Thomee Wright on this matter.
  • Do the easiest problems first. Scoring is based first on number of
    problems solved, and then the total time taken.
  • Read through all the problems before you start programming.
    That way you'll have an idea of which problems are easy and which
    problems are hard.
  • Make sure your output's format matches the specified format
    exactly . Incorrect formatting is the most common error for
    new teams.
  • Use the simplest algorithm that does the job. Your only goal is to
    come up with a correct solution. With most contest problems, memory
    efficiency and run-time efficiency are not an issue.
  • Think through your solutions before you begin to program. You don't
    want to waste time programming an inherently incorrect solution.
  • Program carefully, not quickly. You want to minimize the time to get
    a correct solution. If you program as fast as you can type, you'll
    spend most of your time debugging. You may want to have one team member
    type and another team member watching for bugs.
  • Enable compiler warnings (e.g. use the -Wall
    flag with gcc and g++), so that you can catch errors like
    uninitialized variables.
  • Bring books and printed example code. Take advantage of hard copy
    references.
  • Program on paper while the rest of your team codes on the computer.
    Bring paper and pencils.
  • Some programming contests require you to read input from a file and
    write output to a file. If you're using C, learn to use
    FILE *freopen (const char *path, const char *mode, FILE *stream) .
    That way, you can use printf instead of fprintf
    and scanf instead of fscanf .

Program Templates

Most contests will require you to put your team identification and problem
number at the top and bottom of your output, and some contests, such as NMT's
and the ACM regional contests, will require that you read your input and
write your output to files. Because these are repetitive tasks among all of
your programs, you can save time by using a template source file. *for more programming related topics be a member of developer_ustc group
Go to the top



Approaching Programming contest

How to Approach a Programing Contest

    Steps to take during a contest:
  1. Split problem set and re-staple
  2. Read (lightly) each problem making a few notes about it, keep a short list ranking the problems relative to each other
  3. Quickly discuss problems and do initial allocation
  4. If no real easy problem you might have someone work on stubs
  5. Take turns coding solutions until time runs out
This gets you started. That last step sounds easy but has lots of parts, such as:
  • Establish a time quantum (15 minutes for example)
  • After each 15 minute window, determine if anyone other than the person currently at the keyboard could benefit from using the computer. If yes, swap to next person (consider always giving someone 2 slices to start with if possible).
  • If a person has been debugging for the majority of a time slice, one of two things should happen:
    1. They should relinquish the computer to someone else
    2. One of the other team members should help them debug
    If you decide to relinquish the computer, a printout of the code to be debugged should be made.
    Obviously, there are three approaches to working on problems:
  1. Each person works on a problem independently
  2. One person does one problem, the other two team up on another problem Everyone works on the same problem
If three problems exist that seem relatively straight-forward, each person starting on a different problem might make good sense. As the problems get harder, the idea of two people working together (at least for periods) makes a lot of sense. If you get to a point where a problem is almost solved (or there is only one problem left), it makes sense to have all three team members concentrate on one problem.


Go to the top

Reference Books & Webs for Contest


There are a number of references that you should look into. Below is a short list to start with.

Go to the top

Easy Acm Problem

Easy ACM.UVA.ES Problem

100, 119, 130, 136, 146, 156, 272, 299, 543, 612, 640, 897, 10041, 10191, 10260, 11112 --------------------------------- Below message quoted from acm_solver group |---------------------|
|Easy Problems for ALL|
|---------------------|

This list is specially for the new solvers. Experienced solvers may
also have a look to find whether any easy problem left to solve :

Volume Problem Number
1 (100-199) 100, 102, 113, 136, 151, 160
2 (200-299) 271, 272, 299
3 (300-399) 300, 305, 324, 340, 350, 369, 371, 382, 392
4 (400-499) 412, 424, 438, 441, 443, 444, 446, 458, 476,
488, 489, 490, 492, 494, 495, 499
5 (500-599) 543, 575, 583, 541, 574, 591, 573, 576, 594,
6 (600-699) 640
10(10000-10099) 10008, 10013, 10018, 10023, 10035, 10038,
10055, 10071, 10082
11 (10100-10199) 10106, 10107, 10110, 10168, 10170, 10195
12 (10200-10299) 10222, 10260
13 (10300-10399) 10300, 10302, 10327
14 (10400-10499) 10409, 10424, 10469, 10473
15 (10500-10599) 10579

Go to the top