As I've spent quite a while in practice room 1 recently, looking at hundreds of programs (and challenging some of them), I've seen a lot code that is needlessly complicated. On this page, I'll give some advice how to get your programs shorter, faster and less errorprone. Basically most of the advice is to use the library that comes with each programming language. Note that I can't code C#, so my examples will be in C++/Java only, but since C# has an amazing similarity to Java...
I'll discuss some issues by taking the easy problem "Pencil" in practice room 1 as an example. The input to the problem is an array of up to 50 integers in the range -1000 to 1000 (inclusive). The goal is to find the minimum distance to zero of any of the input numbers. Examples: input { 3, -5, 2 } has result 2 and input { 4, -3, 11 } has result 3.
Many times I have seen programs similar to this one:
1: int bestPencil ( int[] deviations ) {
2: if( deviations.length == 0 )
3: return 0;
4: int best = 1001;
5: for( int i=0; i<deviations.length; ++i ){
6: int temp = deviations[ i ];
7: if( temp == 0 )
8: return 0;
9: if( temp < 0 )
10: temp = temp * -1;
11: if( temp < best )
12: best = temp;
13: }
14: return best;
15: }
This program is correct, but of course I've also seen a lot of bugs in programs (but this should be covered by another tutorial, let me just say that many people incorrectly compute -5 for the input { -5 }. Look at some successfully challenged submissions in the practice room). Now what would I change in the above program?
First of all, the special case that the array is empty doesn't need to be handled (lines 2-3). Why? Because an empty array is not a valid input and the input is guaranteed to be valid. Also, it's of course not defined that in this case the answer thould be zero, don't know where people got this idea from. Some return -1 or even throw an Exception. Just remove lines 2-3.
The special case that a zero occurs in the input doesn't need to be handled by extra code (lines 7-8). The program would be correct without it. Of course it would check the remaining numbers, too, which might be slower. But there are only 50 numbers anyway, no need for any optimization! Furthermore, if there are no zeros, then this actually slows the program down a bit.
I'd write temp = -temp; or temp *= -1; in line 10.
Even easier, the distance of a number from zero is called the absolute value of that number and there are library functions you can use. The lines 9-10 can simply be replaced by temp = abs( temp );temp = Math.abs( temp );
You can use the min-function of the library to replace lines 11-12 by best = Math.min( best, temp );best = min( best, temp );
You don't need to use a temporary variable, especialy if you use the library functions I mentioned (if you don't use them, a temporary variable is indeed good, otherwise you might have to repeat lots of long code.
If you apply the tips, the program now looks like this:
1: int bestPencil ( int[] deviations ) {
2: int best = 1001;
3: for( int i=0; i<deviations.length; ++i )
4: best = Math.min( best, Math.abs( deviations[ i ] ));
5: return best;
6: }
If you're new to programming, this might be a bit confusing because several things happen in just one line. Don't worry, you'll get used to it fast if you try to. The main things you should believe by know:
Writing long code takes more time and gives you more opportunities to make mistakes.
Doing unnecessary things makes your program longer.
Knowing and using library functions can do miracles for you. It's fast to use them and they probably don't have bugs.
Another solution for the problem is to first turn every value in the array into its absolute value, then to sort the array and simply take the first element:
1: int bestPencil ( int[] deviations ) {
2: for( int i=0; i<deviations.length; ++i )
3: deviations[ i ] = Math.abs( deviations[ i ] );
4: Arrays.sort( deviations );
5: return deviations[ 0 ];
6: }
As a general advice, sorting can make many things easier and it's not that expensive. The library functions run in time
For finding the minimum or maximum, sorting is an overkill and a simple loop would be enough. However, it's usually faster and less errorprone to just call a library function and then just pick the right element. And sometimes you'll want to have the array sorted anyway and minimum/maximum is just one more reason to have it sorted. For the median, linear time algorithms exists, but are much more complicated to code. Almost never worth the pain. For the minimum-difference-pair, I believe the sorting method is optimal.
In general, it often helps to think "What if the array would be sorted? Would that make my life easier?". And don't forget: the library already provides fast, correct and easy-to-use sorting functionality, there's absolutely no reason to write your own sorting code. You'll only lose time and make mistakes.
Now how do you get to know the library that comes with your language? Here are some references I know. If you know another one (especially for C#), please tell me.
Sun: Java API - Note that this link goes to Java 1.4 and TopCoder so far uses Java 1.3, so if you see a "Since: 1.4" somewhere (for example in java.lang.String.replaceAll(...)) then you can't use it yet. TopCoder is currently evaluating if they can switch to Java 1.4.
Nicolai Josuttis: The C++ Standard Library : A Tutorial and Reference - This book is very very good. And the author sits in the standardization committee. Do I have to say more?
Rogue Wave: Standard C++ Library Class Reference - Even though it's from a company, this information is - as far as I know - conform with the official C++ standard library.
SGI: C++ Standard Template Library Programmer's Guide - Same here, also seems to fulfill the standard. What's more: they have added some stuff like hash_set, and they are also supported on the TopCoder server.
C++ Reference The iostream part is quite nice, but the STL part is missing so far.
Ok, now that you know where you can get the information, I'll give you some advice on what to look at. Learn how to use this stuff, it's so worth it, I promise.
Java - Look what the classes java.lang.Math and java.lang.String can do for you. Also, you'll find converters between data types in other classes of the package java.lang, for example Integer.parseInt(...) which takes a String and returns an int. Very useful are some classes in the package java.util, in particular the following four, which you can see used very often in my Division 2 solutions. One downside Java has is that TreeSet, TreeMap, etc all work on Objects, so if you want to use basic values like int or boolean, then you have to convert them to Objects in one way or the other (for example String s = "" + i;Integer iObj = new Integer( i );
StringTokenizer - Powerful to split Strings into parts, makes life a lot easier sometimes.
Arrays - For sorting, searching, and some other stuff.
TreeSet - To collect a bunch of items without having duplicates, for fast lookup whether you've already seen an item, for having the items in sorted order at the end, etc.
TreeMap - To be able to collect some data for some items. Example: to store the weight of some people where the people are referenced by their names as Strings. This is similar to an array, but your indices are not limited to non-negative integers. They can be strings, sets, anything. Plus, if you do use integers as indices but they can range from, say, 1 to 1,000,000,000 then you can't have an array that big. But if you know you will only use a few of them, then a TreeMap will work fine.
C++ - I won't repeat what they're good for, you can read that in the Java part above, but here are the names in C++: The class template set<...> is similar to TreeSet, map<...> is similar to TreeMap and when you include <algorithms> you have access to sweet things like sort(...), binary_search(...), min_element(...) etc. Just browse the resources I gave you earlier to find more treasures. To convert between strings and numbers, I usually use istringstream or ostringstream objects, but the good old char[]/sscanf(...)/sprintf(...) combination is still useful sometimes.
C# - ???
Make sure that you get all extreme cases right. For example, I've seen many solutions to the Pencil problem that could handle it if the input contained some negative numbers among some positive ones. But many failed when given a single negative number as input. People tend to think too big. Very often it's the smallest cases where people fail. In the same practice room, a lot of solutions for the medium problem fail if N=1 or N=2. So my advice: check if it works for a single number or for N=1 or for an empty string or array or for N=0, whatever is the smallest valid input. If negative numbers are allowed, try a single negative number. Try zero alone.
Also check the largest valid inputs. If you're not careful enough, your algorithm might be way to slow. Or equivalently bad, you might walk out of bounds of an array. For example, I've seen a solution for the medium problem in practice room 1 with an int[10000] and then the person filled the array from indices 0 to N. But N could be 10000, and it was Java, so he threw an exception and lost all points. General advice for this: Always make your arrays a bit longer than needed, it can't hurt, but might save you.
Don't handle extreme cases that can't occur. In the Pencil problem, quite a lot of people immediately return zero if the input array is empty. But an empty array is invalid input, this can never happen. In the medium problem, some solutions check for N=0, when it was unnecessary because that's no valid input (depending on your algorithm it might be necessary, for example if you have a recursive solution where N is decremented). Writing extra code here is wasted time and it only introduces an opportunity to ruin everything with a bug in code that shouldn't be there.
That said, I'd recommend to always look very carefully at the specification of what a valid input is, what the extreme cases are. Don't handle too few cases, but also don't handle too many.
And before I forget it: Read the match editorials, especially the "Problem Set Analysis & Opinion" and the excellent "Lessons Learned the Hard Way". They discuss how people failed and how the problems could've been solved. Very valuable.
Some people may disagree with this, but this is my opinion: I never submit a program before it correctly solves at least *all examples* given in the problem statement. Never. Sometimes I even add one or two test cases, mostly extreme cases. I fail a lot less often since I adopted this strategy (16 correct out of 17 submissions in my last 7 contests (SRMs 84-91), yaeh ;-). Of course there's the exception when I know that an example is wrong, but then I try to correct it.
My last advice: Go to the practice rooms and try to apply the tips. If you have solved a problem, try to solve it more elegantly with a shorter program*. Look how other people did it. Try to learn from the more experienced programmers. Don't be too shy to ask people for help if you don't understand something or if you don't see how on earth somebody managed to successfully challenge you.
*: No, this does not mean that I suggest to use variable names that are just one character long, actually I think this is a bad idea unless you use a variable name for a standard task (for example, I always use i and j as the coordinates of matrices).