View Source: ProgrammingCompetitions - Waikato Linux Users Group

Edit PageHistory Diff Info LikePages
!!Tips for the New Zealand Programming Competition/ACM constestants.

! Bring pen/paper!
You'll need this during a programming competition, if you can't get on the computer, you need to write out some pseudo code, or markup a printout with possible bugs that need fixing.


! Have a skeleton program

Work on a skeleton program that can read input in, and loop over data.  Perfect this skeleton during the "trial"/test run and __print it out__ and take it with you into the competition proper.  Type it in with your first program and save it as say "template.cc" which you copy to programletter.cc.  An example C++ skeleton is below:

<verbatim>
//Team Name:
#include <iostream>
#include <string>
#include <cassert>
//#include <map>
//#include <list>
//#include <vector>
//#include <deque>
using namespace std;

bool process_one(void)
{
        assert(!cin.eof());
        // Your program goes here

        // return false on the last line of input.
        return true;
}

int main(int argc, char *argv[])
{
        while(process_one())
           ;
        // Any final results go here

        return 0;
}
</verbatim>

! Make sure you can drive your editor/compiler
During the practise session, make sure you can drive the editor/compiler, can you type in your skeleton and get it to compile without errors?  Can you turn on warnings?  Especially for java, are you using java 1.5? or java 1.1?  Once you've compiled your program, can you get back to the editor make a change and compile it again?  Any gotchas to think about (does your editor autosave when you compile?)

At waikato we use gcc/mono so to compile you want (eg for C++ <tt>g++ -W -Wall -g ./questiona.cc -o ./questiona</tt>)

! Choose your questions wisely
If you're reading this guide, chances are you won't get all the questions out.

For the NZProgComp, depending on what level you are depends on which questions you should target.  Look at last years problem set if you can to get a feel for it.  For 3rd years and above, you shouldn't do any of the 3-pointers.  Chances are you're not going to get more than one 100-pointer out, so select which one you want to tackle early and work on it.  Not all questions are created equal,  there will be some 30-pointers that are easier (for you at least) than most of the 10-pointers.  A strategy that worked well for us is when we got our questions, was to put the 3-pointers back in the paper slip and put it away, we weren't going to look at them until after the competition, give the 10-pointers to one predetermined member who was going to start coding them up immediately while the other two members would read the rest of the problem set and look for questions that are easier than their point values suggest (but be careful of hidden problems).  We'd choose at least one 100-pointer to attempt and we'd start writing out high level pseudo code for the problems.

! Don't brute force 100 pointers.

100 point questions look easy to do by brute force.  However you have a time limit of about 180 seconds.  Most of the problems you'll see when brute forced will be O(n!) or at least O(n<sup>2</sup>).  If n is large (which it inevitably is) you're program may not complete for a million years or more.  You will need some critical insight to reduce the search space massively.  Correct solutions to these problems usually complete in under 5 seconds.

Bill Rogers suggests that "you can do anything a million times".  If the order of your program is over a million you may run into problems.

! Type your sample input in
Type the sample input in and use redirection to test the program.  For instance
<verbatim>
 ./qA <qA.in
</verbatim>

We used "qA.in" as the sample input, and "qA.out" as the sample out.  "testA.in" as our hand crafted test input.

You should create "qA.in" files that are given to you on the problem sheets, and create "testA.in" that have any test cases your team have come up with.  Try, if possible to have another team member create "testA.in" they will often see problems you won't.

Also try <tt>./qA <qA.in | tee tmp && cmp tmp qA.out</tt>.  If <tt>cmp</tt> says "Files differ" then you have a formatting error/wrong answer. Fix it before submission.  Every year people submit their program with debug output enabled.  Don't be one of those people, test your program before hand!

! If you get a wrong answer
* Check capitalisation
* Check your spelling(!)
* Check for debug output
* Get someone else to read the problem sheet and ask you if you meet each constraint.
* Consider each constraint, there will be a judging data that tests each one.  If it says that there can be up to 1000 people in one problem, then there is probably a sample problem with 1000 people in it.
* If it is late in the competition, or someone else has already got that problem out then it's unlikely that the judges data is wrong.

----
CategoryProgramming
No page links to ProgrammingCompetitions.
Last edited on Monday, August 14, 2006 3:04:00 am by AristotlePagaltzis
Edit PageHistory Diff Info LikePages