NUS HomeMethods to Solve
Home 1 2 3 4 5 6 7 8 9 C0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 A


This website is last updated on: 04 May 2009 04:07:03 PM

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 :).

New (9 Aug 10): Me and my brother Felix wrote a book about programming contest :). You can buy the book via:
http://www.lulu.com/product/paperback/competitive-programming/12110025
More details on:
https://sites.google.com/site/stevenhalim


(4 May 09): Methods to Solve now contains > 1000 hints =)
This "Methods to Solve" web pages have been around since mid 2001-now.
It will remain as it is for few years ahead. Future hints will be incorporated into "Competitive Programming" book.

Very Important Note:
If you want to copy anything from this website and distribute it either for profit or non profit,
you need to ask my permission first and must cite this website. Thanks for your understanding :)

My UVa Online Judge status:
533
solved before server migration, currently "only" 249.
(rank 594 as of 27/04/09 - will go up again soon, probably top 200),
(details).

My UVa Online Judge volume by volume statistics

VOL: AVAILABLE HINTS

VOL: AVAILABLE HINTS

1: 52 100: 44
2: 27 101: 43
3: 51 102: 31
4: 71 103: 30
5: 45 104: 27
6: 36 105: 36
7: 36 106: 53
8: 48 107: 30

9: 29

108: 30
- 109: 37
- 110: 44
- 111: 35
- 112: 40
- 113: 30
- 114: 41
- 115: 55
- 116: 00
~395 hints so far ~606 hints so far

Alternative view: by category (but not up to date)

Total: > 1000+ hints available.

My ACM-ICPC Live Archive Online Judge status: 21 solved.

Click here to access hints in this Live Archive Online Judge.

Some of the hints are detailed but some are just general hint. I cannot maintain the same level of writing throughout all hints because some of the hints are written by other people, not by me.

Note: please accept the fact that you will be spoiled a lot if you read the hints before attempting the problem by yourself :$.

Google
Find your hints here:
Web www.comp.nus.edu.sg

Frequently Asked Questions

Q1: What is this website all about?
Q2: Is this website sponsored by some organizations?
Q3: Who inspired you to built website like this?
Q4: There are some other websites which copy your idea, what is your opinion about this?
Q5: Who are you anyway? How good are you in programming?
Q6: How much efforts have been (and will be) spent on maintaining this website?
Q7: How to use this website?
Q8: I want to read a good books on algorithm, can you recommend me?
Q9: Hm... I need help regarding some problems... Can I contact you? How do I contact you?

Q10: I can't understand your hint, can I ask for your source code?
Q11: In the list of problems, you have a column with number 1 to 9, what is it?
Q12: Is there is other people who help you?
Q13: Hey... I also want to contribute something, how can I help you?

The Answers :)

Q1: What is this website all about?

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.

Q2: Is this website sponsored by some organizations?

No. This website is hosted in my school website, not funded by anyone else or any organization.
So, thank you School of Computing, National University of Singapore.

Q3: Who inspired you to built website like this?

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 :).

Q4: There are some other websites which copy your idea, what is your opinion about this?

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).
2. Google searches on popular online judge terms point to this website =).
3. Those other website complements this website, especially for many other problems that I have not solve yet.

Q5: Who are you anyway? How good are you in programming?

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).

Q6: How much efforts have been (and will be) spent on maintaining this website?

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". :)

Q7: How to use this website?

1. Read the problems first and try to solve it by yourself.
2. If you stuck and don't know what to do, look at my explanation (if I already solve it).
3
. Fix your code & re-send your code, and hopefully this time you get accepted.

Q8: I want to read a good books on algorithm, can you recommend me?

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

Q9: Hm... I need help regarding some problems... Can I contact you? How do I contact you?

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.

Q10: I cannot understand your hint, can I ask for your source code?

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

Q11: In the list of problems, you have a column with number 1 to 9, what is it?

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:
1: Very very easy, 5 minutes should be enough.
2: Very easy.
3: Easy, typically a problem set should have at least one problem of level 2 or 3.
4: Standard classical problem, estimated time needed: 30 minutes - 1 hour.
5: Getting harder, requires more thinking or efforts than level 4.
6: Even harder than level 5.
7: This is the level where I can solve the problem but takes so much efforts, perhaps outside the max contest time (> 5 hours)
8: Understand the problem, but does not have the fast enough/effective algorithm.
9: Do not understand the problem and therefore, cannot code the solution (too hard for me at the moment)...
*: I have not read it yet.

Q12: Is there is other people who help you?

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 :).

Q13: Hey... I also want to contribute something, how can I help you?

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 =).


The screen shot of my SLS visualization tool Viz.
Click this link to explore more


This document, acmoj.html, has been accessed 224825 times since 29-Jul-08 11:14:53 SGT. This is the 22nd time it has been accessed today.

A total of 79475 different hosts have accessed this document in the last 2089 days; your host, 54.205.160.82, has accessed it 1 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.