Improve your Programming Contest Skills!

Post by William J. Jimenez
"PROGRAMMING CHALLENGES: The Programming Contest Training Manual" by
Skiena and Revilla is the ideal resource for those training for any
of the major programming contests such as the ACM International Collegiate
Programming Contest (ACM ICPC), USA Computing Olympiad, TopCoder Programmer
Challenges, and the International Olympiad in Informatics.
Dr. Rob Kolstad, Head Coach of the USA Computing Olympiad, says that
PROGRAMMING CHALLENGES "...is just the ticket for those interested in
a jumpstart to the world of contest programming...Even contest veterans
are likely to be able to find a nugget or two in the explanations and
strategies...Presented in a logical order, the book guides readers not
only through the techniques and algorithms required but also through a
huge set of problems that can be used for training."
See www.amazon.com/exec/obidos/ASIN/0387001638/ref=nosim/thealgorithmrepo/
and www.springer-ny.com/detail.tpl?isbn=0387001638 for more details.
To help the competitor, the book includes an appendix with training secrets
from competition finalists. A bonus feature allows the user to submit
programs for each of the programming challenges so it can be checked via the online
robot judge www.programming-challenges.com. Over 100 programming challenges
are included! The judge also keeps track of your statistics so that you can
see how you match up to the thousands of other participants worldwide.
The book provides a concrete understanding of algorithmic techniques, such
as backtracking and dynamic programming, and advanced topics, such as number
theory and computational geometry. Tutorial material and sample programs
assist the reader, as well as support for all popular programming languages
(C, C++, Pascal, Java).

"All" popular languages? Since when do C, C++, Pascal and Java constitute "all"?

Post by William J. Jimenez
Steven S. Skiena is a computer science professor at SUNY Stony Brook and
is the author of widely used books such as "The Algorithm Design Manual".
He was also the recipient of the IEEE Computer Society Undergraduate Teaching
Award in 2001. Miguel A. Revilla is currently the official website archivist
of the ACM ICPC and creator/maintainer of the primary robot judge and
contest-hosting website online-judge.uva.es -- which can also be used to
judge all the problems in the book. He is a professor of applied mathematics
at the University of Valladolid in Spain.
For more information, visit www.springer-ny.com/detail.tpl?isbn=0387001638.

Richard Heathfield

2003-07-08 23:46:57 UTC

<snip>

Post by William J. Jimenez
The book provides a concrete understanding of algorithmic techniques,
such as backtracking and dynamic programming, and advanced topics, such
as number theory and computational geometry. Tutorial material and sample
programs assist the reader, as well as support for all popular
programming languages (C, C++, Pascal, Java).

"All" popular languages? Since when do C, C++, Pascal and Java constitute "all"?

Yes, why drag C++, Pascal and Java into it?

;-)

--
Richard Heathfield : ***@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

Isaac To

2003-07-09 01:10:45 UTC

mensanator> "All" popular languages? Since when do C, C++, Pascal and
mensanator> Java constitute "all"?

I think it is since 3 or 4 years ago that Java enters the programming
contest world, in the sense that ACM regional/final contests (or IOI or
similar contests) allow programs written in the language to be submitted.
So far these 4 languages are really the only languages that can be used in
such a contest. There are other contests (like the IPSC) that does not put
restriction on programming languages, of course, but I think those are not
the target audience of the book anyway, judging from the algorithmic biase
of the book.

Regards,
Isaac.

Chris Mattern

2003-07-09 19:36:09 UTC

Post by William J. Jimenez
The book provides a concrete understanding of algorithmic techniques, such
as backtracking and dynamic programming, and advanced topics, such as number
theory and computational geometry. Tutorial material and sample programs
assist the reader, as well as support for all popular programming languages
(C, C++, Pascal, Java).

"All" popular languages? Since when do C, C++, Pascal and Java constitute "all"?

Since when does Pascal constitute "popular"? Not since Borland stopped doing
it, I think...

Chris Mattern

Richard Heathfield

2003-07-09 21:35:29 UTC

[...] Tutorial material and sample
programs assist the reader, as well as support for all popular
programming languages (C, C++, Pascal, Java).

"All" popular languages? Since when do C, C++, Pascal and Java constitute "all"?

Since when does Pascal constitute "popular"? Not since Borland stopped
doing it, I think...

Borland's flagship product, Delphi, is based very firmly on Pascal.

Ben Pfaff

2003-07-09 21:38:10 UTC

[...] Tutorial material and sample
programs assist the reader, as well as support for all popular
programming languages (C, C++, Pascal, Java).

"All" popular languages? Since when do C, C++, Pascal and Java constitute "all"?

Since when does Pascal constitute "popular"? Not since Borland stopped
doing it, I think...

Borland's flagship product, Delphi, is based very firmly on Pascal.

Delphi : Pascal :: C++ : C.

--
<***@cs.stanford.edu> <***@msu.edu> <***@debian.org> <***@gnu.org>
Stanford Ph.D. Candidate - MSU Alumnus - Debian Maintainer - GNU Developer
www.benpfaff.org

Craig

2003-07-10 13:14:57 UTC

Post by Ben Pfaff

[...] Tutorial material and sample
programs assist the reader, as well as support for all popular
programming languages (C, C++, Pascal, Java).

"All" popular languages? Since when do C, C++, Pascal and Java constitute "all"?

Since when does Pascal constitute "popular"? Not since Borland stopped
doing it, I think...

Borland's flagship product, Delphi, is based very firmly on Pascal.

Delphi : Pascal :: C++ : C.

I would wager so far as to say perl is rather popular. COBOL is
certainly well-used, too. Why aren't these included in the
competition? What about languages like ML and OCaml, when can and do
beat languages like java and C++ in programming contests?

Danny Kodicek

2003-07-10 13:57:31 UTC

Post by Craig

Post by Ben Pfaff

[...] Tutorial material and sample
programs assist the reader, as well as support for all popular
programming languages (C, C++, Pascal, Java).

"All" popular languages? Since when do C, C++, Pascal and Java

constitute

Post by Craig

Post by Ben Pfaff

Post by mensanator
"all"?

Since when does Pascal constitute "popular"? Not since Borland stopped
doing it, I think...

Borland's flagship product, Delphi, is based very firmly on Pascal.

Delphi : Pascal :: C++ : C.

Or, for that matter, the excellent and unjustly ignored Lingo.

Danny

g***@cs.uwa.edu.au

2003-07-11 03:46:33 UTC

In comp.programming.contests Craig <***@yahoo.com> wrote:
: I would wager so far as to say perl is rather popular. COBOL is
: certainly well-used, too. Why aren't these included in the
: competition? What about languages like ML and OCaml, when can and do
: beat languages like java and C++ in programming contests?

If teams were allowed to use modern functional languages, those
using the four languages mentioned (which would be the vast majority
of teams), simply couldn't compete. (and yes, I say this from direct
experience) Presumably, the desire to attract as many entrants as
possible is behind the decision not to allow languages that are
well-suited to the task.

Once you've decided to limit languages, there are two big reasons to
limit them severely: Firstly, you can't allow submission of
binaries, so each competition site must have a standardised install
of the right language, and that standard must be clearly detailed to
competitors before the event, and secondly, the more languages you
add to the list, the harder it is to justify your decision on where
to draw the line, and the more it appears arbitrary and politically
motivated.

On the other hand, you need to ensure that every would-be competitor
knows at least one language on your list, so you find the smallest
possible set of languages that covers every (or almost every)
first-year software engineering syllabus.

You end up with those four.

The selection process is internally consistent, but the basic
premise of disallowing the tools that are right for the job seems
very shortsighted and not in the competitors' best interests.

-Greg

Isaac To

2003-07-11 05:50:14 UTC

gregm> If teams were allowed to use modern functional languages, those
gregm> using the four languages mentioned (which would be the vast
gregm> majority of teams), simply couldn't compete. (and yes, I say this
gregm> from direct experience) Presumably, the desire to attract as many
gregm> entrants as possible is behind the decision not to allow
gregm> languages that are well-suited to the task.

Hm... I really want to see the difference, since while I have no big
exposure to such language, I want to know how good they are actually as
compared to C++. Your idea about functional programming seems so much in
contrast with what I see in C++: I'm convinced that the C++ functional
constructs obscures the program so much that it is not worth writing during
contests (and not worth using in general). I want to see it in action. Can
you point me to any place showing the ML or OCAML code that does something
typical in programming contests, like doing a DFS, max-flow, dynamic
programming or shortest path?

Regards,
Isaac.

g***@cs.uwa.edu.au

2003-07-14 07:52:02 UTC

In comp.theory Isaac To <***@csis.hku.hk> wrote:
:>>>>> "gregm" == gregm <***@cs.uwa.edu.au> writes:

: gregm> If teams were allowed to use modern functional languages, those
: gregm> using the four languages mentioned (which would be the vast
: gregm> majority of teams), simply couldn't compete. (and yes, I say this
: gregm> from direct experience)

: Your idea about functional programming seems so much in contrast with
: what I see in C++: I'm convinced that the C++ functional constructs
: obscures the program so much that it is not worth writing during
: contests (and not worth using in general).

That is my impression of C++, too.

: I want to see it in action. Can you point me to any place showing the
: ML or OCAML code that does something typical in programming contests,
: like doing a DFS, max-flow, dynamic programming or shortest path?

We're Haskellers over here, I hope you don't mind. This is a Haskell
solution to one of the questions at our regional last year. It was
written after the event by a student whose team decided not to attempt
this question when constrained to C/C++/Java/Pascal. :)

The question is here:

http://elena.ait.ac.nz/homepages/acm_contest/2002/Parties.pdf

The code is below - it is the work of 15 minutes and doesn't contain any
documentation. It's almost short enough not to need it, but I'll just
explain what the maps and arrays are, because their names are not
obvious:

ids is a FiniteMap mapping employee id strings to numbers.

socs is an array mapping an employee number to sociability.

bosses is an array mapping an employee number to the list of employee
numbers who that employee directly oversees.

bestwith maps an employee number to the best sociability score for that
employee's branch of the hierarchy with that employee attending.

bestwithout maps an employee number to the best sociability score for that
employee's branch of the hierarchy without that employee attending.

I'll be happy to explain anything else that isn't clear.

-Greg

--------------------------------------------------------------------------

import Array
import Data.FiniteMap

main = do input <- readFile "Party.in"
(writeFile "Party.out")$output$process$parse$lines$input

parse ("#":_) = []
parse (name:number:rest) = (name,emps,map parseemp xs):(parse ys)
where emps=read number
(xs,ys)=splitAt emps rest

parseemp str = (idnum,read soc,boss)
where [idnum,soc,boss] = words str

output = unlines.(map outputcomp)
where outputcomp (name,score) = name++": "++(show score)

process = map docomp

docomp (name,size,emps) = (name,bw ceo)
where (idents,socents,bossents) = unzip3 (map format (zip [1..] emps))
format (number,(idnum,soc,boss)) = ((idnum,number),
(number,soc),
(bossnum,number)
)
where Just bossnum = lookupFM ids boss
ids = listToFM (dummy:idents) where dummy = ("-",0)
socs = array (1,size) socents
bosses = accumArray (flip (:)) [] (0,size) bossents
bestwith = array (1,size) [(i,bw i)|i<-[1..size]]
bestwithout = array (1,size) [(i,bwo i)|i<-[1..size]]
bw i = (socs!i) + sum (map (bestwithout!) (bosses!i))
bwo i = sum (map best (bosses!i))
best i = max (bestwith!i) (bestwithout!i)
ceo = head (bosses!0)

Krzysan

2003-07-15 18:34:02 UTC

Post by Isaac To
gregm> If teams were allowed to use modern functional languages, those
gregm> using the four languages mentioned (which would be the vast
gregm> majority of teams), simply couldn't compete. (and yes, I say this
gregm> from direct experience) Presumably, the desire to attract as many
gregm> entrants as possible is behind the decision not to allow
gregm> languages that are well-suited to the task.
Hm... I really want to see the difference, since while I have no big
exposure to such language, I want to know how good they are actually as
compared to C++. Your idea about functional programming seems so much in
contrast with what I see in C++: I'm convinced that the C++ functional
constructs obscures the program so much that it is not worth writing during
contests (and not worth using in general). I want to see it in action.

Can

Post by Isaac To
you point me to any place showing the ML or OCAML code that does something
typical in programming contests, like doing a DFS, max-flow, dynamic
programming or shortest path?
Regards,
Isaac.

In Poland there once a year there is an online contest where you can use
OCaml (Pascal, C and C++ as well, I'm not sure about Java). Personally I
miss Scheme here (compiled with Bigloo).

Regards
Christopher Duleba

Krzysan

2003-07-15 18:37:42 UTC

Can

In Poland there is once a year an online contest where you can use
OCaml (Pascal, C and C++ as well, I'm not sure about Java). Personally I
miss Scheme here (compiled with Bigloo).

Regards
Christopher Duleba

Gordon Cormack

2003-07-14 01:23:28 UTC