Archive | Online Judge RSS feed for this section

11 March 2012 Comments Off

PDF slides Steven Halim’s Book

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)

13 January 2011 Comments Off

Easy ACM UVa problems

Problem No Problem Name
100 The 3n+1 problem
102 Ecological bin packing
113 Power of cryptography
136 Ugly numbers
190 Circle through three points
264 Count on Cantor
272 TEX qoutes
299 Train swapping
305 Joseph
353 Pesky Palindromes
369 Combinations
382 Perfection
401 Palindromes
406 Prime cuts
408 Uniform generator
424 Integer inquery
444 Encoder and decoder
458 The decoder
490 Rotating sequences
492 Pig latin
495 Fibonacci freeze
499 What’s the frequency, Kenneth?
530 Binomial showdown
541 Error correction
543 Goldbach’s conjecture
579 Clock Hands
591 Box of Bricks
609 DNA sorting
623 500!
686 Goldbach’s conjecture (II)
694 The Collatz sequence
713 Adding reversed numbers
729 The Hamming distance problem
834 Continued Fractions
10008 What’s Cryptanalysis?
10013 Super long sums
10018 Reverse and Add
10019 Funny Encryption Method
10035 Primary Arithmetic
10055 Hashmat the brave warrior
10062 Tell me the frequencies!
10070 Leap Year or Not Leap Year
10082 WERTYU
10101 Bangla numbers
10107 What is the median?
10110 Light more light
10161 Ant on a Chessboard
10200 Prime time
10235 Simply Emirp
10242 Fourth point!!
10252 Common Permutation
10282 Babel fish
10286 Trouble with a pentagon
10300 Ecological Premium
10302 Summation of Polynomials
10323 Factorial! You Must be Kidding!!!
10324 Zeros and Ones
10327 Flip sort
10370 Above average
10409 Die game
10420 List of conquests
10424 Love calculator
10432 Polygon inside a circle
10473 Simple base conversion
10515 Powers et al.
10611 The playboy chimp
10696 f91
10700 Camel trading
Tags: , , ,
29 August 2010 Comments Off

10487 – Closest Sum

#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;
}
Tags:
29 August 2010 Comments Off

Getting Started in UVa Online Judge

Getting Started in UVa Online Judge

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!

[...]

17 August 2010 Comments Off

Why programming competition contestants use C++ and Java?

Why programming competition contestants use C++ and Java?

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. [...]

16 August 2010 Comments Off

DOMjudge (alternative to PC^2) – an Automated Judge System

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:

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

[...]

Tags: