[an error occurred while processing this directive]
Web-ring: http://uva.onlinejudge.org; http://www.lulu.com/product/paperback/competitive-programming/12110025; https://sites.google.com/site/stevenhalim; http://acm.uva.es/board; http://acmicpc-live-archive.uva.es/nuevoportal; http://www.acm.inf.ethz.ch/ProblemSetArchive.html; http://www.programming-challenges.com; http://felix-halim.net; http://www.acmsolver.org; http://www.acmbeginner.tk; http://www.harvestsoft.net; http://spoj.sphere.pl; http://acm.pku.edu.cn/judgeonline; http://www.algorithmist.com; http://www.karrels.org/Ed/ACM; http://www.inf.bme.hu/contests/tasks; http://contest.mff.cuni.cz/archive; http://www.cs.sunysb.edu/~algorith; http://olympiads.win.tue.nl/ioi; http://ace.delos.com/usacogate; http://uvatoolkit.com
Hello, my name is Steven from Indonesia. This website contains explanation to hundreds (not all) problems in University of Valladolid (UVa) Online Judge and it's twin sister ACM-ICPC Live Archive Online Judge, as well as some tips and tricks for doing competitive programming. Most of the problems that are available in both Online Judges were from past ACM International Collegiate Programming Contest (Regional or World Finals). Those who want to compete in this competition (or other programming contests) should try this Online Judge. There are other sections in this website that are not related to UVa Online Judge or competitive programming, such as: my research (viz), my teaching, please browse them too if you want :).
Aug 10): Me and my brother Felix wrote a book about programming
contest :). You can buy the book via:
Very Important Note:
Very Important Note:
Frequently Asked Questions
Q1: What is this website all
The Answers :)
This website is dedicated for the user of ACM Valladolid Online Judge (http://icpcres.ecs.baylor.edu/onlinejudge) and it's twin sister ACM-ICPC Live Archive Online Judge (http://acmicpc-live-archive.uva.es/nuevoportal). Both Online Judges are very useful for those who are preparing for ACM International Collegiate Programming Contest (http://icpc.baylor.edu/icpc) as well as hobbyist who likes problem solving using computer algorithms.
No. This website is hosted in my school website, not funded
by anyone else or any organization.
The first time I knew about UVa Online Judge was around early 2000. Around year 2001, I just followed my friend's idea (Ilham Winata Kurnia) to build a website which contain hints for UVa Online Judge problems. It had evolved step by step to reach this state.
However, I admit that the original idea should be credited to Ilham, thanks :).
I do not care..., reasons:
1. This website is officially linked
from the old UVa online judge page (thanks to Ahmed Shamsul Arefin for his suggestion
that this website should be linked from UVa and to Prof Miguel Revilla
and his UVa online judge team who added the link).
I think I am an average programmer, not the "red coder" (TopCoder term).
In the past, I joined several programming contests, National (Indonesian/Singapore level) and International (Asean level), such as: ISSC 99 (Singapore), ACM ICPC 2001 (Singapore), 2003 (Aizu, Japan), and 2004 (Shanghai, China). But truthfully, I never got 1st place in any contest that I have joined... Year 2004 was my last year participating in ACM ICPC as a contestant.
However, after about 4 years of hibernation (early 2005 - late 2008), I revived my competitive programming interest by helping the organization of ACM ICPC Singapore in NUS, in December 2007, then coaching and lead NUS SoC team 2 and 3 to Kuala Lumpur, Malaysia, in December 2008. Now, I have turned this hobby into real profession! I teach an undergraduate course titled "Competitive Programming" in January-April 2009 and will do that again next year in January-April 2010.
Currently, the contents of this website are hints for easy to medium difficulty problems (In this online judge, those easy to medium problems constitute approximately 30-40% problems per volume...). Most of the time, you will not find solution(s) for hard problems here. However, I will start increasing the level of problem difficulties discussed in this website as I have gained more experience by now (early 2009).
Hours of hard work (in the past-up to 2005) had been put to make this website as it is now, but this was not solely my own effort since I also received help from colleagues all around the world.
However, many of you have realized that this website were in hibernation mode for 2.5 years (early 2005-mid 2007...). That hibernation period made me realize that it is quite unlikely that I will be able to provide hints for all problems in the UVa online judge. The number of problems will keep growing and I do not have the much-needed 'free' time that I have when I was still an undergraduate student. My main commitments are now my research and my teaching duties.
I eventually did one major update around mid May 2007 and then declare it static. No more update will be done.... However, at its current state, I believe this website will still be beneficial for new programmers for many years to come even though experts in programming will find that this page is outdated.
This website, however, will be updated again in 2009 as I use this online judge as teaching material for an undergraduate course that I teach: "Competitive Programming". :)
1. Read the problems first and try
to solve it by yourself.
Refer to references in the competitive programming section of this website. These books are very likely available in your school computer science library or you can buy them online. Try amazon.com
I am (very) busy nowadays. So it is best that you put your queries to UVa message board and hope that someone will reply. Thanks for your understanding.
Hm... this has been a problem from time to time. Some Computer Science students are actually given a assignments from this Online Judge (like what I am doing with my students now) and sometimes they play cheat by asking me directly the accepted source code. Some people ask accepted source codes to increase their rank list easily. This is not acceptable either. I have decided that I will not give source code to strangers...
That column is used to indicate the difficulty of the problem. It is my own subjective opinion. Sometimes I feel that a problem is very difficult when others do not feel the same way, and vice versa. However, you can at least use it to roughly gauge how difficult a problem is.
This is how I roughly rate it:
Yes they are. I have a long list of people who help me solving problems in this online judge. I have tried my best to acknowledge their contributions by writing their name for that particular problem. Thanks Guys :).
This contribution section is alive again. If you want to submit hints, send me an email (stevenhalim, email provider gmail) with subject header: "UVa Hints".
Appendix - A note for programmers who are solving problems in UVa Online Judge
I want to link online judge problems like UVa Online Judge with my current research.
In UVa Online Judge, programmers must use exact algorithm to solve the given problem, otherwise you will very likely get Wrong Answer (WA) if your solution has some probabilistic element inside. However, even though competitive (fast + correct) coding, programming tricks, collection of good and efficient exact algorithms are very useful especially for those who wants to be a software engineers in the future, they are simply not enough...
It is because, unfortunately, there are too many real life problems in this world that are "too hard" to be solved exactly. These problems belongs to NP-hard category (refer to famous book by Garey & Johnson 1979). These problems are intractable since current computing power (and even future computing power) won't likely be able to solve these kind of problems within a reasonable amount of time (the time needed to solve them has exponential growth rate).
You can argue that you have solved several NP-hard problems found in UVa online judge, but remember that those problems has a problem size constraint (they are 'small') or other simplifying constraints. An example: problem 116 (Unidirectional TSP), is actually a modified version of the original NP-hard Traveling Salesman Problem (TSP).
In my research, I am is now dealing with these NP-hard combinatorial optimization problems. Nowadays, computer scientist uses stochastic local search (metaheuristic) algorithms to solve them. This is an exciting research field and I invite you to take a look =).