TopCoder Training Camp >> Tutorials >> Basic (programming) tips

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

 

An Example

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?

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

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

  3. I'd write temp = -temp; or temp *= -1; in line 10.

  4. 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 ); (C++) or temp = Math.abs( temp ); (Java).

  5. You can use the min-function of the library to replace lines 11-12 by best = Math.min( best, temp ); (Java) or best = min( best, temp ); (C++). Note that this you only have to type the possible new minimum value only once this way. Btw, micro$oft was too stupid too include min and max at least for VC++, so you might have to do it on your own if you work with that crap. On the TopCoder server, they do exist, don't worry.

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

 

Sorting

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 O(n log n), so 50 is just a joke. Want to find the minimum (maximum) value? Sort and pick the first (last) element. Want to find the element that has equally many smaller and larger elements in the array (also called the median)? Sort and pick the middle element. Want to find the two numbers with the smallest difference but it takes too long to test all n(n-1)/2 pairs? Sort and only test the n-1 pairs of adjacent numbers in the array.

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.

 

Library References

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.

 

The most useful library parts

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.

 

Extreme cases

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.

 

Testing

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.

 

Final words

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


Stefan Pochmann
Last modified: Wed Jun 5 13:45:35 PDT 2002