[clug] Re: ACM programming competition

Crossfire xfire at xware.cx
Wed Sep 8 07:55:23 GMT 2004

Andrew Over was once rumoured to have said:
> On Wed, Sep 08, 2004 at 02:55:56PM +1000, James Ring wrote:
> > On Wed, 8 Sep 2004 01:36 pm, Michael James Stevens wrote:
> > > Yes. I have Warren. (u3950692). This gives us a 3 person team. I'm busy
> > > with COMP3500 right now, so can you email Eric to get our team in
> > 
> > All done!
> Free (unsolicited! woo!) advice (for the actual competition):
> - Avoid computational geometry questions unless you are a comp geom guru
>   [1], or you've solved all the others.  Yes I know it looks easy, but
>   there are 3 different corner cases you haven't thought of (excluding the
>   15 you have).
> - There will be several graph theory problems.  Know about breadth-first vs
>   depth-first traversal, along with things like transitive closure
>   algorithms (floyd-warshall?  it's been a while).
> - Dynamic programming pops up occasionally and yields nice short solutions
>   to otherwise intractable problems.
> - Language familiarity is more important than support for nice data
>   structures (you can do very nasty things in C if you have to).
> - With the exception of the first problem, don't waste your time typing
>   until you've coded a solution on paper.  You'd be amazed how much less
>   buggy things are when you've forced yourself to code it up on paper (at
>   least IMHO).
> - Style?  What's style? (An ideal solution will qualify as an IOCCC entry
>   when you're done).
> - Caffeine is your friend.

You forgot one very important thing:

  - FP Precision sucks.

  Back in '98 (when I last did ACM ProgComp at ANU), there was a problem
that involved the use of FP.  We lost a lot of time trying to find what
was wrong with our submission, which later turned out to be a floating
point precision difference between our solution and the official answer.

One other useful hint:

Don't underestimate the usefulness of scanf.  (A lot of people who
attack the ACM ProgComp underestimate how easy it is to parse the ACM
ProgComp data formats using scanf and use it as a justification to stuff
around with C++ unnecessarily).


More information about the linux mailing list