Last updated on: 10 November 2008 06:01:31 PM

1. Techniques for parsing input data
2. Complete Search a.k.a Brute Force
3. Recursion / Backtracking plus Branch and Bound
4. Divide and Conquer / Transform and Conquer?
5. Optimizing your source code
7. Some solution paradigms
8. Overview on more specialized algorithms: mathematical, sorting, searching, greedy, dynamic programming, graph-related, computational geometry.

1. Techniques for parsing input data

In all programming contest, or more specifically, in all useful program, you need to read in input and process it. However, the input data can be as nasty as possible, and this can be very troublesome to parse.

If you spent too much time in coding how to parse the input efficiently and you are using C/C++ as your programming language, then this tip is for you. Let's see an example:

How to read the following input:

There are N lines, each lines always start with character '0' followed by '.', then unknown number of digits x, finally the line always terminated by three dots "...".

N
0.xxxx...

The fastest way to do it is:

#include <stdio.h>
char digits[100];

void main() {
  scanf("%d",&N);
  for (i=0; i<N; i++) {
    scanf("0.%[0-9]...",&digits); // surprised?
    printf("the digits are 0.%s\n",digits);
  }
}

Yeah, this is the trick that many C/C++ programmers doesn't aware of. Why I said C++ while scanf/printf is a standard C I/O routines? This is because many C++ programmers "forcing" themselves to use cin/cout all the time, without realizing that scanf/printf can still be used inside all C++ programs. Sadly, scanf/printf is declared as deprecated in the newest version of Microsoft Visual C++. I don't know why...

Mastery of programming language I/O routines will help you a lot in programming contests.

References:
-. Your programming language manuals :)

2. Complete Search a.k.a Brute Force

Keep It Short and Simple
Taken from USACO Training Gateway section 1.1.2

This is the most basic problem solving technique. Utilizing the fact that computer is actually very fast...

Solving a problem using complete search is based on the 'Keep It Simple, Stupid' / 'Keep It Short & Simple' (abbreviated as KISS) principle. The goal of solving contest problems is to write programs that work in the time allowed, whether or not there is a faster algorithm.

Complete search exploits the brute force, straight-forward, try-them-all method of finding the answer. This method should almost always be the first algorithm/solution you consider. If this works within time and space constraints, then do it: it's easy to code and usually easy to debug. This means you'll have more time to work on all the hard problems, where brute force doesn't work quickly enough.

In the case of a problem with only fewer than a couple million possibilities, iterate through each one of them, and see if the answer works.

Careful, Careful

Sometimes, it's not obvious that you use this methodology. Let's see the following examples to get the feeling of doing things in "brute force"

Party Lamps [IOI 98]

You are given N lamps and four switches. The first switch toggles all lamps, the second the even lamps, the third the odd lamps, and last switch toggles lamps 1,4,7,10,...

Given the number of lamps, N, the number of button presses made (up to 10,000), and the state of some of the lamps (e.g., lamp 7 is off), output all the possible states the lamps could be in.

Naively, for each button press, you have to try 4 possibilities, for a total of 4^10000 (about 10^6020), which means there's no way you could do complete search (this particular algorithm would exploit recursion).

Noticing that the order of the button presses does not matter gets this number down to about 10000^4 (about 10^16), still too big to completely search (but certainly closer by a factor of over 10^6000).

However, pressing a button twice is the same as pressing the button no times, so all you really have to check is pressing each button either 0 or 1 times. That's only 2^4 = 16 possibilities, surely a number of iterations solvable within the time limit.

The Clocks [IOI 94]

A group of nine clocks inhabits a 3 x 3 grid; each is set to 12:00, 3:00, 6:00, or 9:00. Your goal is to manipulate them all to read 12:00. Unfortunately, the only way you can manipulate the clocks is by one of nine different types of move, each one of which rotates a certain subset of the clocks 90 degrees clockwise.

Find the shortest sequence of moves which returns all the clocks to 12:00.

The 'obvious' thing to do is a recursive solution, which checks to see if there is a solution of 1 move, 2 moves, etc. until it finds a solution. This would take 9^k time, where k is the number of moves. Since k might be fairly large, this is not going to run with reasonable time constraints.

Note that the order of the moves does not matter. This reduces the time down to k^9, which isn't enough of an improvement.

However, since doing each move 4 times is the same as doing it no times, you know that no move will be done more than 3 times. Thus, there are only 49 possibilities, which is only 262,072, which, given the rule of thumb for run-time of more than 10,000,000 operations in a second, should work in time. The brute-force solution, given this insight, is perfectly adequate.

It is beautiful, isn't it? If you have this kind of reasoning ability. Many seemingly hard problems is eventually solvable using brute force :).

References:
-. USACO training gateway

3. Recursion

Do you realized that the statement: "I am who I am" in Exodus 3:14 is recursive.

Recursion is cool. Many algorithms need to be implemented recursively. A popular combinatorial brute force algorithm, backtracking, usually implemented recursively. After highlighting it's importance, lets study it.

Recursion is a function/procedure/method that calls itself again with a smaller range of arguments (break a problem into simpler problems) or with different arguments (it is useless if you use recursion with the same arguments). It keeps calling itself until something that is so simple / simpler than before (which we called base case), that can be solved easily or until an exit condition occurs.

A recursion must stop (actually, all program must terminate). In order to do so, a valid base case or end-condition must be reached. Improper coding will leads to stack overflow error.

You can determine whether a function recursive or not by looking at the source code. If in a function or procedure, it calls itself again, it's recursive type.

Why recursive calls is possible?

When a method/function/procedure is called:
– caller is suspended,
– "state" of caller saved,
– new space allocated for variables of new method.

With recursive call, same things happen.

Recursion is a powerful and elegant technique that can be used to solve a problem by solving a smaller problem of the same type. Many problems in Computer Science involves recursion and some of them are naturally recursive.

If one problem can be solved in both way (recursive or iterative), then choosing iterative version is a good idea since it is faster and doesn't consume a lot of memory. Examples: Factorial, Fibonacci, etc.

However, there are also problems that are can only be solved in recursive way or more efficient in recursive type or when it's iterative solutions are difficult to conceptualize. Examples: Tower of Hanoi, Searching (DFS, BFS), etc.

Types of recursion

There are 2 types of recursion, Linear recursion and multiple branch (Tree) recursion.

1. Linear recursion is a recursion whose order of growth is linear (not branched).
Example of Linear recursion is Factorial, defined by fac (n)=n * fac (n-1).

2. Tree recursion will branch to more than one node each step, growing up very quickly. It provides us a flexible ways to solve some logically difficult problem. It can be used to perform a Complete Search (To make the computer to do the trial and error). This recursion type has a quadratic or cubic or more order of growth and therefore, it is not suitable for solving "big" problems. It's limited to small. Examples: solving Tower of Hanoi, Searching (DFS, BFS), Fibonacci number, etc.

Some compilers can make some type of recursion to be iterative. One example is tail-recursion elimination. Tail-recursive is a type of recursive which the recursive call is the last command in that function/procedure. This

Tips on Recursion:

1. Recursion is very similar to mathematical induction.
2. You first see how you can solve the base case, for n=0 or for n=1.
3. Then you assume that you know how to solve the problem of size n-1, and you look for a way of obtaining the solution for the problem size n from the solution of size n-1.

When constructing a recursive solution, keep the following questions in mind:

1. How can you define the problem in term of a smaller problem of the same type?
2. How does each recursive call diminish the size of the problem?
3. What instance of the problem can serve as the base case?
4. As the problem size diminishes, will you reach this base case?

Sample of a very standard recursion, Factorial (in Java):

static int factorial(int n) {
   if (n==0)
      return 1;
   else
      return n*factorial(n-1);
}

References:
-. CLRS chapter 4, Recurrences

4. Divide and Conquer

Whatever man prays for, he prays for a miracle. Every prayer reduces itself to this
"Great God, grant that twice twos be not four"
(read as: two 2s or 2+2 != 4)
[DAA chapter 4]

This technique use analogy "smaller is simpler". Divide and conquer algorithms try to make problems simpler by dividing it to sub problems that can be solved easier than the main problem and then later it combine the results to produce a complete solution for the main problem.

Divide and Conquer algorithms: Quick Sort, Merge Sort, Binary Search.

Believe it or not, it is a general principle of designing algorithms. If you want to solve something, try thinking in Divide & Conquer way first.

Divide & Conquer has 3 main steps:

1. Divide data into parts
2. Find sub-solutions for each of the parts recursively (usually)
3. Construct the final answer for the original problem from the sub-solutions

In pseudo code, Divide and Conquer can be written like this:

DC(P) {
  if small(P) then
    return Solve(P);
  else {
    divide P into smaller instances P1,...,Pk, k>1;
    Apply DC to each of these subproblems;
    return combine(DC(P1),...,DC(Pk));
  }
}

Application of Divide & Conquer: Binary Search

Binary Search, is not actually follow the pattern of the full version of Divide & Conquer, since it never combine the sub problems solution anyway. However, lets use this example to illustrate the capability of this technique.

Binary Search will help you find an item in an array. The naive version is to scan through the array one by one (sequential search). Stopping when we found the item (success) or when we reach the end of array (failure). This is the simplest and the most inefficient way to find an element in an array. However, you will usually end up using this method because not every array is ordered, you need sorting algorithm to sort them first.

Binary search algorithm is using Divide and Conquer approach to reduce search space and stop when it found the item or when search space is empty.

Pre-requisite to use binary search is the array must be an ordered array, the most commonly used example of  ordered array for binary search is searching an item in a dictionary.

Efficiency of binary search is O(log n). This algorithm was named "binary" because it's behavior is to divide search space into 2 (binary) smaller parts.

Complete binary search algorithm:

1. Let a be an ordered array
   Let i be the start index
   Let j be the ending index
   Let aWord be the word we are looking for
2. Do a recursive binary search, starting with i=1
   and j=total elements in the array.
3. If i>j and we haven't found aWord, stop search, announce failure
4. If a[(i+j) div 2] equal to aWord then
      stop search, announce success
   else if a[(i+j) div 2] smaller than aWord then
      call binary search with i unchanged and j=(i+j) div 2
   else if a[(i+j) div 2] greater than aWord then
      call binary search with i=(i+j) div 2 and j unchanged

References:
-. DAA chapter 4
-. Any other algorithm books

5. Backtracking plus Branch and Bound

Backtracking is a recursive solution for combinatorial objects (Depth First Search). While Branch and Bound is a more sophisticated version of backtracking, done in Breadth First Search manner, and use heuristic functions to quickly prune unpromising search region.

Please read other references book regarding these two useful techniques.

6. Optimizing your source code

Your code must be fast. If it cannot be "fast", then it must at least "fast enough". If time limit is 1 minute and your currently program run in 1 minute 10 seconds, you may want to tweak here and there rather than overhaul the whole code again...

There are many tricks that you can use to optimize your code. Understanding computer hardware, especially I/O, memory, and cache behavior, can help you design a better program. Please do a Google search to find information regarding how to speed up your code using your preferred programming language.

Note: Redesigning your algorithm in a better way (like choosing an algorithm with better worst case order of growth, or choosing a faster data structures) always outperform any compiler-optimization trick. Every program is doing the most task in only about 10% of the code. Find this "critical code" and find a way to optimize it.

7. Some solution paradigms

Here is some things that you need to consider when designing your solution :)

Generating vs Filtering

Programs that generate lots of possible answers and then choose the ones that are correct (imagine an 8-queen solver) are filters. Those that hone in exactly on the correct answer without any false starts are generators. Generally, filters are easier (faster) to code and run slower. Do the math to see if a filter is good enough or if you need to try and create a generator.

Pre-Computation / Pre-Calculation

Sometimes it is helpful to generate tables or other data structures that enable the fastest possible lookup of a result. This is called Pre-Computation (in which one trades space for time). One might either compile Pre-Computed data into a program, calculate it when the program starts, or just remember results as you compute them. A program that must translate letters from upper to lower case when they are in upper case can do a very fast table lookup that requires no conditionals, for example. Contest problems often use prime numbers - many times it is practical to generate a long list of primes for use elsewhere in a program.

Decomposition (The hardest thing at programming contests)

While there are fewer than 20 basic algorithms used in contest problems, the challenge of combination problems that require a combination of two algorithms for solution is daunting. Try to separate the cues from different parts of the problem so that you can combine one algorithm with a loop or with another algorithm to solve different parts of the problem independently. Note that sometimes you can use the same algorithm twice on different (independent!) parts of your data to significantly improve your running time.

Symmetries

Many problems have symmetries (e.g., distance between a pair of points is often the same either way you traverse the points). Symmetries can be 2-way, 4-way, 8-way, and more. Try to exploit symmetries to reduce execution time.

For instance, with 4-way symmetry, you solve only one fourth of the problem and then write down the four solutions that share symmetry with the single answer (look out for self-symmetric solutions which should only be output once or twice, of course).

Solving forward vs backward

Surprisingly, many contest problems work far better when solved backwards than when using a frontal attack. Be on the lookout for processing data in reverse order or building an attack that looks at the data in some order or fashion other than the obvious.

Simplification or in technical terms: Problem Reduction

Some problems can be rephrased into a somewhat different problem such that if you solve the new problem, you either already have or can easily find the solution to the original one; of course, you should solve the easier of the two only. Alternatively, like induction, for some problems one can make a small change to the solution of a slightly smaller problem to find the full answer.

References:
-. USACO training gateway

What's next?

With these basic data structures (chapter 2) and basic techniques (chapter 3), you are able to solve majority of simple problems. Now you are ready to tackle an even harder problems using more sophisticated algorithms. But before that... lets enrich your mathematics. Computer Science and Mathematics are closely intertwined, so, stay tuned :D