ACMSolver :: Art of Programming Contest, Tips and Tricks for C, C++, Java

A long time ago, in 2002 I started the website of “ACMSOLVER.ORG”. Then in 2005, the “Art of Programming Contest” came out. Now, it is time to have a better book of programming contest.  Steven and Felix have written this wonderful book (I ordered one for The University of Newcastle, Australia Programming Training Camp 2012). Here goes some slides. – Arefin 11-May-2012 (Newcastle, AUS)

Steven of course has many other hidden slides and techniques that will only be shown in CS3233 classes or if we are invited to give competitive programming workshop .

Week	Material (public version)	In the Book (CP 2)	Last Update
01, 11 Jan 2012	week01_introduction.pdf ; skillset.xls ; and paper on CS32333	Ch 1	03 Jan 2012
02, 18 Jan 2012	week02_ds_libraries.pdf	Ch 2	22 Dec 2011
03, 25 Jan 2012	week03_paradigms.pdf	Sec 3.1-3.4	23 Dec 2011
04, 01 Feb 2012	week04_dp_1.pdf	Sec 3.5	03 Jan 2012
05, 08 Feb 2012	week05_graph_1.pdf	Ch 4 (except Sec 4.6 + 4.7.4)	03 Jan 2012
06, 15 Feb 2012	week06_dp_2.pdf	Sec 3.5, 4.7.1, 5.4, 5.6, 6.5, 8.4	04 Jan 2012
/	RECESS WEEK	Time to catch up	/
07, 29 Feb 2012	mid-semester team contest	Half	/
08, 07 Mar 2012	week08_graph_2.pdf	Sec 4.6 + 4.7.4	31 Jan 2012
09, 14 Mar 2012	week09_maths.pdf	Ch 5	24 Feb 2012
10, 21 Mar 2012	week10_string.pdf	Ch 6	24 Feb 2012
11, 28 Mar 2012	week12_geometry.pdf	Ch 7	04 Apr 2011
12, 04 Apr 2012	hard stuffs (TBD) ; A* search, and IDA* search	Ch 8	N/A
13, 11 Apr 2012	final team contest	All (i.e. Ch 1-8)	/
/	NO FINAL EXAM	/	/

Computing terms for Chinese readers only (courtesy of: Acer Jing Wei, NUS)

#include <stdio.h>
int main()
{
int n, i, q, c, sz, idx, idx2, t1, t2, elteres, ce = 0;
while(1)
{
scanf("%d",&n);
if(!n) break;
printf("Case %d:\n",++ce);
int set[n], i = 0, q = 0;
sz = n;
while(n--)
{
scanf("%d",&set[i++]);
}
scanf("%d",&q);
while(q--)
{
scanf("%d",&c);

elteres = 2147483647;
for(idx = 0; idx < sz; idx++)
{
for(idx2 = idx + 1; idx2 < sz; idx2++)
{
if(  abs((set[idx] + set[idx2]) - c) < elteres  )
{
elteres = abs((set[idx] + set[idx2]) - c);
t1 = set[idx];
t2 = set[idx2];
}
}
}
printf("Closest sum to %d is %d.\n",c,t1+t2);
}
}
return 0;
}

by Zac Friggstad

The UVa Online Judge is a web site where you can try solving a number of algorithmic problems by implementing the solution in C, C++, Pascal or Java. The problems are usually described in a few paragraphs and some sample input and output is given for the purpose of illustration. For example, the problem might state that a weighted, undirected graph is given as input and you are to output the cost of the minimum spanning tree.

Solving a problem on the UVa Online Judge requires the following:

• Read and understand the problem statement
• Devise an algorithm to solve the problem
• Implement the algorithm in C, C++, Pascal or Java
• Finally, if you are convinced of its correctness, upload your code to have it judged.

The judging is automated (they use benchmark input and output files), so you can typically expect a response within a few seconds.

Getting Started: A Step-By-Step Introduction

The website is located at http://uva.onlinejudge.org/. After registering, choose the “browse problems” link on the lower-left side of the main page. From here, you will be asked to choose which problem set volume you want to browse.

Since this is a tutorial, I will suggest a problem. Follow the “Contest Volumes” link and select “Volume CXI” from here. We are going to try problem number “11172: Relational Operator”, so select it from the list.

Begin by reading the problem statement; hopefully you realize that the problem is absolutely trivial. Don’t worry, there are plenty of far more interesting problems on the archive. This problem is chosen to help you get used to the mechanics of the judge.

Make sure you are comfortable with the input and output specifications. When you submit the problem, the judge will supply their own input based on the input specification and the judge expects the output to conform to the specification in the problem description.

Begin by coding the problem. You should read the input from standard input and write to standard output (e.g. cin and cout in C++ or scanf() and printf() in C). For example, the following C++ code would solve this problem:

#include <iostream>
using namespace std;
int main() {
int n, a, b;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a >> b;
if (a < b) cout << '<' << endl;
else if (a > b) cout << '>' << endl;
else cout << '=' << endl;
}
return 0;
}

Try compiling this problem and testing it with the sample data; I suggest creating a file with the sample input and supplying this file to the program as standard input. For example, if the program name is ‘relational’ and the file name is ‘input.dat’, then you can test your code by executing ./relational < input.dat from a terminal window.

Does it work? Great! You are ready to try submitting it to the judge. In the upper-right corner of the problem description page you should see the graphic . Clicking on this will bring you to the submission page for this problem. Select the language you coded the problem in and upload the file using the upload tool. Once you are ready, click submit and hope for the best!

You can check the status of your submission by selecting the “My Submissions” link on the left side of the page. The “Verdict” heading will tell you if it was solved or if there was a problem (e.g. wrong answer, ran too long, crashed, too much memory was used, compile error, etc).

Now go ahead and solve some more problems!

[...]

Great question! As someone who has dabbled in programming contests a bit myself, I may have something to say.

[Let's get the standard disclaimer out of the way: contest programming is only loosely related to "programming in the real world", and while it tests algorithmic and problem-solving skills and the ability to come up with fast bug-free working code under time pressure, it does not necessarily correlate with being able to build large software projects, write maintainable code, etc (beyond the fact that well-structured programs are easier to debug).]

Now for some answers:

* C++/Java are more common than other languages in the real world as well, so you’d expect to see a higher proportion anywhere. (But it’s even higher in the contest population.)
* Many of these participants are students, or got into contests as students, and C++/Java are more common “first languages” that students learn. (Undergrad students these days may start with Scheme, Haskell, Python, etc., but high-schoolers (often self-taught) less often.) In fact, many of the Eastern European participants still use Pascal, and are more amazing with it than the rest of us will ever be with any language. [...]

DOMjudge is an automated judge system to run programming contests. It has a mechanism to submit problem solutions, have them judged fully automatically and provides (web)interfaces for teams, the jury and the general public.

DOMjudge is meant to be used in programming contests like the ACM ICPC programming contests, where teams are on-site and there is a fixed problem set and timeframe. It is not meant for on-line submission systems like the UVa online judge or as courseware, although other people have modified it to that end.

Key aspects include:

• Lightweight, depends on standard software to do its task
• Webinterface for portability and simplicity
• Scalable: distributed judging is easy
• Modular system for plugging in languages/compilers
• Features rejudging, clarifications, detailed submission/judging info
• Designed with security in mind
• Compatible with ICPC Validator Standard
• It’s Open Source, Free Software

It has been used in many live contests, including:

• Utrechts Kampioenschap Programmeren 2004 – 2009
• Benelux Algorithm Programming Contest 2004, 2006, 2007, 2009
• German Collegiate Programming Contest 2010
• ACM ICPC NWERC 2007, 2008, 2009
• ACM ICPC SWERC 2008

There is also the online demo to see a live DOMjudge setup (with some non-working details).

Requirements

This is a (rough) list of the requirements for DOMjudge.

• At least one machine running Linux, with local root access
• Apache web server with PHP 5 and PHP command line interface
• MySQL database server version 4.1 or newer
• Compilers for the languages you want to support

For a complete list please refer to the administrator manual.

Download

The latest stable release is 3.1.0, dated 14 July 2010.

download here

[...]