|
Greater love has no one than
this, that he lay down his life for his friends...
Look for the series of story about a great love on top of your screen in
all volumes especially volume 1 until
volume 8...
This website is last updated on:
07 August 2008 12:01:18 PM
Web-ring:
http://acm.uva.es/p;
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
Hello, my name is
Steven from Indonesia. This
is my personal website which 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 data structures and algorithms so solve them. 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, such as: my research (viz),
my teaching,
my writing, and
my software, please browse them too if
you want :).
Methods to Solve will
no longer be updated after 18 May 2007
This "Methods to Solve"
web pages have been
around for 6 years (around mid 2001-mid 2007). However, I do not have time to
update it anymore so I have decided to freeze the development of these
pages.
I want to use this opportunity to thank everyone who has contributed in one way or another
to make this web pages as they are now. I believe that the materials
that already exist in these web pages will continue to be a good
resource for many other programmers around the world =).
Note: parts of the content of this website
are published in Ahmed Shamsul Arefin's book: Art of Programming
Contest.
Please take a look.
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 (rank 224 as of 20/04/07 - this will
constantly drop as I already retired),
(details).
My UVa Online Judge volume by volume statistics
Total: 580+ 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 :$.
|
Frequently Asked Questions
Q1: What is this website all
about?
Q2: Is this website sponsored by some organizations? What
about those ads/Christian quotes?
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://acm.uva.es/p/)
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? What about those ads/Christian quotes?
No. This is a personal website, not funded
by anyone or any organization.
However, I do gain some revenues via Google Ads on top of every pages.
I
think many people are seeing this page everyday and gain benefits by
reading the pages inside. If you like this website, you can (indirectly)
pay me
by clicking few advertisement above :). Thanks in advance.
Btw, I also have some Christian quotes on
top of every pages. These are my "eternal life advertisement". Read them,
and you have any enquiries, contact me:
stevenhalim at gmail dot com.
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 (but I have
decide to stop evolving it now).
However, I admit that the original idea
should be credited to Ilham.
Q4: There are some other websites
which copy your idea, what is your opinion about this?
I don't care..., reasons:
1. This website is officially linked
from UVa online judge (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). The 'other' websites
who just copy the content will not get this privilege.
2. Google searches on popular online judge terms points to this website
=).
3. Those other website complements this website, especially for many
other problems that I don't have hints yet.
Q5: Who are you anyway? How good
are you in programming?
I am just an average programmer. I am not
an expert, there are still hundreds people above my rank list in this online
judge and that number will keep increasing since I already retired and
don't solve problems like what I did in the past.
I did join 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.
If someday in the future
I returned again for this ACM ICPC contests, it will be either as coach
or as organizer, and not as contestant...
Moreover, currently I can only solve easy to medium
problems (In this online judge, those easy to medium problems constitute approximately 30-40% problems per volume...
see my statistic above), therefore most of the time, you will not
find solution(s) for hard problems here.
Maybe sometime in the future,
after I'm getting better in programming.
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
don't 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.
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 my bibliography in the
data structures, algorithms and 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?
Since I already retired from competitive
programming, it is rather unlikely that I will be able to think like
what I did in the past when given programming problems. Most
importantly, 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.
Thus, from now (20 April 2007) onwards, I
will not reply to e-mails related to UVa problems.
Q10: I can't 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 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 don't 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.
4: Getting harder.
5: Standard problem, estimated time needed: 30 minutes - 2 hour.
6: A very hard thinking / a lot of effort to solve it.
7: I still don't 100% understand the algorithm (Somebody help me with the
algo)
8: Understand the problem, but cannot code it (don't have the correct/fast
enough algo).
9: Don't understand the problem and therefore, cannot code it.
*: I haven't 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?
I do not accept e-mails that describes new
hints anymore. I will not be able to update them. However, I believe
that there are some other active websites that provide hints for
online judge problems, please submit to them instead.
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 958 times since 29-Jul-08 11:14:53 SGT.
This is the 34th time it has been accessed today.
A total of 449 different hosts have accessed this document in the
last 11 days; your host, 38.103.63.17, 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.
|
