The Importance of Algorithms

By lbackstrom — topcoder member
Discuss this article in the forums

Introduction
The first step towards an understanding of why the study and knowledge of algorithms are so important is to define exactly what we
mean by an algorithm. According to the popular algorithms textbook Introduction to Algorithms (Second Edition by Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rivest, Clifford Stein), "an algorithm is any well­defined computational procedure that takes some value,
or set of values, as input and produces some value, or set of values as output." In other words, algorithms are like road maps for
accomplishing a given, well­defined task. So, a chunk of code that calculates the terms of the Fibonacci sequence is an implementation
of a particular algorithm. Even a simple function for adding two numbers is an algorithm in a sense, albeit a simple one.

Some algorithms, like those that compute the Fibonacci sequences, are intuitive and may be innately embedded into our logical
thinking and problem solving skills. However, for most of us, complex algorithms are best studied so we can use them as building
blocks for more efficient logical problem solving in the future. In fact, you may be surprised to learn just how many complex algorithms
people use every day when they check their e­mail or listen to music on their computers. This article will introduce some basic ideas
related to the analysis of algorithms, and then put these into practice with a few examples illustrating why it is important to know about
algorithms.

Runtime Analysis
One of the most important aspects of an algorithm is how fast it is. It is often easy to come up with an algorithm to solve a problem,
but if the algorithm is too slow, it’s back to the drawing board. Since the exact speed of an algorithm depends on where the algorithm is
run, as well as the exact details of its implementation, computer scientists typically talk about the runtime relative to the size of the
input. For example, if the input consists of N integers, an algorithm might have a runtime proportional to N2, represented as O(N2).
This means that if you were to run an implementation of the algorithm on your computer with an input of size N, it would take C*N2
seconds, where C is some constant that doesn’t change with the size of the input.

However, the execution time of many complex algorithms can vary due to factors other than the size of the input. For example, a
sorting algorithm may run much faster when given a set of integers that are already sorted than it would when given the same set of
integers in a random order. As a result, you often hear people talk about the worst­case runtime, or the average­case runtime. The
worst­case runtime is how long it would take for the algorithm to run if it were given the most insidious of all possible inputs. The
average­case runtime is the average of how long it would take the algorithm to run if it were given all possible inputs. Of the two, the
worst­case is often easier to reason about, and therefore is more frequently used as a benchmark for a given algorithm. The process of
determining the worst­case and average­case runtimes for a given algorithm can be tricky, since it is usually impossible to run an
algorithm on all possible inputs. There are many good online resources that can help you in estimating these values.

Approximate completion time for algorithms, N = 100

O(Log(N)) 10­7 seconds

O(N) 10­6 seconds

O(N*Log(N)) 10­5 seconds

O(N2) 10­4 seconds

O(N6) 3 minutes

O(2N) 1014 years.

O(N!) 10142 years.

Sorting
Sorting provides a good example of an algorithm that is very frequently used by computer scientists. The simplest way to sort a group
of items is to start by removing the smallest item from the group, and put it first. Then remove the next smallest, and put it next and
so on. Unfortunately, this algorithm is O(N2), meaning that the amount of time it takes is proportional to the number of items squared.
If you had to sort a billion things, this algorithm would take around 1018 operations. To put this in perspective, a desktop PC can do a
little bit over 109 operations per second, and would take years to finish sorting a billion things this way.

Luckily, there are a number of better algorithms (quicksort, heapsort and mergesort, for example) that have been devised over the
years, many of which have a runtime of O(N * Log(N)). This brings the number of operations required to sort a billion items down to a
reasonable number that even a cheap desktop could perform. Instead of a billion squared operations (1018) these algorithms require
only about 10 billion operations (1010), a factor of 100 million faster.

Shortest Path
Algorithms for finding the shortest path from one point to another have been researched for years. Applications abound, but lets keep
things simple by saying we want to find the shortest path from point A to point B in a city with just a few streets and intersections.
There are quite a few different algorithms that have been developed to solve such problems, all with different benefits and drawbacks.
Before we delve into them though, lets consider how long a naive algorithm – one that tries every conceivable option – would take to
run. If the algorithm considered every possible path from A to B (that didn’t go in circles), it would not finish in our lifetimes, even if A
and B were both in a small town. The runtime of this algorithm is exponential in the size of the input, meaning that it is O(CN) for some
C. Even for small values of C, CN becomes astronomical when N gets even moderately large.

One of the fastest algorithms for solving this problem has a runtime of O(E*V*Log(V)), where E is the number of road segments, and V
is the number of intersections. To put this in perspective, the algorithm would take about 2 seconds to find the shortest path in a city
with 10,000 intersections, and 20,000 road segments (there are usually about 2 road segments per intersection). The algorithm, known
as Djikstra’s Algorithm, is fairly complex, and requires the use of a data structure known as a priority queue. In some applications,
however, even this runtime is too slow (consider finding the shortest path from New York City to San Francisco – there are millions of
intersections in the US), and programmers try to do better by using what are known as heuristics. A heuristic is an approximation of
something that is relevant to the problem, and is often computed by an algorithm of its own. In the shortest path problem, for
example, it is useful to know approximately how far a point is from the destination. Knowing this allows for the development of faster
algorithms (such as A*, an algorithm that can sometimes run significantly faster than Djikstra’s algorithm) and so programmers come
up with heuristics to approximate this value. Doing so does not always improve the runtime of the algorithm in the worst case, but it
does make the algorithm faster in most real­world applications.

Approximate algorithms
Sometimes, however, even the most advanced algorithm, with the most advanced heuristics, on the fastest computers is too slow. In
this case, sacrifices must be made that relate to the correctness of the result. Rather than trying to get the shortest path, a
programmer might be satisfied to find a path that is at most 10% longer than the shortest path.

In fact, there are quite a few important problems for which the best­known algorithm that produces an optimal answer is insufficiently
slow for most purposes. The most famous group of these problems is called NP, which stands for non­deterministic polynomial (don’t
worry about what that means). When a problem is said to be NP­complete or NP­hard, it mean no one knows a good way to solve them
optimally. Furthermore, if someone did figure out an efficient algorithm for one NP­complete problem, that algorithm would be
applicable to all NP­complete problems.

A good example of an NP­hard problem is the famous traveling salesman problem. A salesman wants to visit N cities, and he knows
how long it takes to get from each city to each other city. The question is "how fast can he visit all of the cities?" Since the fastest
known algorithm for solving this problem is too slow – and many believe this will always be true – programmers look for sufficiently fast
algorithms that give good, but not optimal solutions.

Random Algorithms
Yet another approach to some problems is to randomize an algorithm is some way. While doing so does not improve the algorithm in
the worst case, it often makes very good algorithms in the average case. Quicksort is a good example of an algorithm where
randomization is often used. In the worst case, quicksort sorts a group of items in O(N2), where N is the number of items. If
randomization is incorporated into the algorithm, however, the chances of the worst case actually occurring become diminishingly small,
and on average, quicksort has a runtime of O(N*Log(N)). Other algorithms guarantee a runtime of O(N*Log(N)), even in the worst
case, but they are slower in the average case. Even though both algorithms have a runtime proportional to N*Log(N), quicksort has a
smaller constant factor – that is it requires C*N*Log(N) operations, while other algorithms require more like 2*C*N*Log(N) operations.

Another algorithm that uses random numbers finds the median of a group of numbers with an average runtime of O(N). This is a
significant improvement over sorting the numbers and taking the middle one, which takes O(N*Log(N)). Furthermore, while
deterministic (non­random) algorithms exist for finding the median with a runtime of O(N), the random algorithm is attractively simple,
and often faster than the deterministic algorithms.

The basic idea of the median algorithm is to pick one of the numbers in the group at random, and count how many of the numbers in
the group are less than it. Lets say there are N numbers, and K of them are less than or equal to the number we picked at random. If K
is less than half of N, then we know that the median is the (N/2­K) th number that is greater than the random number we picked, so
we discard the K numbers less than or equal to the random number. Now, we want to find the (N/2­K) th smallest number, instead of
the median. The algorithm is the same though, and we simply pick another number at random, and repeat the above steps.

Compression
Another class of algorithm deals with situations such as data compression. This type of algorithm does not have an expected output
(like a sorting algorithm), but instead tries to optimize some other criteria. In the case of data compression, the algorithm (LZW, for
instance) tries to make the data use as few bytes as possible, in such a way that it can be decompressed to its original form. In some
cases, this type of algorithm will use the same techniques as other algorithms, resulting in output that is good, but potentially sub­
optimal. JPG and MP3 compression, for example, both compress data in a way that makes the final result somewhat lower quality than
the original, but they create much smaller files. MP3 compression does not retain every feature of the original song file, but it attempts
to maintain enough of the details to capture most of the quality, while at the same time ensuring the significantly reduced file size that
we all know and love. The JPG image file format follows the same principle, but the details are significantly different since the goal is
image rather than audio compression.

The Importance of Knowing Algorithms
As a computer scientist, it is important to understand all of these types of algorithms so that one can use them properly. If you are
working on an important piece of software, you will likely need to be able to estimate how fast it is going to run. Such an estimate will
be less accurate without an understanding of runtime analysis. Furthermore, you need to understand the details of the algorithms
involved so that you’ll be able to predict if there are special cases in which the software won’t work quickly, or if it will produce
unacceptable results.

Of course, there are often times when you’ll run across a problem that has not been previously studied. In these cases, you have to
come up with a new algorithm, or apply an old algorithm in a new way. The more you know about algorithms in this case, the better
your chances are of finding a good way to solve the problem. In many cases, a new problem can be reduced to an old problem without
too much effort, but you will need to have a fundamental understanding of the old problem in order to do this.

As an example of this, lets consider what a switch does on the Internet. A switch has N cables plugged into it, and receives packets of
data coming in from the cables. The switch has to first analyze the packets, and then send them back out on the correct cables. A
switch, like a computer, is run by a clock with discrete steps – the packets are send out at discrete intervals, rather than continuously.
In a fast switch, we want to send out as many packets as possible during each interval so they don’t stack up and get dropped. The
goal of the algorithm we want to develop is to send out as many packets as possible during each interval, and also to send them out so
that the ones that arrived earlier get sent out earlier. In this case it turns out that an algorithm for a problem that is known as "stable
matching" is directly applicable to our problem, though at first glance this relationship seems unlikely. Only through pre­existing
algorithmic knowledge and understanding can such a relationship be discovered.

More Real­world Examples
Other examples of real­world problems with solutions requiring advanced algorithms abound. Almost everything that you do with a
computer relies in some way on an algorithm that someone has worked very hard to figure out. Even the simplest application on a
modern computer would not be possible without algorithms being utilized behind the scenes to manage memory and load data from the
hard drive.

There are dozens of applications of complicated algorithms, but I’m going to discuss two problems that require the same skills as some
past TopCoder problems. The first is known as the maximum flow problem, and the second is related to dynamic programming, a
technique that often solves seemingly impossible problems in blazing speed.

Maximum Flow
The maximum flow problem has to do with determining the best way to get some sort of stuff from one place to another, through a
network of some sort. In more concrete terms, the problem first arose in relation to the rail networks of the Soviet Union, during the
1950′s. The US wanted to know how quickly the Soviet Union could get supplies through its rail network to its satellite states in Eastern
Europe.
In addition, the US wanted to know which rails it could destroy most easily to cut off the satellite states from the rest of the Soviet
Union. It turned out that these two problems were closely related, and that solving the max flow problem also solves the min cut
problem of figuring out the cheapest way to cut off the Soviet Union from its satellites.

The first efficient algorithm for finding the maximum flow was conceived by two Computer Scientists, named Ford and Fulkerson. The
algorithm was subsequently named the Ford­Fulkerson algorithm, and is one of the more famous algorithms in computer science. In the
last 50 years, a number of improvements have been made to the Ford­Fulkerson algorithm to make it faster, some of which are
dauntingly complex.

Since the problem was first posed, many additional applications have been discovered. The algorithm has obvious relevance to the
Internet, where getting as much data as possible from one point to another is important. It also comes up in many business settings,
and is an important part of operations research. For example, if you have N employees and N jobs that need to be done, but not every
employee can do every job, the max flow algorithm will tell you how to assign your N employees to jobs in such a way that every job
gets done, provided that’s possible. Graduation, from SRM 200, is a good example of a TopCoder problem that lends itself to a solution
using max flow.

Sequence comparison
Many coders go their entire careers without ever having to implement an algorithm that uses dynamic programming. However, dynamic
programming pops up in a number of important algorithms. One algorithm that most programmers have probably used, even though
they may not have known it, finds differences between two sequences. More specifically, it calculates the minimum number of
insertions, deletions, and edits required to transform sequence A into sequence B.

For example, lets consider two sequences of letters, "AABAA" and "AAAB". To transform the first sequence into the second, the simplest
thing to do is delete the B in the middle, and change the final A into a B. This algorithm has many applications, including some DNA
problems and plagiarism detection. However, the form in which many programmers use it is when comparing two versions of the same
source code file. If the elements of the sequence are lines in the file, then this algorithm can tell a programmer which lines of code were
removed, which ones were inserted, and which ones were modified to get from one version to the next.

Without dynamic programming, we would have to consider a – you guessed it – exponential number of transformations to get from one
sequence to the other. As it is, however, dynamic programming makes for an algorithm with a runtime of only O(N*M), where N and M
are the numbers of elements in the two sequences.

Conclusion
The different algorithms that people study are as varied as the problems that they solve. However, chances are good that the problem
you are trying to solve is similar to another problem in some respects. By developing a good understanding of a large range of
algorithms, you will be able to choose the right one for a problem and apply it properly. Furthermore, solving problems like those found
in TopCoder’s competitions will help you to hone your skills in this respect. Many of the problems, though they may not seem realistic,
require the same set of algorithmic knowledge that comes up every day in the real world.

How to Dissect a Topcoder Problem Statement
By antimatter — topcoder member
Discuss this article in the forums

How many times has this happened to you: you register for the SRM, go into your assigned room when the system tells you to, and
when the match starts, you open the 250… and find it incomprehensible.

Maybe it’s never happened to you. You may be lucky, or you may already be extremely skilled. However, many experienced competitors
(yes, reds too) might end up just staring at a problem for a long time. This is a pretty serious issue. How can you solve the problem if
you have no idea what it’s asking you to do?

Fortunately, topcoder problem statements are formatted in a very specific way.

Knowing your way around the various pieces will go a long way towards helping you understand what the problem is saying.

The Parts of a Problem Statement
Let’s look at the composition of a typical topcoder problem statement. First off is the introduction. Usually, a problem will be led off with
a high­level description of a situation. This description may tie into real­life ideas and topics or it may just be a completely fictional
story, serving only as some sort of context. For many problems the back­story itself is not particularly important in understanding the
actual problem at hand.

Next comes the definition section. It gives you the skeleton of the solution you need to write: class name, method name, arguments,
and return type, followed by the complete method signature. At minimum, you will need to declare a class with the given name,
containing a method which conforms to the given method signature. The syntax given will always be correct for your chosen language.

Sometimes notes follow the method definition. They tend to be important reminders of things that you should pay attention to but
might have missed, or they can also be things that are helpful background knowledge that you might not know beforehand. If the notes
section appears, you should make sure to read it – usually the information contained within is extremely important.

The constraints section is arguably the most important. It lists specific constraints on the input variables. This lets you know crucial
details such as how much memory to allocate or how efficient your algorithm will have to be.

Finally, a set of examples is provided. These give sample inputs against which you can test your program. The given parameters will be
in the correct order, followed by the expected return value and, optionally, an explanation of the test case.

Introduction
The problem statement usually begins by motivating the problem. It gives a situation or context for the problem, before diving into
the gory details. This is usually irrelevant to solving the problem, so ignore it if necessary. In some cases, the motivation can
cause serious ambiguities if it is treated as binding – see MatchMaking (SRM 203 Div I Easy / Div II Medium). Also note that for
some simple problems, the initial context may be left out.

The ordering of the rest of this section varies greatly from problem to problem, based on the writing style of the problem author.
 There will be a description of what you need to do, in high­level terms. Take, for example, UserName (SRM 203, Div 2 easy). What
the problem is asking for you to do is to find the first variant of a given username that is not already taken. Note that the problem
has not yet said anything about variable names or types, or input formats.

There will also be a low­level description of the input. At the bare minimum, the types and variable names of the inputs will be
given to you, as well as what they correspond to and what they mean. Sometimes much more information about input formats will
be given; this typically occurs in more complicated problems.

Sometimes, even more detailed background information needs to be provided. That is also typically given here, or sometimes in
the Notes section.

The Definition
This is a very barebones description of what topcoder wants you to submit. It gives the class name, the method name to create
inside that class, the parameters it should take, the return value, and a method signature. As mentioned before, the basic form of
a submitted solution is to create a class containing a method with the required signature. Make sure that the class is declared
public if not using C++, and make sure to declare the method public also.

Notes and Constraints
Notes don’t always appear. If they do, READ THEM! Typically they will highlight issues that may have come up during testing, or
they may provide background information that you may not have known beforehand. The constraints section gives a list of
constraints on the input variables. These include constraints on sizes of strings and arrays, or allowed characters, or values of
numbers. These will be checked automatically, so there is no need to worry about writing code to check for these cases.

Be careful of the constraints. Sometimes they may rule out certain algorithms, or make it possible for simpler but less efficient
algorithms to run in time. There can be a very big difference between an input of 50 numbers and an input of 5, both in terms of
solutions that will end up passing, and in terms of ease of coding.

Examples
These are a list of sample test cases to test your program against. It gives the inputs (in the correct order) and then the expected
return value, and sometimes an annotation below, to explain the case further if necessary.

It goes without saying that you should test your code against all of the examples, at the very least. There may be tricky cases,
large cases, or corner cases that you have not considered when writing the solution; fixing issues before you submit is infinitely
preferable to having your solution challenged or having it fail during system testing.

The examples are not always comprehensive! Be aware of this. For some problems, passing the examples is almost the same as
passing every test case.

For others, however, they may intentionally (or not) leave out some test case that you should be aware of. If you are not
completely sure that your code is correct, test extensively, and try to come up with your own test cases as well. You may even be
able to use them in the challenge phase.

Solving a problem
Now we’ll walk through a simple problem and dissect it, bit by bit.

Have a look at BettingMoney, the SRM 191 Division 2 Easy. First we identify the parts of this problem. In the statement itself, we first
have the situation behind the problem – gambling. Then we have a little bit of background information about the betting itself. Then, we
have a description of the input – data types, variable names, and what they represent. After this we have the task: to determine what
the net gain is for the day and return the amount in cents.

Also note the two explanatory paragraphs at the end; the first provides an example of the input format and types, and the second gives
a completely worked example, which should be extremely helpful to your understanding.

The definition section is uninteresting, but it is there for completeness’ sake.

The notes for this problem are fairly comprehensive. In terms of background information, you might not know that there are 100 cents
in a dollar. And in terms of clarification, there is explicit confirmation that the return value may in fact be negative, and that the margin
of victory (the variable finalResult) is all that matters when deciding which payoff to make.

The constraints are fairly straightforward. The input arrays will contain the same number of elements, between 1 and 50, inclusive. (50
is a long­standing topcoder tradition for input sizes). finalResult will be between 0 and that same size minus one (which means, if you
give it a little thought, that someone will win their bet). Each element of each array will be between 0 and 5000, inclusive. This is most
likely to make sure that integer arithmetic will do the job just fine.

Finally, there’s the examples section. Often, the problem statement section will contain an annotated example case, which will become
example case 0. Then there are a couple of other example cases, some with explanation and some without. Also note that one of the
examples tests for negative return values, to supplement the notes.

A More Complicated Example
Now have a look at Poetry, the SRM 170 Div 2 Hard. In this case, you may not be able to actually solve this in the time allotted. That’s
ok – the emphasis should first be on understanding what the problem says, even if you can’t code it in time.

The first section tells you immediately what you want to do – you’ll be given a poem, and you will have to determine what its rhyme
scheme is. The rest of the section clarifies what this actually means, in bottom­up fashion (from simpler concepts to more complicated
ones). It defines what a legal word is and how to extract words from a poem, and then it defines what it means when two words rhyme
– that their ending patterns are equal. The concept of ending pattern is then defined. After all this, we find out what it means to have
two lines of the poem rhyme: their last words have to rhyme. Finally, (whew!) we are told how to actually construct the rhyme scheme
and in what format to return it.

This is a problem where a lot of terms need to be defined to get to the heart of things, and so all the definitions deserve at least a
couple of read­throughs, especially if you’re not sure how they all fit together.

The next section is the problem definition section, just for reference. Then there is a single note that clarifies a point that may have
been overlooked when it was stated in the problem statement itself: that blank lines will be labeled with a corresponding space in the
rhyme scheme.

The constraints are fairly standard for topcoder problems: there will be between 1 and 50 lines in the poem, and each line will contain
between 0 and 50 characters. The only allowable characters in the poem will be spaces and letters, and there will be only legal words in
poem.

Finally, there are a number of examples. Usually, problems which are trickier or which have more complex problem statements will have
more examples, to clarify at least some of the finer points of the problem statement. Again, this doesn’t mean that passing the example
cases given is equivalent to having a completely correct solution, but there is a higher chance that you can catch any bugs or trivial
mistakes if there are more examples that you know the answers to.

Try it Yourself
Listed below are a number of additional problems, grouped roughly by difficulty of comprehension. Try them for yourself in the topcoder
Arena Practice Rooms. Even if you can’t solve them, at least work on figuring out what the problem wants by breaking it down in this
manner.

Mentioned in this writeup:
SRM 203 Div 2 Easy – UserName
SRM 191 Div 2 Easy – BettingMoney
SRM 203 Div 1 Easy – MatchMaking
SRM 170 Div 2 Hard – Poetry

Similar tasks:
SRM 146 Div 2 Easy – Yahtzee
SRM 200 Div 2 Easy – NoOrderOfOperations
SRM 185 Div 2 Easy – PassingGrade
SRM 155 Div 2 Easy – Quipu
SRM 147 Div 2 Easy – CCipher
SRM 208 Div 1 Easy – TallPeople
SRM 173 Div 1 Easy – WordForm
SRM 162 Div 1 Easy – PaperFold

More challenging tasks:
SRM 197 Div 2 Hard – QuickSums
SRM 158 Div 1 Hard – Jumper
SRM 170 Div 1 Easy – RecurrenceRelation
SRM 177 Div 1 Easy – TickTick
SRM 169 Div 2 Hard – Twain
SRM 155 Div 1 Med – QuipuReader

How to Find a Solution
By Dumitru — topcoder member
Discuss this article in the forums

Introduction
Straight­forward problems that don’t require a special technique
Breadth First Search (BFS)
Flood Fill
Brute Force and Backtracking
Brute Force
Backtracking
Dynamic Programming
Hard Drills
Maximum Flow
Optimal Pair Matching
Linear Programming (Simplex)
Conclusion

Introduction

With many topcoder problems, the solutions may be found instantly just by reading their descriptions. This is possible thanks to a
collection of common traits that problems with similar solutions often have. These traits serve as excellent hints for experienced
problem solvers that are able to observe them. The main focus of this article is to teach the reader to be able to observe them too.

Straight­forward problems that don’t require any special technique (e.g. simulation, searching, sorting etc.)
In most cases, these problems will ask you to perform some step by step, straight­forward tasks. Their constraints are not high, and
not too low. In most cases the first problems (the easiest ones) in topcoder Single Rounds Matches are of this kind. They test mostly
how fast and properly you code, and not necessarily your algorithmic skills.

Most simple problems of this type are those that ask you just to execute all steps described in the statement.

BusinessTasks – SRM 236 Div 1:
N tasks are written down in the form of a circular list, so the first task is adjacent to the last one. A number n is also given. Starting
with the first task, move clockwise (from element 1 in the list to element 2 in the list and so on), counting from 1 to n. When your
count reaches n, remove that task from the list and start counting from the next available task. Repeat this procedure until one task
remains. Return it.

For N<=1000 this problem is just a matter of coding, no special algorithm is needed – do this operation step by step until one item is
left. Usually these types of problems have a much smaller N, and so we’ll not consider cases where N is very big and for which
complicated solution may be needed. Remember that in topcoder competitions even around 100 millions sets of simple operations (i.e.
some multiplications, attributions or if statements) will run in allowed time.

This category of problems also includes those that need some simple searches.

TallPeople – SRM 208 Div 1:
A group of people stands before you arranged in rows and columns. Looking from above, they form an R by C rectangle of people. Your
job is to return 2 specific heights – the first is computed by finding the shortest person in each row, and then finding the tallest person
among them (the "tallest­of­the­shortest"); and the second is computed by finding the tallest person in each column, and then finding
the shortest person among them (the "shortest­of­the­tallest").

As you see this is a really simple search problem. What you have to do is just to follow the steps described in the statement and find
those 2 needed heights. Other TC problems may ask you to sort a collection of items by respecting certain given rules. These problems
may be also included in this category, because they too are straight­forward – just sort the items respecting the rules! You can do that
with a simple O(N^2) sorting algorithm, or use standard sorting algorithm that exist in your coding language. It’s just a matter of
coding.

Other example(s):
MedalTable – SRM 209 Div 1.

Breadth First Search (BFS)
Problems that use BFS usually ask to find the fewest number of steps (or the shortest path) needed to reach a certain end point (state)
from the starting one. Besides this, certain ways of passing from one point to another are offered, all of them having the same cost of 1
(sometimes it may be equal to another number). Often there is given a N x M table (formed of N lines and M columns) where certain
cells are passable and others are impassable, and the target of the problem is to find the shortest time/path needed to reach the end
point from the start one. Such tables may represent mazes, maps, cities, and other similar things. These may be considered as classical
BFS problems. Because BFS complexity is in most cases linear (sometimes quadratic, or N logN), constraints of N (or M) could be high –
even up to 1 million.

SmartWordToy – SRM 233 Div 1:
A word composed of four Latin lowercase letters is given. With a single button click you can change any letter to the previous or next
letter in alphabetical order (for example ‘c’ can be changed to ‘b’ or ‘d’). The alphabet is circular, thus ‘a’ can become ‘z’, and ‘z’ can
become ‘a’ with one click.

A collection of constraints is also given, each defining a set of forbidden words. A constraint is composed of 4 strings of letters. A word
is forbidden if each of its characters is contained in corresponding string of a single constraint, i.e. first letter is contained in the first
string, the second letter – in the second string, and so on. For example, the constraint "lf a tc e" defines the words "late", "fate", "lace"
and "face".

You should find the minimum number of button presses required to reach the word finish from the word start without passing through
forbidden words, or return ­1 if this is not possible.

Problem hints:

Words can be considered as states. There are at most 26^4 different words composed of 4 letters (thus a linear complexity will
run in allowed time).
There are some ways to pass from one state to another.
The cost of passing from a state to another is always 1 (i.e. a single button click).
You need to find the minimum number of steps required to reach the end state from start state.

Everything indicates us that it’s a problem solved by the help of a BFS. Similar things can be found in any other BFS problems. Now
let’s see an interesting case of BFS problems.

CaptureThemAll – SRM 207 Div 2 (3rd problem):
Harry is playing a chess game. He has one knight, and his opponent Joe has a queen and a rook. Find the minimum number of steps
that Harry’s knight has to jump so that it captures both the queen and the rook.

Problem hints: At first sight this may seem like dynamic programming or backtracking. But as always, take a look into the text of the
statement. After a while you should observe the following things:

A table is given.
The knight can jump from one cell to some of its neighbors.
The cost of passing from a cell to another is always 1 (just one jump).
You need to find the minimum number of steps (jumps).

Given this information we can see that the problem can be easily solved by the help of BFS. Don’t get confused by the fact that
connected points are represented by unconnected cells. Think of cells as points in a graph, or states (whatever you want) – and in order
to pass from one point to another, the knight should be able to jump from the first to the second point.

Notice again that the most revealing hint about the BFS solution is the cost of 1 for any jump.

Train yourself in finding the hints of a BFS problem in following examples:

Other example(s):
RevolvingDoors – SRM 223 Div 1
WalkingHome – SRM 222 Div 1
TurntableService – SRM 219 Div 1

Flood Fill
Sometimes you may encounter problems that are solved by the help of Flood Fill, a technique that uses BFS to find all reachable points.
The thing that makes them different from BFS problems described above is that a minimum path/cost is not needed.

For example, imagine a maze where 1 represents impassable cells and 0 passable cells. You need to find all cells that are reachable
from the upper­left corner. The solution is very simple – take one­by­one a visited vertex, add its unvisited neighbors to the queue of
visited vertices and proceed with the next one while the queue is still populated. Note that in most cases a DFS (Depth First Search) will
not work for such problems due to stack overflows. Better use a BFS. For inexperienced users it may seem harder to implement, but
after a little training it becomes a "piece of cake". A good example of such problem would be:

grafixMask – SRM 211 Div 1:
A 400 x 600 bitmap is given. A set of rectangles covers certain parts of this bitmap (the corners of rectangles have integer
coordinates). You need to find all contiguous uncovered areas, including their sizes.

Problem hints: What do we have here?

A map (table)
 Certain points are impassable (those covered by given rectangles)
Contiguous areas need to be found

It is easy to understand that a problem with such a statement needs a Flood Fill. Usually problems using it are very easy to detect.

Brute Force and Backtracking
I have placed these 2 techniques in the same category because they are very similar. Both do the same thing – try all possible cases
(situations) and choose the best one, or count only those that are needed (depending on the problem). Practically, Backtracking is just
more advanced and optimized than Brute Force. It usually uses recursion and is applied to problems having low constraints (for
example N<=20).

Brute Force
There are many problems that can be solved by the help of a simple brute force. Note that the limits must not be high. How does a
brute force algorithm work? Actually, it tries all possible situations and selects the best one. It’s simple to construct and usually simple
to implement. If there is a problem that asks to enumerate or find all possible ways (situations) of doing a certain thing, and that
doesn’t have high limits – then it’s most probably a brute force problem.

GeneralChess – SRM 197 Div 1:
You are given some knights (at most 8), with their positions on the table (­10000<=x, y<=10000). You need to find all positions to
place another one, so that it threatens all given pieces.

Problem hints: Well, this is one of the easiest examples. So which are the hints of this statement?

You need to find all possible situations (positions) that satisfy a certain rule (threatens all given pieces).
The limits are very low – only 8 knights are at most given.

It’s a common Brute Force problem’s statement. Note that x and y limits are not relevant, because you need only try all positions that
threaten one of the knights. For each of these positions see if the knight placed at that position threatens all others too.

Another interesting problem would be:

LargestCircle – SRM 212 Div 2 (3rd problem):
Given a regular square grid, with some number of squares marked, find the largest circle you can draw on the grid that does not pass
through any of the marked squares. The circle must be centered on a grid point (the corner of a square) and the radius must be an
integer. Return the radius of the circle.

The size of the grid is at most 50.

Problem hints: And again one of the most important hints is the low limit of the size of the grid – only 50. This problem is possible to
be solved with the help of the Brute Force because for each cell you can try to find the circle whose center is situated in that cell and
that respects the rules. Among all of these circles found, select the one that has the greatest radius.

Complexity analysis: there are at most 50×50 cells, a circle’s radius is an integer and can be at most 25 units, and you need a linear
time (depending on your implementation) for searching the cells situated on the border of the circle. Total complexity is low and thus
you can apply a simple Brute Force here.

Other example(s):
Cafeteria – SRM 229 Div 1
WordFind – SRM 232 Div 1

Backtracking
This technique may be used in many types of problems. Just take a look at the limits (N, M and other main parameters). They serve as
the main hint of a backtrack problem. If these are very small and you haven’t found a solution that’s easier to implement – then just
don’t waste your time on searching it and implement a straight­forward backtracking solution.

Usually problems of this kind ask you to find (similarly to Brute Force):

1. Every possible configuration (subset) of items. These configurations should respect some given rules.
2. The "best" configuration (subset) that respects some given rules.

BridgeCrossing – SRM 146 Div 2 (3rd problem):
A group of people is crossing an old bridge. The bridge cannot hold more than two people at once. It is dark, so they can’t walk without
a flashlight, and they only have one flashlight! Furthermore, the time needed to cross the bridge varies among the people in the group.
When people walk together, they always walk at the speed of the slowest person. It is impossible to toss the flashlight across the
bridge, so one person always has to go back with the flashlight to the others. What is the minimum amount of time needed to get all
the people across the bridge?

There are at most 6 people.

Problem hints:

First look at the constraints – there are at most ONLY 6 people! It’s enough for generating all possible permutations, sets etc.
There are different possible ways to pass the people from one side to another and you need to find the best one.

This is of course a problem solved with a backtracking: at the beginning choose any 2 people to pass the bridge first, and after that at
each step try to pass any of those that have been left on the start side. From all these passages select the one that needs the smallest
amount of time. Note that among persons that have passed over the bridge, the one having the greatest speed should return (it’s
better than returning one having a lower speed). This fact makes the code much easier to implement. After having realized these things
– just code the solution. There may be others – but you will lose more time to find another than to code this one.

MNS – SRM 148 Div 1:
9 numbers need to be arranged in a magic number square. A magic number square is a square of numbers that is arranged such that
every row and column has the same sum. You are given 9 numbers that range from 0 to 9 inclusive. Return the number of distinct ways
that they can be arranged in a magic number square. Two magic number squares are distinct if they differ in value at one or more
positions.

Problem hints: Only 9 numbers are given at most; and every distinct way (configuration) to arrange the numbers so that they form a
magic number square should be found. These are the main properties of a Backtracking problem. If you have observed them – think
about the code. You can generate all permutations of numbers and for each of them check if it forms a magic square. If so – add it to
the answer. Note that it must be unique. A possible way to do that – is to have a list of earlier found configurations, thus for each new
magic square check if it exists in that list and if it doesn’t – add it to the answer. There will not be many distinct magic squares, thus no
additional problems will appear when applying this method.

Other example(s):
WeirdRooks – SRM 234 Div 1

Dynamic Programming
Quite a few problems are solved with the help of this technique. Knowing how to detect this type of problem can be very valuable.
However in order to do so, one has to have some experience in dynamic programming. Usually a DP problem has some main integer
variables (e.g. N) which are neither too small, nor too big – so that a usual DP complexity of N^2, N^3 etc. fits in time. Note that in the
event that N is very small (for TC problems usually less than 30) – then it is likely the problem is not a DP one. Besides that there
should exist states and one or more ways (rules) to reach one greater state from another lower one. In addition, greater states should
depend only upon lower states. What is a so­called state? It’s just a certain configuration or situation. To better understand dynamic
programming, you may want to read this article.

Let’s analyze a simple classic DP problem:

Given a list of N coins with their values (V1, V2, … ,VN), and the total sum S. Find the minimum number of coins the sum of which is S
(you can use as many coins of one type as you want), or report that it’s not possible to select coins in such a way that they sum up to
S.

Let N <= 1,000 and S <= 1,000.

Problem hints:

Two main integer variables are given (N and S). These are neither too small, nor are they too big (i.e. a complexity of N*S fits in
time).
A state can be defined as the minimum number of coins needed to reach a certain sum.
A sum (state) i depends only on lower sums (states) j (j<i).
By adding a coin to a certain sum – another greater sum is reached. This is the way to pass from one state to another.

Thus all properties of a DP problem are uncovered in this statement. Let’s see another (slightly harder) DP problem

ZigZag – 2003 TCCC Semifinals 3:
A sequence of numbers is called a zig­zag sequence if the differences between successive numbers strictly alternate between positive
and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially
a zig­zag sequence. Given a sequence of integers, return the length of the longest subsequence that is a zig­zag sequence. A
subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining
elements in their original order. Assume the sequence contains between 1 and 50 elements, inclusive.

Problem hints:

There are N numbers given (1<=N<=50), thus N isn’t too small, nor too big.
A state (i,d) can be defined as the length of the longest zig­zag subsequence ending with the i­th number, for which the number
before the last one is smaller than it for d=0, and bigger for d=1.
A state i (i.e. a subsequence ending with the i­th number) depends only on lower states j (j<i).
By adding a number to the end of a subsequence – another bigger (greater) subsequence is created. This is the way to pass from
one state to another.

As you can see – this statement has almost the same traits (pattern) as in the previous problem. The most difficult part in identifying a
DP problem statement is observing/seeing the states with the properties described above. Once you can do that, the next step is to
construct the algorithm, which is out of the scope of this article.

Other example(s):
ChessMetric – 2003 TCCC Round 4
AvoidRoads – 2003 TCO Semifinals 4
FlowerGarden – 2004 TCCC Round 1
BadNeighbors – 2004 TCCC Round 4

Hard Drills:
Maximum Flow
In many cases it’s hard to detect a problem whose solution uses maximum flow. Often you have to create/define graphs with capacities
based on the problem statement.

Here are some signs of a Maximum Flow problem:

Take a look at the constraints, they have to be appropriate for a O(N^3) or O(N^4) solution, i.e. N shouldn’t be greater than 500
in extreme cases (usually it’s less than 100).
There should be a graph with edges having capacities given, or you should be able to define/create it from data given in the
statement.
You should be finding a maximum value of something.

Sample problem:

You are given a list of water pipes, each having a certain maximum water flow capacity. There are water pipes connected together at
their extremities.

You have to find the maximum amount of water that can flow from start junction to end junction in a unit of time.

Let N<=100.

As you can see – it’s a straight­forward maximum flow problem: water pipes represent edges of the graph, their junctions – vertices;
and you have to find the maximum value of amount of water that can flow from start to end vertex in a unit of time.

Optimal Pair Matching:
These problems usually have a list of items (from a set A) for which other items (from a set B) should be assigned under some rules, so
that all (or a maximum possible number of) items from set A have to each be assigned to a certain item from set B.
Mixed:
Some problems need other techniques in addition to network flows.

Parking – SRM 236 Div 1:
N cars and M parking lots are given. They are situated on a rectangular surface (represented by a table), where certain cells are
impassable. You should find a way to assign each car to a parking lot, so that the greatest of the shortest distances from each car to its
assigned parking lot is as small as possible. Each parking lot can have at most one car assigned to it.

Problem hints: By reading this problem one can simply understand the main idea of the solution – it should be something similar to
optimal pair matching, because each car (point from a set A) should be assigned to a parking lot (point from a set B) so that all are
assigned and that there is at most one car assigned to a parking lot. Additionally, there can be cars that can’t reach certain parking lots,
thus some pairs of points (one point from A and the other from B) are not connected. However a graph should be created for optimal
pair matching. The way to make it is clear – an edge exists between a car and a parking lot if only there is a path between them, and
its cost is equal to the shortest distance needed for the car to reach the parking lot. The next step of the solution is a binary search on
the longest edge. Although it may be out of the scope of this article, I will provide a short explanation: At each step delete those edges
of the initial graph that have costs greater than a certain value C (Note that you’ll have to save the initial graph’s state in order to
repeat this step again for other C values). If it’s possible in this case to assign all the cars to parking lots – then take a smaller C, and
repeat the same operation. If not – take a greater C. After a complete binary search, the smallest C for which a complete assignment is
possible will be found. This will be the answer.

Linear Programming (Simplex)
Most of the common traits of problems solved with the help of the linear programming technique are:

You are given collection of items having different costs/weights. There is a certain quantity of each item that must be achieved.
A list of sets is given. These sets are composed of some of the available items, having certain quantities of each of them. Each set
has a certain cost.
The goal of the problem is to find an optimal combination (the cheapest one) of these sets so that the sum of quantities of each of
the items they have is exactly the one needed to achieve.

At first it may seem confusing, but let’s see an example:

Mixture – SRM 231 Div 1):
A precise mixture of a number of different chemicals, each having a certain amount, is needed. Some mixtures of chemicals may be
purchased at a certain price (the chemical components for the mixture might not be available in pure form). Each of them contains
certain amounts of some of the chemicals. You need not purchase the available mixtures in integral amounts. Hence if you purchase a
1.5 of a mixture having a price of 3 and amounts of "2 0 1", you’ll pay 4.5 and get "3 0 1.5" amounts of chemicals. Your task is to
determine the lowest price that the desired mixture can be achieved.

Problem hints:

A collection of items (chemicals).
A list of sets (available mixtures), each containing certain amounts of each of the items, and having a certain cost.
You need to find the lowest price of the desired collection of items achieved by the combination of the available sets. More than
that – you can take also non­integral amounts of mixtures.

These are exactly the traits described above.

Conclusion
If you have found this article interesting and you have learned new things from it – train yourself on any of the problems in the
topcoder Algorithm Arena. Try hard to see the hints and determine the type of the solution by carefully reading through the problem
statement. Remember, there are still many problems that may not be included properly in any of the categories described above and
may need a different approach.

Planning an Approach to a Topcoder Problem: Part 1
By leadhyena_inran — topcoder member 
Discuss this article in the forums

Planning an approach is a finicky art; it can stump the most seasoned coders as much as it stumps the newer ones, and it can be
extremely hard to put into words. It can involve many calculations and backtracks, as well as foresight, intuition, creativity, and even
dumb luck, and when these factors don’t work in concert it can inject a feeling of helplessness in any coder. Sometimes it’s this feeling
of helplessness that discourages coders from even attempting the Div I Hard. There are even coders that stop competing because they
abhor that mental enfeeblement that comes with some problems. However, if one stays diligent, the solution is never really out of the
mind’s reach. This tutorial will attempt to flesh out the concepts that will enable you to pick an approach to attack the problems with a
solid plan.

Pattern Mining and the Wrong Mindset
It is easy to fall into the trap of looking at the algorithm competition as a collection of diverse yet classifiable story problems. For those
that have done a lot of story problems, you know that there are a limited number of forms of problems (especially in classes where the
professor tends to be repetitious), and when you read a problem in a certain form, your mind says, "Oh, this is an X problem, so I find
the numbers that fit the problem and plug and chug." There are many times when this kind of pattern mining pays off; after a number
of topcoder Single Round Matches, most coders will recognize a set of common themes and practice against them, and this method of
problem attack can be successful for many matches.

However, this approach is perilous. There are times when you skim the problem statement and assume it’s of type Q, then start coding
and discover that your code passes none of the examples. That’s when you reread the problem and find out that this problem is unique
to your experience. At that point, you are paralyzed by your practice; being unable to fit any of your problem types to the problem you
are unable to proceed. You’ll see this often when there’s a really original problem that comes down the pipe, and a lot of seasoned
coders fail the problem because they are blinded by their experience.

Pattern mining encourages this kind of mindset that all of the problem concepts have been exhausted, when in reality this is impossible.
Only by unlearning what you have learned (to quote a certain wise old green midget) and by relearning the techniques of critical
thought needed to plan an approach can your rating sustainably rise.
Coding Kata
Here’s your first exercise: take any problem in the Practice Rooms that you haven’t done. Fight through it, no matter how long it takes,
and figure it out (use the editorial from the competition as a last resort). Get it to pass system tests, and then note how long you took
to solve it. Next, clear your solution out, and try to type it in again (obviously cutting and pasting will ruin the effect). Again, get it to
pass system tests. Note how long it took you to finish the second time. Then, clear it out and do the problem a third time, and again
get it to pass system tests. Record this final time.

The time it takes for your first pass is how long it takes you when you have no expectations of the problem and no approach readily in
mind. Your time on the second pass is usually the first time minus the amount of time it took you to understand the problem statement.
(Don’t be surprised at the number of bugs you’ll repeat in the second pass.) That final recorded time is your potential, for you can solve
it this fast in competition if you see the correct approach immediately after reading it. Let that number encourage you; it really is
possible to solve some of these problems this quickly, even without super fast typing ability. But what you should also learn from the
third pass is the feeling that you knew a working strategy, how the code would look, where you would tend to make the mistakes, and
so on. That’s what it feels like to have the right approach, and that feeling is your goal for future problems in competition.

In most martial arts, there’s a practice called kata where the martial artist performs a scripted series of maneuvers in order, usually
pretending to defend (or sometimes actually defending) against an onslaught of fighters, also scripted to come at the artist predictably.
At first this type of practice didn’t make any sense, because it didn’t seem realistic to the chaotic nature of battle. Furthermore it seems
to encourage the type of pattern mining mentioned in the previous section. Only after triple­coding many problems for a while can one
comprehend the true benefit of this coding kata. The kata demonstrates to its practitioners the mental experience of having a plan,
encouraging the type of discipline it takes to sit and think the problem through. This plan of attack is your approach, and it carries you
through your coding, debugging, and submission.

Approach Tactics
Now that you know what an approach feels like and what its contents are, you’ll realize that you know a lot of different types of these
approaches. Do you give them names? "Oh, I used DP (dynamic programming) on that problem." "Really, I could have done that one
greedy?" "Don’t tell me that the brute­force solution would have passed in time." Really, the name you give an approach to a problem is
a misnomer, because you can’t classify every problem as a type like just greedy or just brute­force. There are an infinite number of
problem types, even more solution types, and even within each solution type there are an infinite number of different variations. This
name is only a very high level summary of the actual steps it takes to get to the solution.

In some of the better match editorials there is a detailed description of one approach to solving the code. The next time you look at a
match summary, and there is a good write­up of a problem, look for the actual steps and formation of the approach. You start to notice
that there is a granularity in the steps, which suggests a method of cogitation. These grains of insight are approach tactics, or ways to
formulate your approach, transform it, redirect it, and solidify it into code that get you closer to the solution or at least point you away
from the wrong solution. When planning your approach, the idea is that you will use whatever approach tactics are at your disposal to
decide on your approach, the idea being that you are almost prewriting the code in your head before you proceed. It’s almost as if you
are convincing yourself that the code you are about to write will work.

Coders with a math background may recognize this method of thinking, because many of these approach tactics are similar to proof
writing techniques. Chess players may identify it with the use of tactics to look many moves ahead of the current one. Application
designers may already be acquainted with this method when working with design patterns. In many other problem solving domains
there is a similar parallel to this kind of taxonomy.

To practice this type of critical thinking and to decide your preferences among approach tactics, it is very useful to record the solutions
to your problems, and to write up a post­SRM analysis of your own performance. Detail in words how each of your solutions work so
that others could understand and reproduce the approach if they wanted to just from your explanations. Not only will writing up your
approaches help you to understand your own thoughts while coding, but this kind of practice also allows you to critique your own
pitfalls and work on them in a constructive manner. Remember, it is difficult to improve that which you don’t understand.

Breaking Down a Problem
Let’s talk about one of the most common approach tactics: breaking down a problem. This is sometimes called top­down programming:
the idea is that your code must execute a series of steps in order, and from simple decisions decide if other steps are necessary, so
start by planning out what your main function needs before you think about how you’ll do the subfunctions. This allows you to
prototype the right functions on the fly (because you only code for what you need and no further), and also it takes your problem and
fragments it into smaller, more doable parts.

A good example of where this approach is useful is in MatArith from Round 2 of the 2002 topcoder Invitational. The problem requires
you to evaluate an expression involving matrices. You know that in order to get to the numbers you’ll need to parse them (because
they’re in String arrays) and pass those values into an evaluator, change it back into a String array and then you’re done. So you’ll need
a print function, a parse function and a new calc function. Without thinking too hard, if you imaging having all three of these functions
written already the problem could be solved in one line:

    public String[] calculate(String[] A, String[] B, String[] C, String eval){ 
return print(calc(parse(A),parse(B),parse(C),eval)); 
    } 

The beauty of this simplest approach tactic is the guidance of your thoughts into a functional hierarchy. You have now fragmented your
work into three steps: making a parse function, a print function, and then a calc function, breaking a tough piece of code into smaller
pieces. If you break down the code fine enough, you won’t have to think hard about the simplest steps, because they’ll become atomic
(more on this below). In fact the rest of this particular problem will fall apart quickly by successive partitioning into functions that
multiply and add the matrices, and one more that reads the eval statement correctly and applies the appropriate functions.

This tactic really works well against recursive problems. The entire idea behind recursive code is that you are breaking the problem into
smaller pieces that look exactly like the original, and since you’re writing the original, you’re almost done. This approach tactic also
plays into the hands of a method of thinking about programs called functional programming. There are several articles on the net and
even a topcoder article written by radeye that talk more about this concept in depth, but the concept is that if properly fragmented, the
code will pass all variable information between functions, and no data needs to be stored between steps, which prevents the possibility
of side­effects (unintended changes to state variables between steps in code) that are harder to debug.

Plan to Debug
Whenever you use an approach you should always have a plan to debug the code that your approach will create. This is the dark
underbelly of every approach tactic. There is always a way that a solution may fail, and by thinking ahead to the many ways it can
break, you can prevent the bugs in the code before you type them. Furthermore, if you don’t pass examples, you know where to start
looking for problems. Finally, by looking for the stress points in the code’s foundation, it becomes easier to prove to yourself that the
approach is a good one.
In the case of a top­down approach, breaking a problem down allows you to isolate sections of the code where there may be problems,
and it will allow you to group tests that break your code into sections based on the subfunction they seem to exploit the most. There is
also an advantage to breaking your code into functions when you fix a bug, because that bug is fixed in every spot where the code is
used. The alternative to this is when a coder copy/pastes sections of code into every place it is needed, making it harder to propagate a
fix and makes the fix more error prone. Also, when you look for bugs in a top­down approach, you should look for bugs inside the
functions before you look between the calls to each function. These parts make up a debugging strategy: where to look first, how to
test what you think is wrong, how to validate pieces and move on. Only after sufficient practice will a debugging strategy become more
intuitive to your method of attack.

Atomic Code
If you arrive at a section of code that you cannot break down further this is atomic code. Hopefully you know how to code each of these
sections, and these form the most common forms of atomic code. But, don’t be discouraged when you hit a kernel of the problem that
you don’t know how to code; these hard­to­solve kernels are in fact what make the problem interesting, and sometimes being able to
see these in advance can make the big difference between solving the problem early with the right approach and heading down the
wrong path with the wrong approach, wasting a lot of time in the process.

The most common type of atomic code you’ll write is in the form of primitives. I’ve always been a proponent of knowing the library of
your language of choice. This is where that knowledge is of utmost importance. What better way to save yourself time is there in both
planning your approach and coding your solution when you know that a possibly difficult section of your code is in fact atomic and
solved using a library function or class?

The second type of atomic code you’ll write are what I call language techniques. These are usually snippets of code committed to
memory that perform a certain operation in the language, like locating the index of the first element in an array with the minimum
value, or parsing a String into tokens separated by whitespace. These techniques are equally essential to planning an approach,
because if you know how to do these fundamental operations intuitively, it makes more tasks in your search for a top­down approach
atomic, thus making the search for the right approach shorter. In addition, it makes the segments of the code in these atomic segments
less error prone. Furthermore, if you are asked to perform a task similar to one that you already know a language technique for, it
makes it much easier to mutate the code to fit the situation (for example: searching for the index of the first maximal element in an
array based on some heuristic is easy if you already know how to type up similar tasks). Looking for these common language
techniques should become an element of your daily practice, and any atomic code should fly off your fingers as soon as you think about
it.

As an aside, I must address the use of code libraries. I know that this is a contested topic, and many successful coders out there make
use of a (sometimes encyclopedic) library as a pre­inserted segment of code before they start coding. This is totally legal (although
changes to the rules after the 2004 topcoder Open may affect their future legality), and there are obvious advantages to using a library,
mainly through the ability to declare more parts of your top­down approach atomic, and by being able to more quickly construct
bottom­up fragments of code (as discussed below). It is my opinion, however, that the disadvantages of using library code outweigh the
advantages. On a small note, library code executed through functions can sometimes slow your coding, because you have to make the
input match the prototype of the code you’re trying to use. Library code is mostly non­mutatable, so if your library is asked to do
something that isn’t expressly defined, you find yourself fumbling over a language technique or algorithm that should already be
internalized. It is also possible that your library code isn’t bug­free, and debugging your library mid­competition is dangerous because
you may have to propagate that change to code you’ve already submitted and also to the template before you open any more
problems. Also, library use is not allowed in onsite competition. Finally, the use of library code (or macros for that manner) get you
used to leaning on your library instead of your instincts of the language, making the use of normal primitives less intuitive and the
understanding of other coder’s solutions during challenge phase not as thorough. If used in moderation your library can be powerful,
but it is not the ultimate weapon for all terrain.

There may be a point where you hit a piece of atomic code that you are unable to fragment. This is when you have to pull out the
thinking cap and start analyzing your current approach. Should I have broken up the tasks differently? Should I store my intermediate
values differently? Or maybe this is the key to the problem that makes the problem hard? All of these things must be considered before
you pound the keys. Even at these points where you realize that you’re stuck, there are ways to manipulate the problem at hand to
come to an insight on how to proceed quickly, and these ways comprise the remaining approach tactics.

Planning an Approach to a Topcoder Problem: Part 2
By leadhyena_inran — topcoder member
Discuss this article in the forums

Bottom Up Programming
This technique is the antithesis to breaking down a program, and should be the first thing you start doing when you get stuck. Bottom­
up programming is the process of building up primitive functions into more functional code until the solution becomes as trivial as one
of the primitives. Sometimes you know that you’ll need certain functions to form a solution and if these functions are atomic or easy to
break down, you can start with these functions and build your solution upward instead of breaking it down.

In the case of MatArith, the procedure to add and multiply matrices was given in the problem statement making it easy to follow
directions and get two functions to start with. From there you could make a smaller evalMult function that multiplied matrices together
using a string evaluation and variable names, then a similar evalAdd that treats each term as a block and you have an approach to
solve the problem.

In general, it’s a very good strategy to code up any detailed procedure in the problem statement before tackling the actual problem.
Examples of these are randomizer functions, any data structures you’re asked to simulate, and any operations on mathematical objects
like matrices and complex numbers. You’ll find that by solving these smaller issues and then rereading the problem statement that you
will understand what needs to be done much better. And sometimes, if you’re really stuck, it doesn’t hurt to write a couple atomic
pieces of code that you know that you’ll need in order to convince your mind to break down the problem towards those functions. As
you can see, your path to the right approach need not be linear as long as it follows your train of thought.

Also, in case of a hidden bug, keep in mind that any code that you write using this approach tactic should be scanned for bugs before
your top­down code, because you tend to write this code first and thus at a stage where you understand the problem less than when
you finish the code. This is a good rule of thumb to follow when looking for errors in your code; they usually sit in the older sections of
the code, even if older is only decided by minutes or even seconds.

Brute Force
Any time the solution requires looking for an optimal configuration or a maximal number or any other choice of one of a finite set of
objects, the simplest way to solve the problem is to try all configurations. Any time the solution requires calculating a massive
calculation requiring many steps, the best way to solve it is to do every calculation as asked for in the problem. Any time the problem
asks you to count the number of ways something can be done, the best way to solve it is to try every way and make a tally. In other
words, the first approach to consider in any possibly time­intensive problem is the most obvious one, even if it is horribly inefficient.

This approach tactic, called brute force, is so called because there is no discerning thought about the method of calculation of the return
value. Any time you run into this kind of an optimization problem the first thing you should do is try to figure in your head the worst
possible test cases and if 8 seconds is enough time to solve each one. If so, brute force can be a very speedy and usually less error
prone approach. In order to utilize brute force, you have to know enough about the programming environment to calculate an estimate
how much time any calculation will take. But an estimate is just a guess, and any guess could be wrong. This is where your wisdom is
forced to kick in and make a judgment call. And this particular judgment call has bitten many a coder that didn’t think it could be done
brute force and couldn’t debug a fancier approach, and likewise those that didn’t figure correctly the worst of the cases to be tested for
time.

In general, if you can’t think of a way to solve the problem otherwise, plan to use brute force. If it ends up that you are wrong, and
there is a test case that takes too long, keep the brute force solution around, and while recoding the more elegant solution, use the
brute­force solution to verify that your elegant code is correct in the smaller cases, knowing that its more direct approach is a good
verification of these cases (being much less error­prone code).

A Place for Algorithms
Well­known and efficient algorithms exist for many standard problems, much like basic approaches exist for many standard word
problems in math, just like standard responses exist for most common opening moves in chess. While in general it’s a bad idea to lean
heavily upon your knowledge of the standard algorithms (it leads down the path of pattern mining and leaves you vulnerable to more
original problems), it’s a very good idea to know the ones that come up often, especially if you can apply them to either an atomic
section of code or to allow them to break your problem down.

This is not the place to discuss algorithms (there are big books to read and other tutorials in this series to follow that will show you the
important stuff), but rather to discuss how algorithms should be used in determining an approach. It is not sufficient to know how to
use an algorithm in the default sense; always strive to know any algorithms you have memorized inside and out. For example, you may
run into a problem like CityLink (SRM 170 Div I Med), which uses a careful mutation of a basic graph algorithm to solve in time,
whereby just coding the regular algorithm would not suffice. True understanding of how the algorithm works allows the insight needed
to be able to even conceive of the right mutation.

So, when you study algorithms, you need to understand how the code works, how long it will take to run, what parts of the code can be
changed and what effect any changes will have on the algorithm. It’s also extremely important that you know how to code the
algorithm by memory before you try to use it in an approach, because without the experience of implementing an algorithm, it becomes
very hard to tell whether your bugs are being caused by a faulty implementation or faulty input into the implementation. It’s also good
to practice different ways to use the algorithms creatively to solve different problems, to see what works and what doesn’t. Better for
an experiment with code to fall flat on its face in practice than during a competition. This is why broad­based algorithmic techniques
(like divide­and­conquer, dynamic programming, greedy algorithms) are better to study first before you study your more focused
algorithms because the concepts are easier to manipulate and easier to implement once you understand the procedure involved.

Manipulating the Domain
This situation will become more and more familiar: you find yourself trudging through the planning stages of a problem because of the
sheer amount of work involved in simulating the domain of the problem. This may be due to the inappropriateness of the presented
domain, and there are times when manipulating the domain of the problem to something more convenient will create an easier or more
recognizable problem. The classic example of this is the game of Fifteen (used as a problem in SRM 172). In the game of Fifteen, you
have numbers from 1 to 9 of which you may claim one per turn, and if exactly three of your numbers add to 15 before exactly three of
your opponent’s numbers adds to 15, then you win. For this problem, you can manipulate the domain by placing the numbers in the
configuration of a 3×3 magic square (where every row, column, and diagonal add up to the same sum, in this case 15). Instantly you
realize that the game of Fifteen is just the game Tic­Tac­Toe in disguise, making the game easier to play and program a solution for,
because the manipulation of the domain transformed the situation of a game where you have no prior knowledge into one where you
have a lot more knowledge. Some mathematicians think of this as the ABA­1 approach, because the algebra suggests the proper
process: first you transform the domain, then you perform your action, then (the A­1) you reverse your transformation. This approach is
very common in solving complex problems like diagonalizing matrices and solving the Rubik’s Cube.

Most commonly this approach tactic is used to simplify basic calculations. A good example of this type of approach is
HexagonIntersections from SRM 206. In this problem it was needed to find the number of tiled hexagons that touched a given line. The
problem became much easier if you "slanted" the grid by transforming the numbers involved so that the hexagons involved had sides
parallel to the x and y axis and the problem still had the same answer, thereby simplifying calculations.

Extreme care must be taken while debugging if you manipulate the domain. Remember that the correct procedure to domain
manipulation is to first manipulate the domain, then solve the problem, and then correct the domain. When you test the code,
remember that either the domain must be properly reversed by the transformation before the result is returned, or the reversal must
not affect the answer. Also, when looking at values inside the domain manipulation, remember that these are transformed values and
not the real ones. It’s good to leave comment lines around your transformed section of code just to remind yourself of this fact.

Unwinding the Definitions
This approach tactic is an old mathematician’s trick, relating to the incessant stacking of definitions upon definitions, and can be used to
unravel a rather gnarly problem statement to get at the inner intended approach to the problem. The best way to do this is with code.
When you read the definition of something you have never encountered before, try to think how you would code it. If the code asks you
to find the simplest grozmojt in a set of integers, first figure out how your code would verify that something was a grozmojt and then
figure out how to search for it, regardless if you even need to verify that something was a grozmojt in the solution. This is very similar
to the bottom­up programming above, but taken at the definition level instead of the procedural one.

Simulation problems fall under similar tactics, and create one of those times when those predisposed to object oriented coding styles
run up the scores. The best way to manage a simulation problem is to create a simulation object that can have actions performed on it
from a main function. That way you don’t worry if you passed enough state into a given function or not; since all of the information in
the simulation is coming along with you, the approach becomes very convenient and reaches atomic code very quickly. This is also the
correct approach to take if an algorithm needs to be simulated to count the steps needed in the algorithm (like MergeSort) or the
number of objects deallocated in the execution of another algorithm (like ImmutableTrees). In these situations, the elegance of the
code is usually sacrificed in the name of correctness and thoroughness, also making the approach easier to plan ahead for.

The Problem is Doable
An old geometry puzzle goes like this: you have a pair of concentric circles and the only length you are given is the length of a chord of
the outer circle (call the chord length x) that is tangent to the inner circle, and you are asked for the area between the circles. You
respond: "Well, if the problem is doable then the inner circle’s radius is irrelevant to the calculation, so I’ll declare it to be 0. Because
the area of the inner circle is 0, or degenerates to the center of the outer circle, the chord of the outer circle passes through the center
and is thus the diameter, and thus the area of the outer circle is Pi(x/2)2." Note that a proper geometric proof of this fact is harder to
do; the sheer fact that a solution exists actually makes the problem easier. Since the writer had to write a solution for the problem, you
know it’s always solvable, and this fact can be used to your advantage in an SRM.

This approach tactic broadens into the concept that the writer is looking for a particular type of solution, and sometimes through edits
of the original problem statement this approach is given away (especially if the original problem is considered too hard for the level it’s
at). Look for lowered constraints like arrays of size 20 (which many a seasoned coder will tell you is almost a codeword that the writer
is looking for a brute force solution), or integers limited to between 1 and 10000 (allowing safe multiplication in ints without overflow).
By leaning on the constraints you are acting similarly to the situation above, by not allowing the complexities of the problem that were
trimmed off by the constraints to complicate your approach.

Sometimes the level of the problem alone will give a hint to what solution is intended. For example, look at FanFailure (from SRM 195
Div I Easy). The problem used the language of subsets and maximal and minimal, so you start to think maybe attack with brute force,
and then you see the constraints opened up to 50 for the array size. 250 distinct subsets rules out brute force (better to find this out in
the approach than in the code, right?) and you could look to fancier algorithms… but then you realize that this is a Div I Easy and
probably isn’t as hard as it looks so you think through the greedy algorithm and decide that it probably works. This choice wouldn’t
have been so obvious had it not been a Div I Easy.

Keep in mind that these invisible cues are not objective and can’t be used to reason why an approach will work or not; they are there
only to suggest what the writer’s mind was thinking. Furthermore, if the writer is evil or particularly tricky, cues of this nature may be
red herrings to throw these tactics astray. As long as you temper this approach tactic with solid analysis before you go on a wild goose
chase, this "circular reasoning" can be used to great advantage.

Case Reduction
Sometimes the simplest problems to state are the ones that provide the most difficulty. With these types of problems it’s not unusual
that the solution requires that you break up the problem not into steps but into cases. By breaking a problem up into cases of different
sets of inputs you can create subproblems that can be much easier to solve. Consider the problem TeamPhoto (SRM 167 Div I Medium).
This problem is simple to state, but abhorrent to solve. If you break up the problem into a series of cases, you find that where the
entire problem couldn’t alone be solved by a greedy algorithm, each of the different cases could be, and you could take the best case
from those optimal configurations to solve the problem.

The most common use of case reduction involves removing the boundary cases so that they don’t mess up a naive solution. A good
example of this is BirthdayOdds (SRM 174 Div I Easy); many people hard coded if(daysInYear==1)return 2; to avoid the possible
problems with the boundary case, even if their solution would have handled it correctly without that statement. By adding that level of
security, it became easier to verify that the approach they chose was correct.

Plans Within Plans
As illustrated above, an approach isn’t easily stated, and is usually glossed over if reduced to a one­word label. Furthermore, there are
many times when there exist levels to a problem, each of which needs to be solved before the full solution comes to light. One clear
example of this is the problem MagicianTour (SRM 191 Div I Hard). There are definitely two delineated steps to this problem: the first
step requires a graph search to find all connected components and their 2­coloring, and the second step requires the DP knapsack
algorithm. In cases like this, it’s very helpful to remember that sometimes more than one approach tactic needs to be applied to the
situation to get at the solution. Another great example is TopographicalImage (SRM 209 Div I Hard) which asks for the lowest angle
that places a calculated value based on shortest path under a certain limit. To solve, note that looking for this lowest value can be
approached by binary search, but there are plans within plans, and the inner plan is to apply Floyd­Warshall’s All Pairs Shortest Paths
algorithm to decide if the angle is satisfactory.

Remember also that an approach isn’t just "Oh, I know how to break this down… Let’s go!" The idea of planning your approach is to
strategically think about: the steps in your code, how an algorithm is to be applied, how the values are to be stored and passed, how
the solution will react to the worst case, where the most probable nesting places are for bugs. The idea is that if the solution is carefully
planned, there is a lower chance of losing it to a challenge or during system tests. For each approach there are steps that contain plans
for their steps.

Tactical Permutation
There is never a right approach for all coders, and there are usually at least two ways to do a problem. Let’s look at an unsavory
Division One Easy called OhamaLow (SRM 206 Div I Easy). One of the more popular ways to approach this problem is to try all
combinations of hands, see if the hand combination is legal, sort the hand combination, and compare it to the best hand so far. This is a
common brute­force search strategy. But it’s not the entire approach. Remember that there are plans within plans. You have to choose
an approach on how to form each hand (this could be done recursively or using multiple for­loops), how to store the hands (int arrays,
Strings, or even a new class), and how to compare them. There are many different ways to do each of these steps, and most of the
ways to proceed with the approach will work. As seen above as well as here, there are many times where more than one approach will
do the job, and these approaches are considered permutable. In fact, one way to permute the top­level brute­force search strategy is
to instead of considering all possible constructible hands and picking the best one, you can construct all possible final hands in best to
worst order and stop when you have found one that’s constructible. In other words you take all 5 character substrings of "87654321" in
order and see if the shared hand and player hand can make the chosen hand, and if so return that hand. This approach also requires
substeps (how to decide if the hand can be formed, how to walk the possible hands, and so on) but sometimes (and in this case it is
better) you can break it down faster.

The only way you get to choose between two approaches is if you are able to come up with both of them. A very good way to practice
looking for multiple approaches to problems is to try to solve as many of the problems in the previous SRM using two different
approaches. By doing this, you stretch your mind into looking for these different solutions, increasing your chances of finding the more
elegant solution, or the faster one to type, or even the one that looks easier to debug.

Backtracking from a Flawed Approach
As demonstrated in the previous section, it is very possible for there to exist more than one way to plan an approach to a problem. It
may even hit you in the middle of coding your approach how to more elegantly solve the problem. One of the hardest disciplines to
develop while competing in topcoder Single Round Matches is the facility to stick to the approach you’ve chosen until you can prove
without a shadow of a doubt that you made a mistake in the approach and the solution will not work. Remember that you are not
awarded points for code elegance, or for cleverness, or for optimized code. You are granted points solely on the ability to quickly post
correct code. If you come up with a more elegant solution than the one you’re in the middle of typing up, you have to make the split
second analysis of how much time you’ll lose for changing your current approach, and in most cases it isn’t worth it.

There is no easy answer to planning the right approach the first time. If you code up a solution and you know it is right but has bugs
this is much easier to repair than the sudden realization that you just went the entirely wrong direction. If you get caught in this
situation, whatever you do, don’t erase your code! Relabel your main function and any subfunctions or data structures that may be
affected by further changes. The reason is because while you may desire a clean slate, you must accept that some of your previous
routines may be the same, and retracing your steps by retyping the same code can be counterproductive to your thinking anew.
Furthermore, by keeping the old code you can test against it later looking for cases that will successfully challenge other coders using
the same flawed approach.

Conclusion
Planning an approach is not a science, although there is a lot of rigor in the thought involved. Rather, it is mainly educated guesswork
coupled with successful planning. By being creative, economical, and thorough about your thought process you can become more
successful and confident in your solutions and the time you spend thinking the problem through will save you time later in the coding
and debugging. This ability to plan your code before the fingers hit the keys only develops through lots of practice, but this diligence is
rewarded with an increasing ability to solve problems and eventually a sustained rating increase.

Mentioned in this writeup:
TCI ’02 Round 2 Div I Med – MatArith
SRM 170 Div I Med – CityLink
SRM 172 Div I Med – Fifteen
SRM 206 Div I Hard – HexagonIntersections
SRM 195 Div I Easy – FanFailure
SRM 167 Div I Med – TeamPhoto
SRM 174 Div I Easy – BirthdayOdds
SRM 191 Div I Hard – MagicianTour
SRM 210 Div II Hard – TopographicalImage
SRM 206 Div I Easy – OmahaLow

Mathematics for Topcoders
By dimkadimon — topcoder member 
Discuss this article in the forums

Introduction
I have seen a number of competitors complain that they are unfairly disadvantaged because many topcoder problems are too
mathematical. Personally, I love mathematics and thus I am biased in this issue. Nevertheless, I strongly believe that problems should
contain at least some math, because mathematics and computer science often go hand in hand. It is hard to imagine a world where
these two fields could exist without any interaction with each other. These days, a great deal of applied mathematics is performed on
computers such as solving large systems of equations and approximating solutions to differential equations for which no closed formula
exists. Mathematics is widely used in computer science research, as well as being heavily applied to graph algorithms and areas of
computer vision.

This article discusses the theory and practical application to some of the more common mathematical constructs. The topics covered
are: primes, GCD, basic geometry, bases, fractions and complex numbers.

Primes
A number is prime if it is only divisible by 1 and itself. So for example 2, 3, 5, 79, 311 and 1931 are all prime, while 21 is not prime
because it is divisible by 3 and 7. To find if a number n is prime we could simply check if it divides any numbers below it. We can use
the modulus (%) operator to check for divisibility:

    for (int i=2; i<n; i++) 
if (n%i==0) return false; 

    return true; 

We can make this code run faster by noticing that we only need to check divisibility for values of i that are less or equal to the square
root of n (call this m). If n divides a number that is greater than m then the result of that division will be some number less than m and
thus n will also divide a number less or equal to m. Another optimization is to realize that there are no even primes greater than 2.
Once we’ve checked that n is not even we can safely increment the value of i by 2. We can now write the final method for checking
whether a number is prime:

    public boolean isPrime (int n){ 
if (n<=1) return false; 
if (n==2) return true; 
if (n%2==0) return false; 
int m=Math.sqrt(n); 

for (int i=3; i<=m; i+=2) 
if (n%i==0) 
return false; 

return true; 
    } 

Now suppose we wanted to find all the primes from 1 to 100000, then we would have to call the above method 100000 times. This
would be very inefficient since we would be repeating the same calculations over and over again. In this situation it is best to use a
method known as the Sieve of Eratosthenes. The Sieve of Eratosthenes will generate all the primes from 2 to a given number n. It
begins by assuming that all numbers are prime. It then takes the first prime number and removes all of its multiples. It then applies
the same method to the next prime number. This is continued until all numbers have been processed. For example, consider finding
primes in the range 2 to 20. We begin by writing all the numbers down:

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

2 is the first prime. We now cross out all of its multiples, ie every second number:

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
The next non­crossed out number is 3 and thus it is the second prime. We now cross out all the multiples of 3, ie every third number
from 3:

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

All the remaining numbers are prime and we can safely terminate the algorithm. Below is the code for the sieve:

    public boolean[] sieve(int n){ 
boolean[] prime=new boolean[n+1]; 
Arrays.fill(prime,true); 
prime[0]=false; 
prime[1]=false; 
int m=Math.sqrt(n); 

for (int i=2; i<=m; i++) 
if (prime[i]) 
for (int k=i*i; k<=n; k+=i) 
prime[k]=false; 

return prime; 
    } 

In the above method, we create a boolean array prime which stores the primality of each number less of equal than n. If prime[i] is
true then number i is prime. The outer loop finds the next prime while the inner loop removes all the multiples of the current prime.

GCD
The greatest common divisor (GCD) of two numbers a and b is the greatest number that divides evenly into both a and b. Naively we
could start from the smallest of the two numbers and work our way downwards until we find a number that divides into both of them:

    for (int i=Math.min(a,b); i>=1; i‐‐) 
if (a%i==0 && b%i==0) 
return i; 

Although this method is fast enough for most applications, there is a faster method called Euclid’s algorithm. Euclid’s algorithm iterates
over the two numbers until a remainder of 0 is found. For example, suppose we want to find the GCD of 2336 and 1314. We begin by
expressing the larger number (2336) in terms of the smaller number (1314) plus a remainder:

    2336 = 1314 x 1 + 1022

We now do the same with 1314 and 1022:

    1314 = 1022 x 1 + 292

We continue this process until we reach a remainder of 0:

    1022 = 292 x 3 + 146 
    292 = 146 x 2 + 0 

The last non­zero remainder is the GCD. So the GCD of 2336 and 1314 is 146. This algorithm can be easily coded as a recursive
function:

    //assume that a and b cannot both be 0 
    public int GCD(int a, int b){ 
if (b==0) return a; 
return GCD(b,a%b); 
    } 

Using this algorithm we can find the lowest common multiple (LCM) of two numbers. For example the LCM of 6 and 9 is 18 since 18 is
the smallest number that divides both 6 and 9. Here is the code for the LCM method:

    public int LCM(int a, int b){ 
return b*a/GCD(a,b); 
    } 

As a final note, Euclid’s algorithm can be used to solve linear Diophantine equations. These equations have integer coefficients and are
of the form:

    ax + by = c 

Geometry

Occasionally problems ask us to find the intersection of rectangles. There are a number of ways to represent a rectangle. For the
standard Cartesian plane, a common method is to store the coordinates of the bottom­left and top­right corners.

Suppose we have two rectangles R1 and R2. Let (x1, y1) be the location of the bottom­left corner of R1 and (x2, y2) be the location of
its top­right corner. Similarly, let (x3, y3) and (x4, y4) be the respective corner locations for R2. The intersection of R1 and R2 will be a
rectangle R3 whose bottom­left corner is at (max(x1, x3), max(y1, y3)) and top­right corner at (min(x2, x4), min(y2, y4)). If max(x1,
x3) > min(x2, x4) or max(y1, y3) > min(y2, y4) then R3 does not exist, ie R1 and R2 do not intersect. This method can be extended to
intersection in more than 2 dimensions as seen in CuboidJoin (SRM 191, Div 2 Hard).

Often we have to deal with polygons whose vertices have integer coordinates. Such polygons are called lattice polygons. In his tutorial
on Geometry Concepts, lbackstrom presents a neat way for finding the area of a lattice polygon given its vertices. Now, suppose we do
not know the exact position of the vertices and instead we are given two values:

    B = number of lattice points on the boundary of the polygon

    I = number of lattice points in the interior of the polygon 

Amazingly, the area of this polygon is then given by:
    Area = B/2 + I ‐ 1

The above formula is called Pick’s Theorem due to Georg Alexander Pick (1859 – 1943). In order to show that Pick’s theorem holds for
all lattice polygons we have to prove it in 4 separate parts. In the first part we show that the theorem holds for any lattice rectangle
(with sides parallel to axis). Since a right­angled triangle is simply half of a rectangle it is not too difficult to show that the theorem also
holds for any right­angled triangle (with sides parallel to axis). The next step is to consider a general triangle, which can be represented
as a rectangle with some right­angled triangles cut out from its corners. Finally, we can show that if the theorem holds for any two
lattice polygons sharing a common side then it will also hold for the lattice polygon, formed by removing the common side. Combining
the previous result with the fact that every simple polygon is a union of triangles gives us the final version of Pick’s Theorem. Pick’s
theorem is useful when we need to find the number of lattice points inside a large polygon.

Another formula worth remembering is Euler’s Formula for polygonal nets. A polygonal net is a simple polygon divided into smaller
polygons. The smaller polygons are called faces, the sides of the faces are called edges and the vertices of the faces are called vertices.
Euler’s Formula then states:

    V ‐ E + F = 2, where 

    V = number of vertices 
    E = number of edges 
    F = number of faces 

For example, consider a square with both diagonals drawn. We have V = 5, E = 8 and F = 5 (the outside of the square is also a face)
and so V – E + F = 2.

We can use induction to show that Euler’s formula works. We must begin the induction with V = 2, since every vertex has to be on at
least one edge. If V = 2 then there is only one type of polygonal net possible. It has two vertices connected by E number of edges. This
polygonal net has E faces (E – 1 "in the middle" and 1 "outside"). So V – E + F = 2 – E + E = 2. We now assume that V – E + F = 2 is
true for all 2<=V<=n. Let V = n + 1. Choose any vertex w at random. Now suppose w is joined to the rest of the net by G edges. If we
remove w and all these edges, we have a net with n vertices, E – G edges and F – G + 1 faces. From our assumption, we have:

(n) ‐ (E ‐ G) + (F ‐ G + 1) = 2
thus (n+1) ‐ E + F = 2

Since V = n + 1, we have V – E + F = 2. Hence by the principal of mathematical induction we have proven Euler’s formula.

Bases
A very common problem faced by topcoder competitors during challenges involves converting to and from binary and decimal
representations (amongst others).

So what does the base of the number actually mean? We will begin by working in the standard (decimal) base. Consider the decimal
number 4325. 4325 stands for 5 + 2 x 10 + 3 x 10 x 10 + 4 x 10 x 10 x 10. Notice that the "value" of each consequent digit increases
by a factor of 10 as we go from right to left. Binary numbers work in a similar way. They are composed solely from 0 and 1 and the
"value" of each digit increases by a factor of 2 as we go from right to left. For example, 1011 in binary stands for 1 + 1 x 2 + 0 x 2 x 2
+ 1 x 2 x 2 x 2 = 1 + 2 + 8 = 11 in decimal. We have just converted a binary number to a decimal. The same applies to other bases.
Here is code which converts a number n in base b (2<=b<=10) to a decimal number:

    public int toDecimal(int n, int b){ 
int result=0; 
int multiplier=1; 

while(n>0){
result+=n%10*multiplier; 
multiplier*=b; 
n/=10; 
} 

return result; 
    } 

Java users will be happy to know that the above can be also written as:

    return Integer.parseInt(""+n,b);

To convert from a decimal to a binary is just as easy. Suppose we wanted to convert 43 in decimal to binary. At each step of the method
we divide 43 by 2 and memorize the remainder. The final list of remainders is the required binary representation:

    43/2 = 21 + remainder 1 
    21/2 = 10 + remainder 1 
    10/2 = 5  + remainder 0 
    5/2  = 2  + remainder 1 
    2/2  = 1  + remainder 0 
    1/2  = 0  + remainder 1 

So 43 in decimal is 101011 in binary. By swapping all occurrences of 10 with b in our previous method we create a function which
converts from a decimal number n to a number in base b (2<=b<=10):

    public int fromDecimal(int n, int b){ 
int result=0; 
int multiplier=1; 

while(n>0){
result+=n%b*multiplier; 
multiplier*=10; 
n/=b; 
}  
return result; 
    } 
If the base b is above 10 then we must use non­numeric characters to represent digits that have a value of 10 and more. We can let ‘A’
stand for 10, ‘B’ stand for 11 and so on. The following code will convert from a decimal to any base (up to base 20):

    public String fromDecimal2(int n, int b){ 
String chars="0123456789ABCDEFGHIJ"; 
String result=""; 

while(n>0){
result=chars.charAt(n%b) + result; 
n/=b; 
} 
return result; 
    } 

In Java there are some useful shortcuts when converting from decimal to other common representations, such as binary (base 2), octal
(base 8) and hexadecimal (base 16):

    Integer.toBinaryString(n); 
    Integer.toOctalString(n); 
    Integer.toHexString(n); 

Fractions and Complex Numbers
Fractional numbers can be seen in many problems. Perhaps the most difficult aspect of dealing with fractions is finding the right way of
representing them. Although it is possible to create a fractions class containing the required attributes and methods, for most purposes
it is sufficient to represent fractions as 2­element arrays (pairs). The idea is that we store the numerator in the first element and the
denominator in the second element. We will begin with multiplication of two fractions a and b:

    public int[] multiplyFractions(int[] a, int[] b){ 
int[] c={a[0]*b[0], a[1]*b[1]}; 
return c; 
    } 

Adding fractions is slightly more complicated, since only fractions with the same denominator can be added together. First of all we
must find the common denominator of the two fractions and then use multiplication to transform the fractions such that they both have
the common denominator as their denominator. The common denominator is a number which can divide both denominators and is
simply the LCM (defined earlier) of the two denominators. For example lets add 4/9 and 1/6. LCM of 9 and 6 is 18. Thus to transform
the first fraction we need to multiply it by 2/2 and multiply the second one by 3/3:

    4/9 + 1/6 = (4*2)/(9 * 2) + (1 * 3)/(6 * 3) =  8/18 +  3/18 

Once both fractions have the same denominator, we simply add the numerators to get the final answer of 11/18. Subtraction is very
similar, except we subtract at the last step:

    4/9 ‐ 1/6 =  8/18 ‐  3/18 =  5/18

Here is the code to add two fractions:

    public int[] addFractions(int[] a, int[] b){ 
int denom=LCM(a[1],b[1]); 
int[] c={denom/a[1]*a[0] + denom/b[1]*b[0], denom}; 
return c; 
    } 

Finally it is useful to know how to reduce a fraction to its simplest form. The simplest form of a fraction occurs when the GCD of the
numerator and denominator is equal to 1. We do this like so:

    public void reduceFraction(int[] a){ 
int b=GCD(a[0],a[1]); 
a[0]/=b; 
a[1]/=b; 
    } 

Using a similar approach we can represent other special numbers, such as complex numbers. In general, a complex number is a
number of the form a + ib, where a and b are reals and i is the square root of ­1. For example, to add two complex numbers m = a +
ib and n = c + id we simply group likewise terms:

    m + n 
    = (a + ib) + (c + id) 
    = (a + c) + i(b + d) 

Multiplying two complex numbers is the same as multiplying two real numbers, except we must use the fact that i^2 = ­1:

    m * n 
    = (a + ib) * (c + id) 
    = ac + iad + ibc + (i^2)bd 
    = (ac ‐ bd) + i(ad + bc) 

By storing the real part in the first element and the complex part in the second element of the 2­element array we can write code that
performs the above multiplication:

    public int[] multiplyComplex(int[] m, int[] n){ 
int[] prod = {m[0]*n[0] ‐ m[1]*n[1], m[0]*n[1] + m[1]*n[0]}; 
return prod; 
    } 

Conclusion
In conclusion I want to add that one cannot rise to the top of the topcoder rankings without understanding the mathematical constructs
and algorithms outlined in this article. Perhaps one of the most common topics in mathematical problems is the topic of primes. This is
closely followed by the topic of bases, probably because computers operate in binary and thus one needs to know how to convert from
binary to decimal. The concepts of GCD and LCM are common in both pure mathematics as well as geometrical problems. Finally, I have
included the last topic not so much for its usefulness in topcoder competitions, but more because it demonstrates a means of treating
certain numbers.

Geometry Concepts: Basic Concepts
By lbackstrom — topcoder member
Discuss this article in the forums

Introduction
Vectors
Vector Addition
Dot Product
Cross Product
Line­Point Distance
Polygon Area

Introduction
Many topcoders seem to be mortally afraid of geometry problems. I think it’s safe to say that the majority of them would be in favor of
a ban on topcoder geometry problems. However, geometry is a very important part of most graphics programs, especially computer
games, and geometry problems are here to stay. In this article, I’ll try to take a bit of the edge off of them, and introduce some
concepts that should make geometry problems a little less frightening.

Vectors
Vectors are the basis of a lot of methods for solving geometry problems. Formally, a vector is defined by a direction and a magnitude.
In the case of two­dimension geometry, a vector can be represented as pair of numbers, x and y, which gives both a direction and a
magnitude. For example, the line segment from (1,3) to (5,1) can be represented by the vector (4,­2). It’s important to understand,
however, that the vector defines only the direction and magnitude of the segment in this case, and does not define the starting or
ending locations of the vector.

Vector Addition
There are a number of mathematical operations that can be performed on vectors. The simplest of these is addition: you can add two
vectors together and the result is a new vector. If you have two vectors (x1, y1) and (x2, y2), then the sum of the two vectors is
simply (x1+x2, y1+y2). The image below shows the sum of four vectors. Note that it doesn’t matter which order you add them up in –
just like regular addition. Throughout these articles, we will use plus and minus signs to denote vector addition and subtraction, where
each is simply the piecewise addition or subtraction of the components of the vector.

Dot Product
The addition of vectors is relatively intuitive; a couple of less obvious vector operations are dot and cross products. The dot product of
two vectors is simply the sum of the products of the corresponding elements. For example, the dot product of (x1, y1) and (x2, y2) is
x1*x2 + y1*y2. Note that this is not a vector, but is simply a single number (called a scalar). The reason this is useful is that the dot
product, A ? B = |A||B|Cos(?), where ? is the angle between the A and B. |A| is called the norm of the vector, and in a 2­D geometry
problem is simply the length of the vector, sqrt(x2+y2). Therefore, we can calculate Cos(?) = (A ? B)/(|A||B|). By using the acos
function, we can then find ?. It is useful to recall that Cos(90) = 0 and Cos(0) = 1, as this tells you that a dot product of 0 indicates two
perpendicular lines, and that the dot product is greatest when the lines are parallel. A final note about dot products is that they are not
limited to 2­D geometry. We can take dot products of vectors with any number of elements, and the above equality still holds.

Cross Product
An even more useful operation is the cross product. The cross product of two 2­D vectors is x1*y2 ‐ y1*x2 Technically, the cross product
is actually a vector, and has the magnitude given above, and is directed in the +z direction. Since we’re only working with 2­D
geometry for now, we’ll ignore this fact, and use it like a scalar. Similar to the dot product, A x B = |A||B|Sin(?). However, ? has a
slightly different meaning in this case: |?| is the angle between the two vectors, but ? is negative or positive based on the right­hand
rule. In 2­D geometry this means that if A is less than 180 degrees clockwise from B, the value is positive. Another useful fact related
to the cross product is that the absolute value of |A||B|Sin(?) is equal to the area of the parallelogram with two of its sides formed by
A and B. Furthermore, the triangle formed by A, B and the red line in the diagram has half of the area of the parallelogram, so we can
calculate its area from the cross product also.
Line­Point Distance
Finding the distance from a point to a line is something that comes up often in geometry problems. Lets say that you are given 3
points, A, B, and C, and you want to find the distance from the point C to the line defined by A and B (recall that a line extends
infinitely in either direction). The first step is to find the two vectors from A to B (AB) and from A to C (AC). Now, take the cross product
AB x AC, and divide by |AB|. This gives you the distance (denoted by the red line) as (AB x AC)/|AB|. The reason this works comes from
some basic high school level geometry. The area of a triangle is found as base*height/2. Now, the area of the triangle formed by A, B
and C is given by (AB x AC)/2. The base of the triangle is formed by AB, and the height of the triangle is the distance from the line to
C. Therefore, what we have done is to find twice the area of the triangle using the cross product, and then divided by the length of the
base. As always with cross products, the value may be negative, in which case the distance is the absolute value.

Things get a little bit trickier if we want to find the distance from a line segment to a point. In this case, the nearest point might be one
of the endpoints of the segment, rather than the closest point on the line. In the diagram above, for example, the closest point to C on
the line defined by A and B is not on the segment AB, so the point closest to C is B. While there are a few different ways to check for
this special case, one way is to apply the dot product. First, check to see if the nearest point on the line AB is beyond B (as in the
example above) by taking AB ? BC. If this value is greater than 0, it means that the angle between AB and BC is between ­90 and 90,
exclusive, and therefore the nearest point on the segment AB will be B. Similarly, if BA ? AC is greater than 0, the nearest point is A. If
both dot products are negative, then the nearest point to C is somewhere along the segment. (There is another way to do this, which
I’ll discuss here).

    //Compute the dot product AB ? BC 
    int dot(int[] A, int[] B, int[] C){ 
AB = new int[2]; 
BC = new int[2]; 
AB[0] = B[0]‐A[0]; 
AB[1] = B[1]‐A[1]; 
BC[0] = C[0]‐B[0]; 
BC[1] = C[1]‐B[1]; 
int dot = AB[0] * BC[0] + AB[1] * BC[1]; 
return dot; 
    } 
    //Compute the cross product AB x AC 
    int cross(int[] A, int[] B, int[] C){ 
AB = new int[2]; 
AC = new int[2]; 
AB[0] = B[0]‐A[0]; 
AB[1] = B[1]‐A[1]; 
AC[0] = C[0]‐A[0]; 
AC[1] = C[1]‐A[1]; 
int cross = AB[0] * AC[1] ‐ AB[1] * AC[0]; 
return cross; 
    } 
    //Compute the distance from A to B 
    double distance(int[] A, int[] B){ 
int d1 = A[0] ‐ B[0]; 
int d2 = A[1] ‐ B[1]; 
return sqrt(d1*d1+d2*d2); 
    } 
    //Compute the distance from AB to C 
    //if isSegment is true, AB is a segment, not a line. 
    double linePointDist(int[] A, int[] B, int[] C, boolean isSegment){ 
double dist = cross(A,B,C) / distance(A,B); 
if(isSegment){ 
int dot1 = dot(A,B,C); 
if(dot1 > 0)return distance(B,C); 
int dot2 = dot(B,A,C); 
if(dot2 > 0)return distance(A,C); 
} 
return abs(dist); 
    } 

That probably seems like a lot of code, but lets see the same thing with a point class and some operator overloading in C++ or C#. The
* operator is the dot product, while ^ is cross product, while + and – do what you would expect.

//Compute the distance from AB to C
    //if isSegment is true, AB is a segment, not a line. 
    double linePointDist(point A, point B, point C, bool isSegment){ 
double dist = ((B‐A)^(C‐A)) / sqrt((B‐A)*(B‐A)); 
if(isSegment){ 
 int dot1 = (C‐B)*(B‐A); 
if(dot1 > 0)return sqrt((B‐C)*(B‐C)); 
int dot2 = (C‐A)*(A‐B); 
if(dot2 > 0)return sqrt((A‐C)*(A‐C)); 
} 
return abs(dist); 
    } 

Operator overloading is beyond the scope of this article, but I suggest that you look up how to do it if you are a C# or C++ coder, and
write your own 2­D point class with some handy operator overloading. It will make a lot of geometry problems a lot simpler.

Polygon Area
Another common task is to find the area of a polygon, given the points around its perimeter. Consider the non­convex polygon below,
with 5 points. To find its area we are going to start by triangulating it. That is, we are going to divide it up into a number of triangles. In
this polygon, the triangles are ABC, ACD, and ADE. But wait, you protest, not all of those triangles are part of the polygon! We are
going to take advantage of the signed area given by the cross product, which will make everything work out nicely. First, we’ll take the
cross product of AB x AC to find the area of ABC. This will give us a negative value, because of the way in which A, B and C are
oriented. However, we’re still going to add this to our sum, as a negative number. Similarly, we will take the cross product AC x AD to
find the area of triangle ACD, and we will again get a negative number. Finally, we will take the cross product AD x AE and since these
three points are oriented in the opposite direction, we will get a positive number. Adding these three numbers (two negatives and a
positive) we will end up with a negative number, so will take the absolute value, and that will be area of the polygon.

The reason this works is that the positive and negative number cancel each other out by exactly the right amount. The area of ABC and
ACD ended up contributing positively to the final area, while the area of ADE contributed negatively. Looking at the original polygon, it
is obvious that the area of the polygon is the area of ABCD (which is the same as ABC + ABD) minus the area of ADE. One final note, if
the total area we end up with is negative, it means that the points in the polygon were given to us in clockwise order. Now, just to
make this a little more concrete, lets write a little bit of code to find the area of a polygon, given the coordinates as a 2­D array, p.

    int area = 0; 
    int N = lengthof(p); 

    //We will triangulate the polygon 
    //into triangles with points p[0],p[i],p[i+1] 

    for(int i = 1; i+1<N; i++){ 
int x1 = p[i][0] ‐ p[0][0]; 
int y1 = p[i][1] ‐ p[0][1]; 
int x2 = p[i+1][0] ‐ p[0][0]; 
int y2 = p[i+1][1] ‐ p[0][1]; 
int cross = x1*y2 ‐ x2*y1; 
area += cross; 
    } 
    return abs(cross/2.0); 

Notice that if the coordinates are all integers, then the final area of the polygon is one half of an integer.

Geometry Concepts: Line Intersection and its Applications
By lbackstrom — topcoder member

Line­Line Intersection
Finding a Circle From 3 Points
Reflection
Rotation
Convex Hull

In the previous section we saw how to use vectors to solve geometry problems. Now we are going to learn how to use some basic linear
algebra to do line intersection, and then apply line intersection to a couple of other problems. 

Line­Line Intersection
One of the most common tasks you will find in geometry problems is line intersection. Despite the fact that it is so common, a lot of
coders still have trouble with it. The first question is, what form are we given our lines in, and what form would we like them in? Ideally,
each of our lines will be in the form Ax+By=C, where A, B and C are the numbers which define the line. However, we are rarely given
lines in this format, but we can easily generate such an equation from two points. Say we are given two different points, (x1, y1) and
(x2, y2), and want to find A, B and C for the equation above. We can do so by setting 
    A = y2‐y1
    B = x1‐x2
    C = A*x1+B*y1
Regardless of how the lines are specified, you should be able to generate two different points along the line, and then generate A, B and
C. Now, lets say that you have lines, given by the equations:
    A1x + B1y = C1
    A2x + B2y = C2 
 
To find the point at which the two lines intersect, we simply need to solve the two equations for the two unknowns, x and y.

    double det = A1*B2 ‐ A2*B1 
if(det == 0){ 
//Lines are parallel 
}else{ 
double x = (B2*C1 ‐ B1*C2)/det 
double y = (A1*C2 ‐ A2*C1)/det 
} 

To see where this comes from, consider multiplying the top equation by B2, and the bottom equation by B1. This gives you
    A1B2x + B1B2y = B2C1
    A2B1x + B1B2y = B1C2
Now, subtract the bottom equation from the top equation to get
    A1B2x ‐ A2B1x = B2C1 ‐ B1C2
Finally, divide both sides by A1B2 ‐ A2B1, and you get the equation for x. The equation for y can be derived similarly.

This gives you the location of the intersection of two lines, but what if you have line segments, not lines. In this case, you need to make
sure that the point you found is on both of the line segments. If your line segment goes from (x1,y1) to (x2,y2), then to check if (x,y)
is on that segment, you just need to check that min(x1,x2) = x = max(x1,x2), and do the same thing for y. You must be careful about
double precision issues though. If your point is right on the edge of the segment, or if the segment is horizontal or vertical, a simple
comparison might be problematic. In these cases, you can either do your comparisons with some tolerance, or else use a fraction class.

Finding a Circle From 3 Points
Given 3 points which are not colinear (all on the same line) those three points uniquely define a circle. But, how do you find the center
and radius of that circle? This task turns out to be a simple application of line intersection. We want to find the perpendicular bisectors
of XY and YZ, and then find the intersection of those two bisectors. This gives us the center of the circle.

To find the perpendicular bisector of XY, find the line from X to Y, in the form Ax+By=C. A line perpendicular to this line will be given by
the equation ‐Bx+Ay=D, for some D. To find D for the particular line we are interested in, find the midpoint between X and Y by taking
the midpoint of the x and y components independently. Then, substitute those values into the equation to find D. If we do the same
thing for Y and Z, we end up with two equations for two lines, and we can find their intersections as described above.

Reflection
Reflecting a point across a line requires the same techniques as finding a circle from 3 points. First, notice that the distance from X to
the line of reflection is the same as the distance from X’ to the line of reflection. Also note that the line between X and X’ is
perpendicular to the line of reflection. Now, if the line of reflection is given as Ax+By=C, then we already know how to find a line
perpendicular to it: ‐Bx+Ay=D. To find D, we simply plug in the coordinates for X. Now, we can find the intersection of the two lines at Y,
and then find X' = Y ‐ (X ‐ Y).

Rotation
Rotation doesn’t really fit in with line intersection, but I felt that it would be good to group it with reflection. In fact, another way to find
the reflected point is to rotate the original point 180 degrees about Y.

Imagine that we want to rotate one point around another, counterclockwise by ϴ degrees. For simplicity, lets assume that we are
rotating about the origin. In this case, we can find that x' = x Cos(ϴ) ‐ y Sin(ϴ) and y' = x Sin(ϴ) + y Cos(ϴ). If we are rotating
about a point other than the origin, we can account for this by shifting our coordinate system so that the origin is at the point of
rotation, doing the rotation with the above formulas, and then shifting the coordinate system back to where it started.

Convex Hull
A convex hull of a set of points is the smallest convex polygon that contains every one of the points. It is defined by a subset of all the
points in the original set. One way to think about a convex hull is to imagine that each of the points is a peg sticking up out of a board.
Take a rubber band and stretch it around all of the points. The polygon formed by the rubber band is a convex hull. There are many
different algorithms that can be used to find the convex hull of a set of points. In this article, I’m just going to describe one of them,
which is fast enough for most purposes, but is quite slow compared to some of the other algorithms.
First, loop through all of your points and find the leftmost point. If there is a tie, pick the highest point. You know for certain that this
point will be on the convex hull, so we’ll start with it. From here, we are going to move clockwise around the edge of the hull, picking
the points on the hull, one at a time. Eventually, we will get back to the start point. In order to find the next point around the hull, we
will make use of cross products. First, we will pick an unused point, and set the next point, N, to that point. Next, we will iterate
through each unused points, X, and if (X‐P) x (N‐P) (where P is the previous point) is negative, we will set N to X. After we have
iterated through each point, we will end up with the next point on the convex hull. See the diagram below for an illustration of how the
algorithm works. We start with P as the leftmost point. Now, say that we have N and X as shown in the leftmost frame. In this case the
cross product will be negative, so we will set N = X, and there will be no other unused points that make the cross product negative, and
hence we will advance, setting P = N. Now, in the next frame, we will end up setting N = X again, since the cross product here will be
negative. However, we aren’t done yet because there is still another point that will make the cross product negative, as shown in the
final frame.

The basic idea here is that we are using the cross product to find the point which is furthest counterclockwise from our current position
at P. While this may seem fairly straightforward, it becomes a little bit tricky when dealing with colinear points. If you have no colinear
points on the hull, then the code is very straightforward.

    convexHull(point[] X){ 
int N = lengthof(X); 
int p = 0;
//First find the leftmost point 
for(int i = 1; i<N; i++){ 
if(X[i] < X[p]) 
p = i; 
} 
int start = p; 
do{ 
int n = ‐1; 
for(int i = 0; i<N; i++){ 

//Don't go back to the same point you came from 
if(i == p)continue; 

//If there is no N yet, set it to i 
if(n == ‐1)n = i; 
int cross = (X[i] ‐ X[p]) x (X[n] ‐ X[p]); 

if(cross < 0){ 
//As described above, set N=X 
n = i; 
} 
} 
p = n;
}while(start!=p); 
    } 

Once we start to deal with colinear points, things get trickier. Right away we have to change our method signature to take a boolean
specifying whether to include all of the colinear points, or only the necessary ones.

    //If onEdge is true, use as many points as possible for 
    //the convex hull, otherwise as few as possible. 
    convexHull(point[] X, boolean onEdge){ 
int N = lengthof(X); 
int p = 0;
boolean[] used = new boolean[N]; 
//First find the leftmost point 
for(int i = 1; i<N; i++){ 
if(X[i] < X[p]) 
p = i; 
} 
int start = p; 
do{ 
int n = ‐1; 
int dist = onEdge?INF:0; 
for(int i = 0; i<N; i++){ 
//X[i] is the X in the discussion 

//Don't go back to the same point you came from 
if(i==p)continue; 

//Don't go to a visited point 
if(used[i])continue; 

//If there is no N yet, set it to X 
if(n == ‐1)n = i; 
int cross = (X[i] ‐ X[p]) x (X[n] ‐ X[p]); 

//d is the distance from P to X 
 int d = (X[i] ‐ X[p]) ? (X[i] ‐ X[p]); 
if(cross < 0){ 
//As described above, set N=X 
n = i; 
dist = d; 
}else if(cross == 0){ 
//In this case, both N and X are in the 
//same direction.  If onEdge is true, pick the 
//closest one, otherwise pick the farthest one. 
if(onEdge && d < dist){ 
dist = d; 
n = i; 
}else if(!onEdge && d > dist){ 
dist = d; 
n = i; 
} 
} 
} 
p = n;
used[p] = true; 
}while(start!=p); 
    } 

Geometry Concepts: Using Geometry in Topcoder Problems
By lbackstrom — topcoder member

PointInPolygon
TVTower
Satellites
Further Problems

PointInPolygon (SRM 187)
Requires: Line­Line Intersection, Line­Point Distance

First off, we can use our Line­Point Distance code to test for the "BOUNDARY" case. If the distance from any segment to the test point
is 0, then return "BOUNDARY". If you didn’t have that code pre­written, however, it would probably be easier to just check and see if
the test point is between the minimum and maximum x and y values of the segment. Since all of the segments are vertical or
horizontal, this is sufficient, and the more general code is not necessary.

Next we have to check if a point is in the interior or the exterior. Imagine picking a point in the interior and then drawing a ray from
that point out to infinity in some direction. Each time the ray crossed the boundary of the polygon, it would cross from the interior to
the exterior, or vice versa. Therefore, the test point is on the interior if, and only if, the ray crosses the boundary an odd number of
times. In practice, we do not have to draw a raw all the way to infinity. Instead, we can just use a very long line segment from the test
point to a point that is sufficiently far away. If you pick the far away point poorly, you will end up having to deal with cases where the
long segment touches the boundary of the polygon where two edges meet, or runs parallel to an edge of a polygon ? both of which are
tricky cases to deal with. The quick and dirty way around this is to pick two large random numbers for the endpoint of the segment.
While this might not be the most elegant solution to the problem, it works very well in practice. The chance of this segment intersecting
anything but the interior of an edge are so small that you are almost guaranteed to get the right answer. If you are really concerned,
you could pick a few different random points, and take the most common answer.

    String testPoint(verts, x, y){ 
int N = lengthof(verts); 
int cnt = 0; 
double x2 = random()*1000+1000; 
double y2 = random()*1000+1000; 
for(int i = 0; i<N; i++){ 
if(distPointToSegment(verts[i],verts[(i+1)%N],x,y) == 0) 
return "BOUNDARY"; 
if(segmentsIntersect((verts[i],verts[(i+1)%N],{x,y},{x2,y2})) 
cnt++; 
} 
if(cnt%2 == 0)return "EXTERIOR"; 
else return "INTERIOR"; 
    } 

TVTower(SRM 183)
Requires: Finding a Circle From 3 Points

In problems like this, the first thing to figure out is what sort of solutions might work. In this case, we want to know what sort of circles
we should consider. If a circle only has two points on it, then, in most cases, we can make a slightly smaller circle, that still has those
two points on it. The only exception to this is when the two points are exactly opposite each other on the circle. Three points, on the
other hand, uniquely define a circle, so if there are three points on the edge of a circle, we cannot make it slightly smaller, and still have
all three of them on the circle. Therefore, we want to consider two different types of circles: those with two points exactly opposite each
other, and those with three points on the circle. Finding the center of the first type of circle is trivial ? it is simply halfway between the
two points. For the other case, we can use the method for Finding a Circle From 3 Points. Once we find the center of a potential circle, it
is then trivial to find the minimum radius.

    int[] x, y; 
    int N; 
    double best = 1e9; 
    void check(double cx, double cy){ 
 double max = 0; 
for(int i = 0; i< N; i++){ 
max = max(max,dist(cx,cy,x[i],y[i])); 
} 
best = min(best,max); 
    } 
    double minRadius(int[] x, int[] y){ 
this.x = x; 
this.y = y; 
N = lengthof(x); 
if(N==1)return 0; 
for(int i = 0; i<N; i++){ 
for(int j = i+1; j<N; j++){ 
double cx = (x[i]+x[j])/2.0; 
double cy = (y[i]+y[j])/2.0; 
check(cx,cy); 
for(int k = j+1; k<N; k++){ 
//center gives the center of the circle with 
//(x[i],y[i]), (x[j],y[j]), and (x[k],y[k]) on 
//the edge of the circle. 
double[] c = center(i,j,k); 
check(c[0],c[1]); 
} 
} 
} 
return best; 
    } 

Satellites (SRM 180)
Requires: Line­Point Distance

This problem actually requires an extension of the Line­Point Distance method discussed previously. It is the same basic principle, but
the formula for the cross product is a bit different in three dimensions.

The first step here is to convert from spherical coordinates into (x,y,z) triples, where the center of the earth is at the origin.

    double x = sin(lng/180*PI)*cos(lat/180*PI)*alt; 
    double y = cos(lng/180*PI)*cos(lat/180*PI)*alt; 
    double z = sin(lat/180*PI)*alt; 

Now, we want to take the cross product of two 3­D vectors. As I mentioned earlier, the cross product of two vectors is actually a vector,
and this comes into play when working in three dimensions. Given vectors (x1,y1,z1) and (x2,y2,z2) the cross product is defined as the
vector (i,j,k) where

    i = y1z2 ‐ y2z1; 
    j = x2z1 ‐ x1z2; 
    k = x1y2 ‐ x2y1; 

Notice that if z1 = z2 = 0, then i and j are 0, and k is equal to the cross product we used earlier. In three dimensions, the cross product
is still related to the area of the parallelogram with two sides from the two vectors. In this case, the area of the parallelogram is the
norm of the vector: sqrt(i*i+j*j+k*k).

Hence, as before, we can determine the distance from a point (the center of the earth) to a line (the line from a satellite to a rocket).
However, the closest point on the line segment between a satellite and a rocket may be one of the end points of the segment, not the
closest point on the line. As before, we can use the dot product to check this. However, there is another way which is somewhat simpler
to code. Say that you have two vectors originating at the origin, S and R, going to the satellite and the rocket, and that |X| represents
the norm of a vector X. 
Then, the closest point to the origin is R if |R|2 + |R‐S|2 = |S|2 and it is S if |S|2 + |R‐S|2 = |R|2
Naturally, this trick works in two dimensions also.

Further Problems
Once you think you’ve got a handle on the three problems above, you can give these ones a shot. You should be able to solve all of
them with the methods I’ve outlined, and a little bit of cleverness. I’ve arranged them in what I believe to ascending order of difficulty.
ConvexPolygon (SRM 166)
Requires: Polygon Area

Surveyor (TCCC ’04 Qual 1)
Requires: Polygon Area

Travel (TCI ’02)
Requires: Dot Product

Parachuter (TCI ’01 Round 3)
Requires: Point In Polygon, Line­Line Intersection

PuckShot (SRM 186)
Requires: Point In Polygon, Line­Line Intersection

ElectronicScarecrows (SRM 173)
Requires: Convex Hull, Dynamic Programming

Mirrors (TCI ’02 Finals)
Requires: Reflection, Line­Line Intersection

Symmetry (TCI ’02 Round 4)
Requires: Reflection, Line­Line Intersection
Warehouse (SRM 177)
Requires: Line­Point Distance, Line­Line Intersection

The following problems all require geometry, and the topics discussed in this article will be useful. However, they all require some
additional skills. If you got stuck on them, the editorials are a good place to look for a bit of help. If you are still stuck, there has yet to
be a problem related question on the round tables that went unanswered.
DogWoods (SRM 201)
ShortCut (SRM 215)
SquarePoints (SRM 192)
Tether (TCCC ’03 W/MW Regional)
TurfRoller (SRM 203)
Watchtower (SRM 176)

Introduction to Graphs and Their Data Structures: Section 1
Section 1: Recognizing and Representing a Graph

By gladius — topcoder member
Discuss this article in the forums

Introduction
Recognizing a graph problem
Representing a graph and key concepts
Singly linked lists
Trees
Graphs
Array representation

Introduction
Graphs are a fundamental data structure in the world of programming, and this is no less so on topcoder. Usually appearing as the hard
problem in Division 2, or the medium or hard problem in Division 1, there are many different forms solving a graph problem can take.
They can range in difficulty from finding a path on a 2D grid from a start location to an end location, to something as hard as finding
the maximum amount of water that you can route through a set of pipes, each of which has a maximum capacity (also known as the
maximum­flow minimum­cut problem – which we will discuss later). Knowing the correct data structures to use with graph problems is
critical. A problem that appears intractable may prove to be a few lines with the proper data structure, and luckily for us the standard
libraries of the languages used by topcoder help us a great deal here!

Recognizing a graph problem
The first key to solving a graph related problem is recognizing that it is a graph problem. This can be more difficult than it sounds,
because the problem writers don’t usually spell it out for you. Nearly all graph problems will somehow use a grid or network in the
problem, but sometimes these will be well disguised. Secondly, if you are required to find a path of any sort, it is usually a graph
problem as well. Some common keywords associated with graph problems are: vertices, nodes, edges, connections, connectivity, paths,
cycles and direction. An example of a description of a simple problem that exhibits some of these characteristics is:

"Bob has become lost in his neighborhood. He needs to get from his current position back to his home. Bob’s neighborhood is a 2
dimensional grid, that starts at (0, 0) and (width – 1, height – 1). There are empty spaces upon which bob can walk with no difficulty,
and houses, which Bob cannot pass through. Bob may only move horizontally or vertically by one square at a time.

Bob’s initial position will be represented by a ‘B’ and the house location will be represented by an ‘H’. Empty squares on the grid are
represented by ‘.’ and houses are represented by ‘X’. Find the minimum number of steps it takes Bob to get back home, but if it is not
possible for Bob to return home, return ­1.

An example of a neighborhood of width 7 and height 5:

    ...X..B 
    .X.X.XX 
    .H..... 
    ...X... 
    .....X." 

Once you have recognized that the problem is a graph problem it is time to start building up your representation of the graph in
memory.

Representing a graph and key concepts
Graphs can represent many different types of systems, from a two­dimensional grid (as in the problem above) to a map of the internet
that shows how long it takes data to move from computer A to computer B. We first need to define what components a graph consists
of. In fact there are only two, nodes and edges. A node (or vertex) is a discrete position in the graph. An edge (or connection) is a link
between two vertices that can be either directed or undirected and may have a cost associated with it. An undirected edge means that
there is no restriction on the direction you can travel along the edge. So for example, if there were an undirected edge from A to B you
could move from A to B or from B to A. A directed edge only allows travel in one direction, so if there were a directed edge from A to B
you could travel from A to B, but not from B to A. An easy way to think about edges and vertices is that edges are a function of two
vertices that returns a cost. We will see an example of this methodology in a second.

For those that are used to the mathematical description of graphs, a graph G = {V, E} is defined as a set of vertices, V, and a collection
of edges (which is not necessarily a set), E. An edge can then be defined as (u, v) where u and v are elements of V. There are a few
technical terms that it would be useful to discuss at this point as well:

Order – The number of vertices in a graph Size – The number of edges in a graph

Singly linked lists
An example of one of the simplest types of graphs is a singly linked list! Now we can start to see the power of the graph data structure,
as it can represent very complicated relationships, but also something as simple as a list.

A singly linked list has one "head" node, and each node has a link to the next node. So the structure looks like this:
    structure node
[node] link; 
[data] 
    end 

    node head; 

A simple example would be:

    node B, C; 
    head.next = B;
B.next = C;
C.next = null;

This would be represented graphically as head ­> B ­> C ­> null. I’ve used null here to represent the end of a list.

Getting back to the concept of a cost function, our cost function would look as follows:

    cost(X, Y) := if (X.link = Y) return 1; 
    else if (X = Y) return 0; 
    else "Not possible" 

This cost function represents the fact that we can only move directly to the link node from our current node. Get used to seeing cost
functions because anytime that you encounter a graph problem you will be dealing with them in some form or another! A question that
you may be asking at this point is "Wait a second, the cost from A to C would return not possible, but I can get to C from A by stepping
through B!" This is a very valid point, but the cost function simply encodes the *direct* cost from a node to another. We will cover how
to find distances in generic graphs later on.

Now that we have seen an example of the one of the simplest types of graphs, we will move to a more complicated example.

Trees
There will be a whole section written on trees. We are going to cover them very briefly as a stepping­stone along the way to a full­
fledged graph. In our list example above we are somewhat limited in the type of data we can represent. For example, if you wanted to
start a family tree (a hierarchal organization of children to parents, starting from one child) you would not be able to store more than
one parent per child. So we obviously need a new type of data structure. Our new node structure will look something like this:

    structure node
[node] mother, father; 
[string] name 
    end 

    node originalChild; 

With a cost function of:

    cost(X, Y) := if ((X.mother = Y) or (X.father = Y)) return 1; 
    else if (X = Y) return 0; 
    else "Not possible" 

Here we can see that every node has a mother and father. And since node is a recursive structure definition, every mother has mother
and father, and every father has a mother and father, and so on. One of the problems here is that it might be possible to form a loop if
you actually represented this data structure on a computer. And a tree clearly cannot have a loop. A little mind exercise will make this
clear: a father of a child is also the son of that child? It’s starting to make my head hurt already. So you have to be very careful when
constructing a tree to make sure that it is truly a tree structure, and not a more general graph. A more formal definition of a tree is that
it is a connected acyclic graph. This simply means that there are no cycles in the graph and every node is connected to at least one
other node in the graph.

Another thing to note is that we could imagine a situation easily where the tree requires more than two node references, for example in
an organizational hierarchy, you can have a manager who manages many people then the CEO manages many managers. Our example
above was what is known as a binary tree, since it only has two node references. Next we will move onto constructing a data structure
that can represent a general graph!

Graphs
A tree only allows a node to have children, and there cannot be any loops in the tree, with a more general graph we can represent
many different situations. A very common example used is flight paths between cities. If there is a flight between city A and city B
there is an edge between the cities. The cost of the edge can be the length of time that it takes for the flight, or perhaps the amount of
fuel used.

The way that we will represent this is to have a concept of a node (or vertex) that contains links to other nodes, and the data
associated with that node. So for our flight path example we might have the name of the airport as the node data, and for every flight
leaving that city we have an element in neighbors that points to the destination.

    structure node
[list of nodes] neighbors 
[data] 
    end 

    cost(X, Y) := if (X.neighbors contains Y) return X.neighbors[Y]; 
else "Not possible" 

    list nodes; 

This is a very general way to represent a graph. It allows us to have multiple edges from one node to another and it is a very compact
representation of a graph as well. However the downside is that it is usually more difficult to work with than other representations (such
as the array method discussed below).
Array representation
Representing a graph as a list of nodes is a very flexible method. But usually on topcoder we have limits on the problems that attempt
to make life easier for us. Normally our graphs are relatively small, with a small number of nodes and edges. When this is the case we
can use a different type of data structure that is easier to work with.

The basic concept is to have a 2 dimensional array of integers, where the element in row i, at column j represents the edge cost from
node i to j. If the connection from i to j is not possible, we use some sort of sentinel value (usually a very large or small value, like ­1 or
the maximum integer). Another nice thing about this type of structure is that we can represent directed or undirected edges very easily.

So for example, the following connection matrix:

A  B  C 
    A   0  1  5 
    B  ‐1  0  1 
    C  ‐1 ‐1  0 

Would mean that node A has a 0 weight connection to itself, a 1 weight connection to node B and 5 weight connection to node C. Node
B on the other hand has no connection to node A, a 0 weight connection to itself, and a 1 weight connection to C. Node C is connected
to nobody. This graph would look like this if you were to draw it:

This representation is very convenient for graphs that do not have multiple edges between each node, and allows us to simplify working
with the graph.

Introduction to Graphs and Their Data Structures: Section 2
Section 2: Searching a Graph

By gladius — topcoder member

Basic methods for searching graphs
Introduction
Stack
Depth First Search
Queue
Breadth First Search

Basic methods for searching graphs
Introduction
So far we have learned how to represent our graph in memory, but now we need to start doing something with this information. There
are two methods for searching graphs that are extremely prevalent, and will form the foundations for more advanced algorithms later
on. These two methods are the Depth First Search and the Breadth First Search.

We will begin with the depth first search method, which will utilize a stack. This stack can either by represented explicitly (by a stack
data­type in our language) or implicitly when using recursive functions.

Stack
A stack is one of the simplest data structures available. There are four main operations on a stack:

1. Push – Adds an element to the top of the stack
2. Pop – Removes the top element from the stack
3. Top – Returns the top element on the stack
4. Empty – Tests if the stack is empty or not

In C++, this is done with the STL class stack:

    #include <stack> 
    std::stack<int> myStack; 

In Java, we use the Stack class:

    import java.util.*; 
    Stack stack = new Stack(); 

In C#, we use Stack class:

    using System.Collections; 
    Stack stack = new Stack(); 

Depth First Search
Now to solve an actual problem using our search! The depth first search is well geared towards problems where we want to find any
solution to the problem (not necessarily the shortest path), or to visit all of the nodes in the graph. A recent topcoder problem was a
classic application of the depth first search, the flood­fill. The flood­fill operation will be familiar to anyone who has used a graphic
painting application. The concept is to fill a bounded region with a single color, without leaking outside the boundaries.
This concept maps extremely well to a Depth First search. The basic concept is to visit a node, then push all of the nodes to be visited
onto the stack. To find the next node to visit we simply pop a node of the stack, and then push all the nodes connected to that one onto
the stack as well and we continue doing this until all nodes are visited. It is a key property of the Depth First search that we not visit
the same node more than once, otherwise it is quite possible that we will recurse infinitely. We do this by marking the node as we visit
it.

So the basic structure will look something like this:

    dfs(node start) { 
stack<node> s; 
s.push(start);
while (s.empty() == false) {
top = s.top(); 
s.pop();

if (top is not marked as visited) { 
check for termination condition (have we reached the node we want to?) 

mark top as visited; 
add all of top's neighbors to the stack. 
} 
} 
    } 

Alternatively we can define the function recursively as follows:

    dfs(node current) { 
mark current as visited; 
visit all of current's unvisited neighbors by calling dfs(neighbor) 
    } 

The problem we will be discussing is grafixMask, a Division 1 500 point problem from SRM 211. This problem essentially asks us to find
the number of discrete regions in a grid that has been filled in with some values already. Dealing with grids as graphs is a very powerful
technique, and in this case makes the problem quite easy.

We will define a graph where each node has 4 connections, one each to the node above, left, right and below. However, we can
represent these connections implicitly within the grid, we need not build out any new data structures. The structure we will use to
represent the grid in grafixMask is a two dimensional array of booleans, where regions that we have already determined to be filled in
will be set to true, and regions that are unfilled are set to false.

To set up this array given the data from the problem is very simple, and looks something like this:

    bool fill[600][400]; 
    initialize fills to false; 

    foreach rectangle in Rectangles 
set from (rectangle.left, rectangle.top) to (rectangle.right, retangle.bottom) to true 

Now we have an initialized connectivity grid. When we want to move from grid position (x, y) we can either move up, down, left or
right. When we want to move up for example, we simply check the grid position in (x, y­1) to see if it is true or false. If the grid
position is false, we can move there, if it is true, we cannot.

Now we need to determine the area of each region that is left. We don’t want to count regions twice, or pixels twice either, so what we
will do is set fill[x][y] to true when we visit the node at (x, y). This will allow us to perform a Depth­First search to visit all of the nodes
in a connected region and never visit any node twice, which is exactly what the problem wants us to do! So our loop after setting
everything up will be:

    int[] result; 

    for x = 0 to 599 
for y = 0 to 399 
if (fill[x][y] == false) 
result.addToBack(doFill(x,y)); 

All this code does is check if we have not already filled in the position at (x, y) and then calls doFill() to fill in that region. At this point
we have a choice, we can define doFill recursively (which is usually the quickest and easiest way to do a depth first search), or we can
define it explicitly using the built in stack classes. I will cover the recursive method first, but we will soon see for this problem there are
some serious issues with the recursive method.

We will now define doFill to return the size of the connected area and the start position of the area:

    int doFill(int x, int y) { 
// Check to ensure that we are within the bounds of the grid, if not, return 0 
if (x < 0 || x >= 600) return 0; 
// Similar check for y 
if (y < 0 || y >= 400) return 0; 
// Check that we haven't already visited this position, as we don't want to count it twice 
if (fill[x][y]) return 0; 

// Record that we have visited this node 
fill[x][y] = true; 

// Now we know that we have at least one empty square, then we will recursively attempt to 
// visit every node adjacent to this node, and add those results together to return. 
return 1 + doFill(x ‐ 1, y) + doFill(x + 1, y) + doFill(x, y + 1) + doFill(x, y ‐ 1); 
    } 
This solution should work fine, however there is a limitation due to the architecture of computer programs. Unfortunately, the memory
for the implicit stack, which is what we are using for the recursion above is more limited than the general heap memory. In this
instance, we will probably overflow the maximum size of our stack due to the way the recursion works, so we will next discuss the
explicit method of solving this problem.

Sidenote:

Stack memory is used whenever you call a function; the variables to the function are pushed onto the stack by the compiler for you.
When using a recursive function, the variables keep getting pushed on until the function returns. Also any variables the compiler needs
to save between function calls must be pushed onto the stack as well. This makes it somewhat difficult to predict if you will run into
stack difficulties. I recommend using the explicit Depth First search for every situation you are at least somewhat concerned about
recursion depth.

In this problem we may recurse a maximum of 600 * 400 times (consider the empty grid initially, and what the depth first search will
do, it will first visit 0,0 then 1,0, then 2,0, then 3,0 … until 599, 0. Then it will go to 599, 1 then 598, 1, then 597, 1, etc. until it
reaches 599, 399. This will push 600 * 400 * 2 integers onto the stack in the best case, but depending on what your compiler does it
may in fact be more information. Since an integer takes up 4 bytes we will be pushing 1,920,000 bytes of memory onto the stack,
which is a good sign we may run into trouble.

We can use the same function definition, and the structure of the function will be quite similar, just we won’t use any recursion any
more:

    class node { int x, y; } 

    int doFill(int x, int y) { 
int result = 0; 

// Declare our stack of nodes, and push our starting node onto the stack 
stack<node> s; 
s.push(node(x, y));

while (s.empty() == false) { 
node top = s.top(); 
s.pop();

// Check to ensure that we are within the bounds of the grid, if not, continue 
if (top.x < 0 || top.x >= 600) continue; 
// Similar check for y 
if (top.y < 0 || top.y >= 400) continue; 
// Check that we haven't already visited this position, as we don't want to count it twice 
if (fill[top.x][top.y]) continue; 

fill[top.x][top.y] = true; // Record that we have visited this node 

// We have found this node to be empty, and part 
// of this connected area, so add 1 to the result 
result++; 

// Now we know that we have at least one empty square, then we will attempt to 
// visit every node adjacent to this node. 
s.push(node(top.x + 1, top.y));
s.push(node(top.x ‐ 1, top.y));
s.push(node(top.x, top.y + 1));
s.push(node(top.x, top.y ‐ 1));
} 
return result; 
    } 

As you can see, this function has a bit more overhead to manage the stack structure explicitly, but the advantage is that we can use the
entire memory space available to our program and in this case, it is necessary to use that much information. However, the structure is
quite similar and if you compare the two implementations they are almost exactly equivalent.

Congratulations, we have solved our first question using a depth first search! Now we will move onto the depth­first searches close
cousin the Breadth First search.

If you want to practice some DFS based problems, some good ones to look at are:

TCCC 03 Quarterfinals – Marketing – Div 1 500
TCCC 03 Semifinals Room 4 – Circuits – Div 1 275

Queue
A queue is a simple extension of the stack data type. Whereas the stack is a FILO (first­in last­out) data structure the queue is a FIFO
(first­in first­out) data structure. What this means is the first thing that you add to a queue will be the first thing that you get when you
perform a pop().

There are four main operations on a queue:

1. Push – Adds an element to the back of the queue
2. Pop – Removes the front element from the queue
3. Front – Returns the front element on the queue
4. Empty – Tests if the queue is empty or not

In C++, this is done with the STL class queue:

    #include <queue> 
    queue<int> myQueue; 
In Java, we unfortunately don’t have a Queue class, so we will approximate it with the LinkedList class. The operations on a linked list
map well to a queue (and in fact, sometimes queues are implemented as linked lists), so this will not be too difficult.

The operations map to the LinkedList class as follows:

1. Push – boolean LinkedList.add(Object o)
2. Pop – Object LinkedList.removeFirst()
3. Front – Object LinkedList.getFirst()
4. Empty – int LinkedList.size()

import java.util.*;
LinkedList myQueue = new LinkedList();

In C#, we use Queue class:

The operations map to the Queue class as follows:

1. Push – void Queue.Enqueue(Object o)
2. Pop – Object Queue.Dequeue()
3. Front – Object Queue.Peek()
4. Empty – int Queue.Count

using System.Collections;
Queue myQueue = new Queue();

Breadth First Search
The Breadth First search is an extremely useful searching technique. It differs from the depth­first search in that it uses a queue to
perform the search, so the order in which the nodes are visited is quite different. It has the extremely useful property that if all of the
edges in a graph are unweighted (or the same weight) then the first time a node is visited is the shortest path to that node from the
source node. You can verify this by thinking about what using a queue means to the search order. When we visit a node and add all the
neighbors into the queue, then pop the next thing off of the queue, we will get the neighbors of the first node as the first elements in
the queue. This comes about naturally from the FIFO property of the queue and ends up being an extremely useful property. One thing
that we have to be careful about in a Breadth First search is that we do not want to visit the same node twice, or we will lose the
property that when a node is visited it is the quickest path to that node from the source.

The basic structure of a breadth first search will look this:

    void bfs(node start) { 
queue<node> s; 
s.push(start);
mark start as visited
while (s.empty() == false) {
top = s.front(); 
s.pop();

check for termination condition (have we reached the node we want to?)

add all of top's unvisited neighbors to the queue 
mark all of top's unvisited neighbors as visited 
} 
    } 

Notice the similarities between this and a depth­first search, we only differ in the data structure used and we mark a vertex visited as
we push it into the queue, not as we pop it.

The problem we will be discussing in relation to the Breadth First search is a bit harder than the previous example, as we are dealing
with a slightly more complicated search space. The problem is the 1000 from Division 1 in SRM 156, Pathfinding. Once again we will be
dealing in a grid­based problem, so we can represent the graph structure implicitly within the grid.

A quick summary of the problem is that we want to exchange the positions of two players on a grid. There are impassable spaces
represented by ‘X’ and spaces that we can walk in represented by ‘ ‘. Since we have two players our node structure becomes a bit more
complicated, we have to represent the positions of person A and person B. Also, we won’t be able to simply use our array to represent
visited positions any more, we will have an auxiliary data structure to do that. Also, we are allowed to make diagonal movements in this
problem, so we now have 9 choices, we can move in one of 8 directions or simply stay in the same position. Another little trick that we
have to watch for is that the players can not just swap positions in a single turn, so we have to do a little bit of validity checking on the
resulting state.

First, we set up the node structure and visited array:

    class node { 
int player1X, player1Y, player2X, player2Y; 
int steps; // The current number of steps we have taken to reach this step
    } 

    bool visited[20][20][20][20]; 

Here a node is represented as the (x,y) positions of player 1 and player 2. It also has the current steps that we have taken to reach the
current state, we need this because the problem asks us what the minimum number of steps to switch the two players will be. We are
guaranteed by the properties of the Breadth First search that the first time we visit the end node, it will be as quickly as possible (as all
of our edge costs are 1).

The visited array is simply a direct representation of our node in array form, with the first dimension being player1X, second player1Y,
etc. Note that we don’t need to keep track of steps in the visited array.

Now that we have our basic structure set up, we can solve the problem (note that this code is not compilable):

    void pushToQueue(queue<node> q, node v) { 
if (visited[v.player1X][v.player1Y][v.player2X][v.player2Y]) return; 
 q.push(v);
visited[v.player1X][v.player1Y][v.player2X][v.player2Y] = true;
    } 

    int minTurns(String[] board) { 
int width = board[0].length; 
int height = board.length; 

node start; 
// Find the initial position of A and B, and save them in start. 

queue<node> q; 
pushToQueue(q, start) 
while (q.empty() == false) { 
node top = q.front(); 
q.pop();

// Check if player 1 or player 2 is out of bounds, or on an X square, if so continue 
// Check if player 1 or player 2 is on top of each other, if so continue 

// Check if the current positions of A and B are the opposite of what they were in start. 
// If they are we have exchanged positions and are finished! 
if (top.player1X == start.player2X && top.player1Y == start.player2Y && 
top.player2X == start.player1X && top.player2Y == start.player1Y) 
return top.steps; 

// Now we need to generate all of the transitions between nodes, we can do this quite easily using some 
// nested for loops, one for each direction that it is possible for one player to move.  Since we need 
// to generate the following deltas: (‐1,‐1), (‐1,0), (‐1,1), (0,‐1), (0,0), (0,1), (1,‐1), (1,0), (1,1) 
// we can use a for loop from ‐1 to 1 to do exactly that. 
for (int player1XDelta = ‐1; player1XDelta <= 1; player1XDelta++) { 
for (int player1YDelta = ‐1; player1YDelta <= 1; player1YDelta++) { 
for (int player2XDelta = ‐1; player2XDelta <= 1; player2XDelta++) { 
for (int player2YDelta = ‐1; player2YDelta <= 1; player2YDelta++) { 
// Careful though!  We have to make sure that player 1 and 2 did not swap positions on this turn 
if (top.player1X == top.player2X + player2XDelta && top.player1Y == top.player2Y + player2YDelta && 
top.player2X == top.player1X + player1XDelta && top.player2Y == top.player1Y + player1YDelta) 
continue; 

// Add the new node into the queue 
pushToQueue(q, node(top.player1X + player1XDelta, top.player1Y + player1YDelta, 
top.player2X + player2XDelta, top.player2Y + player2YDelta, 
top.steps + 1)); 
} 
} 
} 
} 
} 

// It is not possible to exchange positions, so 
// we return ‐1.  This is because we have explored 
// all the states possible from the starting state, 
// and haven't returned an answer yet. 
return ‐1;
    } 

This ended up being quite a bit more complicated than the basic Breadth First search implementation, but you can still see all of the
basic elements in the code. Now, if you want to practice more problems where Breadth First search is applicable, try these:

Inviational 02 Semifinal Room 2 – Div 1 500 – Escape

Introduction to Graphs and Their Data Structures: Section 3
Section 3: Finding the Best Path through a Graph

By gladius — topcoder member

Finding the best path through a graph
Dijkstra (Heap method)
Floyd­Warshall

Finding the best path through a graph
An extremely common problem on topcoder is to find the shortest path from one position to another. There are a few different ways for
going about this, each of which has different uses. We will be discussing two different methods, Dijkstra using a Heap and the Floyd
Warshall method.

Dijkstra (Heap method)
Dijkstra using a Heap is one of the most powerful techniques to add to your topcoder arsenal. It essentially allows you to write a
Breadth First search, and instead of using a Queue you use a Priority Queue and define a sorting function on the nodes such that the
node with the lowest cost is at the top of the Priority Queue. This allows us to find the best path through a graph in O(m * log(n)) time
where n is the number of vertices and m is the number of edges in the graph.
Sidenote:
If you haven’t seen big­O notation before then I recommend reading this.

First however, an introduction to the Priority Queue/Heap structure is in order. The Heap is a fundamental data structure and is
extremely useful for a variety of tasks. The property we are most interested in though is that it is a semi­ordered data structure. What I
mean by semi­ordered is that we define some ordering on elements that are inserted into the structure, then the structure keeps the
smallest (or largest) element at the top. The Heap has the very nice property that inserting an element or removing the top element
takes O(log n) time, where n is the number of elements in the heap. Simply getting the top value is an O(1) operation as well, so the
Heap is perfectly suited for our needs.

The fundamental operations on a Heap are:

1. Add – Inserts an element into the heap, putting the element into the correct ordered location.
2. Pop – Pops the top element from the heap, the top element will either be the highest or lowest element, depending on
implementation.
3. Top – Returns the top element on the heap.
4. Empty – Tests if the heap is empty or not.

Pretty close to the Queue or Stack, so it’s only natural that we apply the same type of searching principle that we have used before,
except substitute the Heap in place of the Queue or Stack. Our basic search routine (remember this one well!) will look something like
this:

    void dijkstra(node start) { 
priorityQueue s; 
s.add(start);
while (s.empty() == false) {
top = s.top(); 
s.pop();
mark top as visited;
} 
    } 

check for termination condition (have we reached the target node?)
add all of top’s unvisited neighbors to the stack.

Unfortunately, not all of the default language libraries used in topcoder have an easy to use priority queue structure.

C++ users are lucky to have an actual priority_queue<> structure in the STL, which is used as follows:

    #include  
    using namespace std; 
    priority_queue pq; 
1. Add ‐ void pq.push(type)
2. Pop ‐ void pq.pop()
3. Top ‐ type pq.top()
4. Empty ‐ bool pq.empty()

However, you have to be careful as the C++ priority_queue<> returns the *highest* element first, not the lowest. This has been the
cause of many solutions that should be O(m * log(n)) instead ballooning in complexity, or just not working.

To define the ordering on a type, there are a few different methods. The way I find most useful is the following though:

    Define your structure: 
    struct node { 
int cost; 
int at; 
    }; 

And we want to order by cost, so we define the less than operator for this structure as follows:

    bool operator<(const node &leftNode, const node &rightNode) { 
if (leftNode.cost != rightNode.cost) return leftNode.cost < rightNode.cost; 
if (leftNode.at != rightNode.at) return leftNode.at < rightNode.at; 
return false; 
    } 

Even though we don’t need to order by the ‘at’ member of the structure, we still do otherwise elements with the same cost but different
‘at’ values may be coalesced into one value. The return false at the end is to ensure that if two duplicate elements are compared the
less than operator will return false.

Java users unfortunately have to do a bit of makeshift work, as there is not a direct implementation of the Heap structure. We can
approximate it with the TreeSet structure which will do full ordering of our dataset. It is less space efficient, but will serve our purposes
fine.

    import java.util.*; 
    TreeSet pq = new TreeSet(); 

1. Add ‐ boolean add(Object o)
2. Pop ‐ boolean remove(Object o)

In this case, we can remove anything we want, but pop should remove the first element, so we will always call it like

    this: pq.remove(pq.first()); 
3. Top ‐ Object first()
4. Empty ‐ int size()
To define the ordering we do something quite similar to what we use in C++:

    class Node implements Comparable { 
public int cost, at; 

public int CompareTo(Object o) { 
Node right = (Node)o; 
if (cost < right.cost) return ‐1; 
if (cost > right.cost) return 1; 
if (at < right.at) return ‐1; 
if (at > right.at) return 1; 
return 0; 
} 
    } 

C# users also have the same problem, so they need to approximate as well, unfortunately the closest thing to what we want that is
currently available is the SortedList class, and it does not have the necessary speed (insertions and deletions are O(n) instead of O(log
n)). Unfortunately there is no suitable built­in class for implementing heap based algorithms in C#, as the HashTable is not suitable
either.

Getting back to the actual algorithm now, the beautiful part is that it applies as well to graphs with weighted edges as the Breadth First
search does to graphs with un­weighted edges. So we can now solve much more difficult problems (and more common on topcoder)
than is possible with just the Breadth First search.

There are some extremely nice properties as well, since we are picking the node with the least total cost so far to explore first, the first
time we visit a node is the best path to that node (unless there are negative weight edges in the graph). So we only have to visit each
node once, and the really nice part is if we ever hit the target node, we know that we are done.

For the example here we will be using KiloManX, from SRM 181, the Div 1 1000. This is an excellent example of the application of the
Heap Dijkstra problem to what appears to be a Dynamic Programming question initially. In this problem the edge weight between nodes
changes based on what weapons we have picked up. So in our node we at least need to keep track of what weapons we have picked
up, and the current amount of shots we have taken (which will be our cost). The really nice part is that the weapons that we have
picked up corresponds to the bosses that we have defeated as well, so we can use that as a basis for our visited structure. If we
represent each weapon as a bit in an integer, we will have to store a maximum of 32,768 values (2^15, as there is a maximum of 15
weapons). So we can make our visited array simply be an array of 32,768 booleans. Defining the ordering for our nodes is very easy in
this case, we want to explore nodes that have lower amounts of shots taken first, so given this information we can define our basic
structure to be as follows:

    boolean visited[32768]; 

    class node { 
int weapons; 
int shots;
// Define a comparator that puts nodes with less shots on top appropriate to your language 
    }; 

Now we will apply the familiar structure to solve these types of problems.

    int leastShots(String[] damageChart, int[] bossHealth) { 
priorityQueue pq; 

pq.push(node(0, 0)); 

while (pq.empty() == false) { 
node top = pq.top(); 
pq.pop(); 

// Make sure we don't visit the same configuration twice 
if (visited[top.weapons]) continue; 
visited[top.weapons] = true; 

// A quick trick to check if we have all the weapons, meaning we defeated all the bosses. 
// We use the fact that (2^numWeapons ‐ 1) will have all the numWeapons bits set to 1. 
if (top.weapons == (1 << numWeapons) ‐ 1) 
return top.shots; 

for (int i = 0; i < damageChart.length; i++) { 
// Check if we've already visited this boss, then don't bother trying him again 
if ((top.weapons >> i) & 1) continue; 

// Now figure out what the best amount of time that we can destroy this boss is, given the weapons we have. 
// We initialize this value to the boss's health, as that is our default (with our KiloBuster). 
int best = bossHealth[i]; 
for (int j = 0; j < damageChart.length; j++) { 
if (i == j) continue; 
if (((top.weapons >> j) & 1) && damageChart[j][i] != '0') { 
// We have this weapon, so try using it to defeat this boss 
int shotsNeeded = bossHealth[i] / (damageChart[j][i] ‐ '0'); 
if (bossHealth[i] % (damageChart[j][i] ‐ '0') != 0) shotsNeeded++; 
best = min(best, shotsNeeded); 
} 
} 

// Add the new node to be searched, showing that we defeated boss i, and we used 'best' shots to defeat him. 
pq.add(node(top.weapons | (1 << i), top.shots + best)); 
} 
 } 
    } 

There are a huge number of these types of problems on topcoder; here are some excellent ones to try out:

SRM 150 – Div 1 1000 – RoboCourier
SRM 194 – Div 1 1000 – IslandFerries
SRM 198 – Div 1 500 – DungeonEscape
TCCC ’04 Round 4 – 500 – Bombman

Floyd­Warshall
Floyd­Warshall is a very powerful technique when the graph is represented by an adjacency matrix. It runs in O(n^3) time, where n is
the number of vertices in the graph. However, in comparison to Dijkstra, which only gives us the shortest path from one source to the
targets, Floyd­Warshall gives us the shortest paths from all source to all target nodes. There are other uses for Floyd­Warshall as well;
it can be used to find connectivity in a graph (known as the Transitive Closure of a graph).

First, however we will discuss the Floyd Warshall All­Pairs Shortest Path algorithm, which is the most similar to Dijkstra. After running
the algorithm on the adjacency matrix the element at adj[i][j] represents the length of the shortest path from node i to node j. The
pseudo­code for the algorithm is given below:

    for (k = 1 to n) 
for (i = 1 to n) 
for (j = 1 to n) 
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);  

As you can see, this is extremely simple to remember and type. If the graph is small (less than 100 nodes) then this technique can be
used to great effect for a quick submission.

An excellent problem to test this out on is the Division 2 1000 from SRM 184, TeamBuilder.

Greedy is Good
By supernova — topcoder member
Discuss this article in the forums

John Smith is in trouble! He is a topcoder member and once he learned to master the "Force" of dynamic programming, he began
solving problem after problem. But his once obedient computer acts quite unfriendly today. Following his usual morning ritual, John
woke up at 10 AM, had a cup of coffee and went to solve a problem before breakfast. Something didn’t seem right from the beginning,
but based on his vast newly acquired experience, he wrote the algorithm in a flash. Tired of allocating matrices morning after morning,
the computer complained: "Segmentation fault!". Despite his empty stomach, John has a brilliant idea and gets rid of his beloved
matrix by adding an extra "for cycle". But the computer cries again: "Time limit exceeded!"

Instead of going nuts, John makes a radical decision. Enough programming, he says! He decides to take a vacation as a reward for his
hard work.

Being a very energetic guy, John wants to have the time of his life! With so many things to do, it is unfortunately impossible for him to
enjoy them all. So, as soon as he eats his breakfast, he devises a "Fun Plan" in which he describes a schedule of his upcoming
activities:

ID Scheduled Activity Time Span

Monday, 10:00
1 Debug the room PM – Tuesday,
1:00 AM

Tuesday, 6:00
2 Enjoy a trip to Hawaii AM – Saturday,
10:00 PM

Tuesday, 11:00
Win the Chess
3 AM – Tuesday,
Championship
9:00 PM

Tuesday, 7:00
4 Attend the Rock Concert PM – Tuesday,
11:00 PM

Wednesday,
Win the Starcraft 3:00 PM –
5
Tournament Thursday, 3:00
PM

Thursday,
10:00 AM –
6 Have some paintball fun
Thursday, 4:00
PM

Saturday,
Participate in the
12:00 PM –
7 topcoder Single Round
Saturday, 2:00
Match
PM

Saturday, 8:30
 8 Take a shower PM – Saturday
8:45 PM

Saturday, 9:00
Organize a Slumber
9 PM – Sunday,
Party
6:00 AM

Participate in an "All you Saturday, 9:01
10 can eat" and "All you PM – Saturday,
can drink" challenge 11:59 PM

He now wishes to take advantage of as many as he can. Such careful planning requires some cleverness, but his mind has gone on
vacation too. This is John Smith’s problem and he needs our help.

Could we help him have a nice holiday? Maybe we can! But let’s make an assumption first. As John is a meticulous programmer, once
he agrees on something, he sticks to the plan. So, individual activities may either be chosen or not. For each of the two choices
regarding the first activity, we can make another two choices regarding the second. After a short analysis, we find out that we have 2 ^
N possible choices, in our case 1024. Then, we can check each one individually to see whether it abides the time restrictions or not.
From these, finding the choice with the most activities selected should be trivial. There are quite a lot of alternatives, so John would
need to enlist the help of his tired computer. But what happens if we have 50 activities? Even with the most powerful computer in the
world, handling this situation would literally take years. So, this approach is clearly not feasible.

Let’s simply the problem and trust our basic instinct for a moment. A good approach may be to take the chance as the first opportunity
arises. That is, if we have two activities we can follow and they clash, we choose the one that starts earlier in order to save some time.
In this case John will start his first evening by debugging his room. Early the next morning, he has a plane to catch. It is less than a
day, and he has already started the second activity. This is great! Actually, the best choice for now. But what happens next? Spending
5 days in Hawaii is time consuming and by Saturday evening, he will still have only two activities performed. Think of all the activities
he could have done during this five day span! Although very fast and simple, this approach is unfortunately not accurate.

We still don’t want to check for every possible solution, so let’s try another trick. Committing to such a time intensive activity like the
exotic trip to Hawaii can simply be avoided by selecting first the activity which takes the least amount of time and then continuing this
process for the remaining activities that are compatible with those already selected. According to the previous schedule, first of all we
choose the shower. With only 15 minutes consumed, this is by far the best local choice. What we would like to know is whether we
can still keep this "local best" as the other compatible activities are being selected. John’s schedule will look like this:

Take a shower (15 minutes)
Participate in the topcoder Single Round Match (2 hours)
Participate in an "All you can eat" and "All you can drink" challenge (2 hours 58 minutes)
Debug the room (3 hours)
Attend the Rock Concert (4 hours)
Have some paintball fun (6 hours)

Out of the 10 possible activities, we were able to select 6 (which is not so bad). We now run the slow but trustworthy algorithm to see if
this is actually the best choice we can make. And the answer is indeed 6. John is very appreciative for our help, but once he returns
from the holiday, confident in our ingenious approach, he may face a serious problem:

By going for the short date, he misses both the school exam and the match of his favorite team. Being the topcoders that we are, we
must get used to writing reliable programs. A single case which we cannot handle dooms this approach to failure.

What we generally have to do in situations like this is to analyze what might have caused the error in the first place and act accordingly
to avoid it in the future. Let’s look again at the previous scenario. The dating activity clashes with both the exam and the match, while
the other two only clash with the date. So, the idea almost comes from itself. Why not always select the activity that produces the
minimum amount of clashes with the remaining activities? Seems logical – it all makes sense now! We’ll try to prove that this approach
is indeed correct. Suppose we have already selected an activity X and try to check if we could have selected two activities A and B that
clash with X instead. A and B should of course not clash, otherwise the final result will not improve. But now, we are back to the
previous case (X has two clashes, while A and B have only one). If this is the case, A and B are selected from the beginning. The only
way to disprove our assumption is to make A and B clash more, without affecting other activities except X. This is not very intuitive, but
if we think it through we can (unfortunately) build such a case:

The activities represented by the blue lines are the optimal choice given the above schedule. But as the activity in red produces only 2
clashes, it will be chosen first. There are 4 compatible activities left before, but they all clash with each other, so we can only select one.
The same happens for the activities scheduled after, leaving space for only one more choice. This only gives us 3 activities, while the
optimum choice selects 4.

So far, every solution we came up with had a hidden flaw. It seems we have to deal with a devilish problem. Actually, this problem has
quite an elegant and straightforward solution. If we study the figure above more carefully, we see that the blue activity on the bottom­
left is the only one which finishes before the "timeline" indicated by the thin vertical bar. So, if we are to choose a single activity,
choosing the one that ends first (at a time t1), will leave all the remaining time interval free for choosing other activities. If we choose
any other activity instead, the remaining time interval will be shorter. This is obvious, because we will end up anyway with only one
activity chosen, but at a time t2 > t1. In the first case we had available all the time span between t1 and finish and that included the
time between t2 and finish. Consequently, there is no disadvantage in choosing the activity that finishes earlier. The advantage may
result in the situation when we are able to insert another activity that starts between t1 and t2 and ends up before the end of any
activity that starts after time t2.
Known as the "Activity Selection", this is a standard problem that can be solved by the Greedy Method. As a greedy man takes as
much as he can as often as he can, in our case we are choosing at every step the activity that finishes first and do so every time there
is no activity in progress. The truth is we all make greedy decisions at some point in our life. When we go shopping or when we drive a
car, we make choices that seem best for the moment. Actually, there are two basic ingredients every greedy algorithm has in common:

Greedy Choice Property: from a local optimum we can reach a global optimum, without having to reconsider the decisions
already taken.
Optimal Substructure Property: the optimal solution to a problem can be determined from the optimal solutions to its
subproblems.

The following pseudo code describes the optimal activity selection given by the "greedy" algorithm proven earlier:

    Let N denote the number of activities and 
{I} the activity I  ( 1 <= I <= N )
For each {I}, consider S[I] and F[I] its starting and finishing time
Sort the activities in the increasing order of their finishing time
‐ that is, for every I < J we must have F [I] <= F [J]

//  A denotes the set of the activities that will be selected
A = {1}
//  J denotes the last activity selected
J = 1
For I = 2  to N
// we can select activity 'I' only if the last activity 
// selected has already been finished 
If S [I] >= F [J]   
//  select activity 'I' 
A = A + {I}   
// Activity 'I' now becomes the last activity selected 
J = I 
Endif 
Endfor 
    Return A 

After applying the above algorithm, Johnny’s "Fun Plan" would look like this:

Eliminate all the bugs and take some time to rest
Tuesday is for chess, prepare to beat them all
A whole day of Starcraft follows, this should be fun
The next two days are for recovery
As for the final day, get a few rating points on topcoder, take a shower and enjoy the versatile food and the good quality wine

The problem of John Smith is solved, but this is just one example of what Greedy can do. A few examples of real topcoder problems will
help you understand the concept better. But before moving on, you may wish to practice a little bit more what you have read so far on
a problem similar with the Activity Selection, named Boxing.

BioScore
In this problem you are asked to maximize the average homology score for all the pairs in the set. As an optimal solution is required,
this may be a valuable clue in determining the appropriate method we can use. Usually, this kind of problems can be solved by dynamic
programming, but in many cases a Greedy strategy could also be employed.

The first thing we have to do here is to build the frequency matrix. This is an easy task as you just have to compare every pair of
two sequences and count the occurrences of all the combinations of nucleic acids (AA, AC, AG, AT, CA, CC, CG, CT, GA, GC, GG, GT, TA,
TC, TG, TT). Each of these combinations will be an element in the matrix and its value will represent the total number of occurrences.
For example, let’s take the set { "ACTAGAGAC", "AAAAAAAAA", "TAGTCATAC", "GCAGCATTC" } used in Example 2. 
In the bottom­right part of the figure above, you can see the resulting frequency matrix. Let us denote it by F What we have to do from
now is to find another matrix S such that the sum of the 16 corresponding products of the type F[I,J] * S[I,J] (1 <= I,J <= 4) is
maximized.

Now, let’s look at the matrix restrictions and analyze them one by one:

1) The sum of the 16 entries must be 0.

This is more like a commonsense condition. With all the elements in F positive, the final score tends to increase as we increase the
elements in S. But because the sum must be kept at 0, in order to increase an element, we’ll have to decrease others. The challenge of
this problem resides in finding the optimal distribution.

2) All entries must be integers between ­10 and 10 inclusive

Another commonsense condition! Our search space has been drastically reduced, but we are still left with a lot of alternatives.

3) It must be symmetric ( score(x,y) = score(y,x) )

Because of the symmetry, we must attribute the same homology score to combinations like "AC" and "CA". As a result, we can also
count their occurrences together. For the previous example, we have the set of combinations with the following frequencies:

AA: 14 CC: 3 GG: 0 TT: 1

AC + CA: AG + GA: AT + TA:

11 10 10

CG + GC: 2 CT + TC: 0

GT + TG: 3

An intuitive approach would be to assign a higher homology score to the combinations that appear more often. But as we must keep
the score sum to 0, another problem arises. Combinations like AA, CC, GG and TT appear only once in the matrix. So, their homology
score contribute less to the total sum.

4) Diagonal entries must be positive ( score(x,x)>0 )

This restriction differentiates the elements on the diagonal from the others even further. Basically, we have two groups: the four
elements on the diagonal (which correspond to the combinations AA, CC, GG and TT) and the six elements not on the diagonal (which
correspond to the combinations AC + CA, AG + GA, AT + TA, CG + GC, CT + TC and GT +TG). Each of these groups can have different
states, depending on the value we assign to their elements.

To make things easier, for each possible state in the first group we wish to find an optimal state for the second group. As all
the elements in the second group have the same property, we will try to find their optimal state by using a Greedy approach. But
because the elements in the first group can take any values between 1 and 10, the sum we wish to obtain for the scores we choose in
the second group has to be recalculated. It’s easy to notice that the sum of the elements in the first group can range anywhere
between 4 and 40. As a result, depending on the choice we make for the first group, we’ll have to obtain a sum between ­2 and ­20 for
the second (we shall not forget that the symmetrical elements in the matrix have been coupled together, thus they count twice in the
score matrix).

Now, we have finally reached to the problem core. The solution to the entire problem depends on finding the optimal choice for the
scores in the second group. If the problem has indeed the greedy choice property and the optimal substructure property, we’ll be
able to pick one element form the group, assign it the best scenario and proceed with the remaining elements in the same manner.

Claim: If we always give the highest possible score to the combination that has the most occurrences in the group, we’ll
obtain in the end the highest possible score for the entire group.

The first thing we have to do is to sort these six elements in matrix F. Then, we have to actually compute the corresponding score
values in S. As the total score we should obtain is at least ­20, one quick insight tells us that the first two elements could be given a
score of 10 (if we assign ­10 to all the remaining four elements, ­20 can still be achieved). We know as well that the final score is less
than 0. Because we want to maximize the scores for the first elements, the last three elements can only be ­10 (in the best case the
score sum of the elements is ­2 and then, we assign scores in the following manner: [10, 10, 8, ­10, ­10, ­10]). Finally, the value of the
third element will depend on the choices we make for the first group. From the maximum of 10, we subtract half of the score sum of
the elements in the first group (we should note here that the aforementioned sum must be even).

Now, we have to make sure that our approach is indeed correct. The proof is quite straightforward, as in order keep the sum in S
constant we can only decrease from the score of a combination with more occurrences and increase to the score of a combination with
fewer occurrences. Let f1 and f2 be the frequencies of the two combinations and f1 >= f2. We have f1 * s1 + f2 * s2 = X, where X is
the sum we should maximize. By our greedy assumption, s1 >= s2. As s1 + s2 remains constant, the previous sum changes to: f1*
(s1 – a) + f2*( s2 + a) = Y, where a is strictly greater than 0. We find out that Y – X = a * (f2 – f1). Because f1 >= f2, this difference
will always be less than or equal to 0. It results that Y <= X. As Y was chosen arbitrarily, it can be concluded that the initial greedy
choice always gives the maximum possible score.

We apply the algorithm described above for each state of the elements in the first group and save the best result.

Representation: Instead of using the matrices F and S, we find it more convenient to use arrays for storing both the
combination frequencies and their corresponding score. The first 4 elements of F will denote the frequency of the combinations
AA, CC, GG and TT. The next 6 elements will denote the other possible combinations and are sorted in the decreasing order of their
frequency (F[5] >= F[6] >= F[7] >= F[8] >= F[9] >= F[10]). S will be an array of 10 elements such that S[I] is the score we attribute
to the combination I.

The main algorithm is illustrated in the following pseudo code:

    Best = ‐Infinity 
For S [1] = 1 to 10 
For S [2] = 1 to 10 
For S [3] = 1 to 10 
For S [4] = 1 to 10 
If  (S [1] + S [2] + S [3] + S [4]) mod 2 = 0 
 S [5] = S[6] = 10 
S [7] = 10 ‐ (S [1] + S [2] + S [3] + S[4]) / 2 
S [8] = S [9] = S [10] = ‐10  
//  in Best we save the greatest average homology score 
Best = max (Best , score (F,S))  
// obtained so far. 
Endif 
Endfor 
Endfor 
Endfor 
Endfor 
    Return Best 

Given the score matrix (in our case the array S), we compute the final result by just making the sum of the products of the form F[I] *
S[I] ( 1 <= I <=10) and divide it by N * (N­1) / 2 in order to obtain the average homology score.

GoldMine
We are now going to see how a gold mine can be exploited to its fullest, by being greedy. Whenever we notice the maximum profit is
involved, a greedy switch should activate. In this case, we must allocate all the miners to the available mines, such that the total profit
is maximized. After a short analysis, we realize that we want to know how much money can be earned from a mine in all the possible
cases. And there are not so many cases, as in each mine we can only have between 0 and 6 workers. The table below represents the
possible earnings for the two mines described in the example 0 of the problem statement:

0 workers 1 worker 2 workers 3 workers 4 workers 5 workers 6 workers

First mine 0 57 87 87 67 47 27

Second mine 0 52 66 75 75 66 48

As we are going to assign workers to different mines, we may be interested in the profit a certain worker can bring to the mine he was
assigned. This can be easily determined, as we compute the difference between the earnings resulted from a mine with the worker and
without. If we only had one worker, the optimal choice would have been to allocate him in the mine where he can bring the best
profit. But as we have more workers, we want to check if assigning them in the same manner would bring the best global profit.

In our example we have 4 workers that must be assigned. The table below shows the profit obtained in the two mines for each
additional worker.

Initially Worker 1 Worker 2 Worker 3 Worker 4 Worker 5 Worker 6

First mine ­ 57 30 0 ­20 ­20 ­20

Second mine ­ 52 14 9 0 ­9 ­20

We notice that the first mine increases its profit by 57 if we add a worker, while the second by only 52. So, we allocate the first worker
to the first mine.

Initially Worker 1 Worker 2 Worker 3 Worker 4 Worker 5 Worker 6

First mine ­ 57 30 0 ­20 ­20 ­20

Second mine ­ 52 14 9 0 ­9 ­20

Now, an additional worker assigned to the first mine would only increase its profit by 30. We put him in the second, where the profit
can be increased by 52.

Initially Worker 1 Worker 2 Worker 3 Worker 4 Worker 5 Worker 6

First mine ­ 57 30 0 ­20 ­20 ­20

Second mine ­ 52 14 9 0 ­9 ­20

The third miner would be more useful to the first mine as he can bring a profit of 30.

Initially Worker 1 Worker 2 Worker 3 Worker 4 Worker 5 Worker 6

First mine ­ 57 30 0 ­20 ­20 ­20

Second mine ­ 52 14 9 0 ­9 ­20

As for the last miner, we can either place him in the first mine (for a zero profit) or in the second (for a profit of 14). Obviously, we
assign him to the second.

Initially Worker 1 Worker 2 Worker 3 Worker 4 Worker 5 Worker 6

First mine ­ 57 30 0 ­20 ­20 ­20

Second mine ­ 52 14 9 0 ­9 ­20

In the end two of the workers have been allocated to the first mine and another two to the second. The example shows us that this is
indeed the choice with the best total profit. But will our "greedy" approach always work?

Claim: We obtain the maximum total profit when we assign the workers one by one to the mine where they can bring the
best immediate profit.
Proof: Let A and B be two mines and a1, a2, b1, b2 be defined as below:
a1 – the profit obtained when an additional worker is assigned to mine A
a1 + a2 – the profit obtained when two additional workers are assigned to mine A
b1 – the profit obtained when an additional worker is assigned to mine B
b1 + b2 – the profit obtained when two additional workers are assigned to mine B
Let us now consider that we have two workers to assign and a1 >= b1.

Our greedy algorithm will increase the profit by a1 for the first worker and by max (a2, b1) for the second worker. The total profit in
this case is a1+max(a2,b1). If we were to choose the profit b1 for the first worker instead, the alternatives for the second worker
would be a profit of a1 or a profit of b2.

In the first case, the total profit would be b1+a1 <= a1 + max (a2,b1).
In the second case, the total profit would be b1+b2. We need to prove that b1+b2 <= a1+max(a2,b1). But b2 <= b1 as the profit of
allocating an extra worker to a mine is always higher or equal with the profit of allocating the next extra worker to that
mine.

Gold Mine Status Profit from extra­worker 1 Profit from extra­worker 2

number of ores > number of workers + 2 60 60

number of ores = number of workers + 2 60 50

number of ores = number of workers + 1 50 ­20

number of ores < number of workers + 1 ­20 ­20

As b1+b2 <= a1+b2 <= a1+b1 <= a1+max(a2,b1), the greedy choice is indeed the best .

Coding this is not difficult, but one has to take into account the problem constraints (all miners must be placed, there are at most six
workers in a mine and if a worker can be optimally assigned to more than one mine, put him in the mine with the lowest index).

WorldPeace
The greedy algorithms we have seen so far work well in every possible situation as their correction has been proven. But there is
another class of optimization problems where Greedy Algorithms have found their applicability. This category mostly includes NP­
complete problems (like the Traveling Salesman Problem) and here, one may prefer to write an heuristic based on a greedy algorithm
than to wait … The solution is not always the best, but for most real purposes, it is good enough. While this problem is not NP, it is an
excellent example of how a simple greedy algorithm can be adapted to fool not only the examples, but also the carefully designed
system tests. Such an algorithm is not very hard to come with and after a short analysis we notice that in order to maximize the total
number of groups it is always optimal to form a group from the k countries that have the highest number of citizens. We
apply this principle at every single step and then sort the sequence again to see which are the next k countries having the highest
number of citizens. This idea is illustrated in the following pseudo code:

    Groups = 0 
    Repeat  
//sorts the array in decreasing order 
Sort (A) 
Min= A[K] 
If Min > 0 Groups = Groups + 1 
For I = 1 to K 
A[I] = A[I] ‐ 1 
Endfor
    Until  Min = 0
    Return Groups 

Unfortunately, a country can have up to a billion citizens, so we cannot afford to make only one group at a time. Theoretically, for a
given set of k countries, we can make groups until all the citizens in one of these countries have been grouped. And this can be done in
a single step:

    Groups = 0 
    Repeat  
// sorts the array in decreasing order 
Sort (A) 
Min= A[K] 
Groups = Groups + Min 
For I = 1 to K 
A[I] = A[I] ‐ Min 
Endfor 
    Until  Min = 0
    Return Groups 

The execution time is no longer a problem, but it is the algorithm! As we check it on the example 0, our method returns 4 instead of 5.
The result returned for the examples 1, 2 and 3 is correct. As for the last example, instead of making 3983180234 groups, we are able
to make 3983180207. Taking into account the small difference, we may say that our solution is pretty good, so maybe we can refine it
more on this direction.

So far, we have two algorithms:

a first greedy algorithm that is accurate, but not fast enough
a second greedy algorithm that is fast, but not very accurate.

What we want to do is to optimize accuracy as much as we can, without exceeding the execution time limit. Basically, we are looking for
a truce between speed and accuracy. The only difference in the two algorithms described above is the number of groups we select
at a given time. The compromise we will make is to select an arbitrarily large number of groups in the beginning, and as we approach
the end to start being more cautious. When we are left with just a few ungrouped citizens in every country, it makes complete sense to
use the safe brute force approach. In the variable Allowance defined in the algorithm below, we control the number of groups we want
to make at a given moment.
    Groups = 0 
    Repeat  
// sorts the array in decreasing order 
Sort (A) 
Min= A[K] 
Allowance = (Min+999) / 1000 
Groups = Groups + Allowance 
For I = 1 to K 
A[I] = A[I] ‐ Allowance 
Endfor 
    Until  Min = 0
    Return Groups 

If this approach is correct indeed, remains to be seen. Despite the fact it escaped both Tomek’s keen eyes and system tests, it is very
likely that the result is not optimal for all the set of possible test cases. This was just an example to show that a carefully chosen
refinement on a simple (but obvious faulty) greedy approach can actually be the "right" way. For more accurate solutions to this
problem, see the Match Editorial.

Conclusion
Greedy algorithms are usually easy to think of, easy to implement and run fast. Proving their correctness may require rigorous
mathematical proofs and is sometimes insidious hard. In addition, greedy algorithms are infamous for being tricky. Missing even a very
small detail can be fatal. But when you have nothing else at your disposal, they may be the only salvation. With backtracking or
dynamic programming you are on a relatively safe ground. With greedy instead, it is more like walking on a mined field. Everything
looks fine on the surface, but the hidden part may backfire on you when you least expect. While there are some standardized problems,
most of the problems solvable by this method call for heuristics. There is no general template on how to apply the greedy method to a
given problem, however the problem specification might give you a good insight. Advanced mathematical concepts such as matroids
may give you a recipe for proving that a class of problems can be solved with greedy, but it ultimately comes down to the keen sense
and experience of the programmer. In some cases there are a lot of greedy assumptions one can make, but only few of them are
correct (see the Activity Selection Problem). In other cases, a hard problem may hide an ingenious greedy shortcut, like there was the
case in the last problem discussed, WorldPeace. And this is actually the whole beauty of greedy algorithms! Needless to say, they can
provide excellent challenge opportunities…

A few final notes

a problem that seems extremely complicated on the surface (see TCSocks) might signal a greedy approach.
problems with a very large input size (such that a n^2 algorithm is not fast enough) are also more likely to be solved by greedy
than by backtracking or dynamic programming.
despite the rigor behind them, you should look to the greedy approaches through the eyes of a detective, not with the glasses of a
mathematician.

A good detective Greedy and lucky Greedy and not so lucky

in addition, study some of the standard greedy algorithms to grasp the concept better (Fractional Knapsack Problem, Prim
Algorithm, Kruskal Algorithm, Dijkstra Algorithm, Huffman Coding, Optimal Merging, Topological Sort).

Further Problems
Level 1
GroceryBagger – SRM 222
FanFailure – SRM 195
PlayGame – SRM 217
SchoolAssembly – TCO04 Round 2
RockStar – SRM 216
Apothecary – SRM 204
Boxing – TCO04 Round 3
Unblur – TCO04 Semifinal Room 3

Level 2
Crossroads – SRM 217
TCSocks – SRM 207
HeatDeath – TCO04 Round 4
BioScore – TCO04 Semifinal Room 1
Rationalization – SRM 224

Level 3
GoldMine – SRM 169
MLBRecord – TCO04 Round 2
RearrangeFurniture – SRM 220
WorldPeace – SRM 204

Dynamic Programming – From Novice to Advanced
By Dumitru — topcoder member
Discuss this article in the forums
An important part of given problems can be solved with the help of dynamic programming (DP for short). Being able to tackle problems
of this type would greatly increase your skill. I will try to help you in understanding how to solve problems using DP. The article is based
on examples, because a raw theory is very hard to understand.

Note: If you’re bored reading one section and you already know what’s being discussed in it – skip it and go to the next one.

Introduction (Beginner)

What is a dynamic programming, how can it be described?

A DP is an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states. A sub­solution of the
problem is constructed from previously found ones. DP solutions have a polynomial complexity which assures a much faster running
time than other techniques like backtracking, brute­force etc.

Now let’s see the base of DP with the help of an example:

Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we
can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way that they sum up to S.

Now let’s start constructing a DP solution:

First of all we need to find a state for which an optimal solution is found and with the help of which we can find the optimal solution for
the next state.

What does a "state" stand for?

It’s a way to describe a situation, a sub­solution for the problem. For example a state would be the solution for sum i, where i=S. A
smaller state than state i would be the solution for any sum j, where j<i. For finding a state i, we need to first find all smaller states j
(j<i) . Having found the minimum number of coins which sum up to i, we can easily find the next state – the solution for i+1.

How can we find it?

It is simple – for each coin j, Vj=i, look at the minimum number of coins found for the i­Vjsum (we have already found it previously).
Let this number be m. If m+1 is less than the minimum number of coins already found for current sum i, then we write the new result
for it.

For a better understanding let’s take this example:
Given coins with values 1, 3, and 5.
And the sum S is set to be 11.

First of all we mark that for state 0 (sum 0) we have found a solution with a minimum number of 0 coins. We then go to sum 1. First,
we mark that we haven’t yet found a solution for this one (a value of Infinity would be fine). Then we see that only coin 1 is less than
or equal to the current sum. Analyzing it, we see that for sum 1­V1= 0 we have a solution with 0 coins. Because we add one coin to
this solution, we’ll have a solution with 1 coin for sum 1. It’s the only solution yet found for this sum. We write (save) it. Then we
proceed to the next state – sum 2. We again see that the only coin which is less or equal to this sum is the first coin, having a value of
1. The optimal solution found for sum (2­1) = 1 is coin 1. This coin 1 plus the first coin will sum up to 2, and thus make a sum of 2 with
the help of only 2 coins. This is the best and only solution for sum 2. Now we proceed to sum 3. We now have 2 coins which are to be
analyzed – first and second one, having values of 1 and 3. Let’s see the first one. There exists a solution for sum 2 (3 – 1) and
therefore we can construct from it a solution for sum 3 by adding the first coin to it. Because the best solution for sum 2 that we found
has 2 coins, the new solution for sum 3 will have 3 coins. Now let’s take the second coin with value equal to 3. The sum for which this
coin needs to be added to make 3 , is 0. We know that sum 0 is made up of 0 coins. Thus we can make a sum of 3 with only one coin –
3. We see that it’s better than the previous found solution for sum 3 , which was composed of 3 coins. We update it and mark it as
having only 1 coin. The same we do for sum 4, and get a solution of 2 coins – 1+3. And so on.

Pseudocode:

    Set Min[i] equal to Infinity for all of i 
    Min[0]=0 

    For i = 1 to S
For j = 0 to N ‐ 1 
If (Vj<=i AND Min[i‐Vj]+1<Min[i]) 
Then Min[i]=Min[i‐Vj]+1 

    Output Min[S] 

Here are the solutions found for all sums:

Coin value added to a smaller sum to
Sum Min. nr. of coins
obtain this sum (it is displayed in brackets)
0 0 ­
1 1 1 (0)
2 2 1 (1)
3 1 3 (0)
4 2 1 (3)
5 1 5 (0)
6 2 3 (3)
7 3 1 (6)
8 2 3 (5)
9 3 1 (8)
 10 2 5 (5)
11 3 1 (10)

As a result we have found a solution of 3 coins which sum up to 11.

Additionally, by tracking data about how we got to a certain sum from a previous one, we can find what coins were used in building it.
For example: to sum 11 we got by adding the coin with value 1 to a sum of 10. To sum 10 we got from 5. To 5 – from 0. This way we
find the coins used: 1, 5 and 5.

Having understood the basic way a DP is used, we may now see a slightly different approach to it. It involves the change (update) of
best solution yet found for a sum i, whenever a better solution for this sum was found. In this case the states aren’t calculated
consecutively. Let’s consider the problem above. Start with having a solution of 0 coins for sum 0. Now let’s try to add first coin (with
value 1) to all sums already found. If the resulting sum t will be composed of fewer coins than the one previously found – we’ll update
the solution for it. Then we do the same thing for the second coin, third coin, and so on for the rest of them. For example, we first add
coin 1 to sum 0 and get sum 1. Because we haven’t yet found a possible way to make a sum of 1 – this is the best solution yet found,
and we mark S[1]=1. By adding the same coin to sum 1, we’ll get sum 2, thus making S[2]=2. And so on for the first coin. After the
first coin is processed, take coin 2 (having a value of 3) and consecutively try to add it to each of the sums already found. Adding it to
0, a sum 3 made up of 1 coin will result. Till now, S[3] has been equal to 3, thus the new solution is better than the previously found
one. We update it and mark S[3]=1. After adding the same coin to sum 1, we’ll get a sum 4 composed of 2 coins. Previously we found
a sum of 4 composed of 4 coins; having now found a better solution we update S[4] to 2. The same thing is done for next sums – each
time a better solution is found, the results are updated.

Elementary

To this point, very simple examples have been discussed. Now let’s see how to find a way for passing from one state to another, for
harder problems. For that we will introduce a new term called recurrent relation, which makes a connection between a lower and a
greater state.

Let’s see how it works:

Given a sequence of N numbers – A[1] , A[2] , …, A[N] . Find the length of the longest non­decreasing sequence.

As described above we must first find how to define a "state" which represents a sub­problem and thus we have to find a solution for it.
Note that in most cases the states rely on lower states and are independent from greater states.

Let’s define a state i as being the longest non­decreasing sequence which has its last number A[i] . This state carries only data about
the length of this sequence. Note that for i<j the state i is independent from j, i.e. doesn’t change when we calculate state j. Let’s see
now how these states are connected to each other. Having found the solutions for all states lower than i, we may now look for state i.
At first we initialize it with a solution of 1, which consists only of the i­th number itself. Now for each j<i let’s see if it’s possible to pass
from it to state i. This is possible only when A[j]=A[i] , thus keeping (assuring) the sequence non­decreasing. So if S[j] (the solution
found for state j) + 1 (number A[i] added to this sequence which ends with number A[j] ) is better than a solution found for i (ie.
S[j]+1>S[i] ), we make S[i]=S[j]+1. This way we consecutively find the best solutions for each i, until last state N.

Let’s see what happens for a randomly generated sequence: 5, 3, 4, 8, 6, 7:

The length of the longest The last sequence i from
I non­decreasing sequence which we "arrived"
of first i numbers to this one
1 1 1 (first number itself)
2 (second number
2 1
itself)
3 2 2
4 3 3
5 3 3
6 4 5

Practice problem:
Given an undirected graph G having N (1<N<=1000) vertices and positive weights. Find the shortest path from vertex 1 to vertex N, or
state that such path doesn’t exist.

Hint: At each step, among the vertices which weren’t yet checked and for which a path from vertex 1 was found, take the one which
has the shortest path, from vertex 1 to it, yet found.

Try to solve the following problems from topcoder competitions:

ZigZag – 2003 TCCC Semifinals 3
BadNeighbors – 2004 TCCC Round 4
FlowerGarden – 2004 TCCC Round 1

Intermediate

Let’s see now how to tackle bi­dimensional DP problems.

Problem:
A table composed of N x M cells, each having a certain quantity of apples, is given. You start from the upper­left corner. At each step
you can go down or right one cell. Find the maximum number of apples you can collect.

This problem is solved in the same way as other DP problems; there is almost no difference.

First of all we have to find a state. The first thing that must be observed is that there are at most 2 ways we can come to a cell – from
the left (if it’s not situated on the first column) and from the top (if it’s not situated on the most upper row). Thus to find the best
solution for that cell, we have to have already found the best solutions for all of the cells from which we can arrive to the current cell.

From above, a recurrent relation can be easily obtained:
S[i][j]=A[i][j] + max(S[i­1][j], if i>0 ; S[i][j­1], if j>0) (where i represents the row and j the column of the table , its left­upper
corner having coordinates {0,0} ; and A[i][j] being the number of apples situated in cell i,j).

S[i][j] must be calculated by going first from left to right in each row and process the rows from top to bottom, or by going first from
top to bottom in each column and process the columns from left to right.

Pseudocode:

    For i = 0 to N ‐ 1 
For j = 0 to M ‐ 1 
S[i][j] = A[i][j] + 
max(S[i][j‐1], if j>0 ; S[i‐1][j], if i>0 ; 0) 

    Output S[n‐1][m‐1] 

Here are a few problems, from topcoder Competitions, for practicing:

AvoidRoads – 2003 TCO Semifinals 4
ChessMetric – 2003 TCCC Round 4

Upper­Intermediate

This section will discuss about dealing DP problems which have an additional condition besides the values that must be calculated.

As a good example would serve the following problem:

Given an undirected graph G having positive weights and N vertices.

You start with having a sum of M money. For passing through a vertex i, you must pay S[i] money. If you don’t have enough money –
you can’t pass through that vertex. Find the shortest path from vertex 1 to vertex N, respecting the above conditions; or state that
such path doesn’t exist. If there exist more than one path having the same length, then output the cheapest one. Restrictions:
1<N<=100 ; 0<=M<=100 ; for each i, 0<=S[i]<=100. As we can see, this is the same as the classical Dijkstra problem (finding the
shortest path between two vertices), with the exception that it has a condition. In the classical Dijkstra problem we would have used a
uni­dimensional array Min[i] , which marks the length of the shortest path found to vertex i. However in this problem we should also
keep information about the money we have. Thus it would be reasonable to extend the array to something like Min[i][j] , which
represents the length of the shortest path found to vertex i, with j money being left. In this way the problem is reduced to the original
path­finding algorithm. At each step we find the unmarked state (i,j) for which the shortest path was found. We mark it as visited (not
to use it later), and for each of its neighbors we look if the shortest path to it may be improved. If so – then update it. We repeat this
step until there will remain no unmarked state to which a path was found. The solution will be represented by Min[N­1][j] having the
least value (and the greatest j possible among the states having the same value, i.e. the shortest paths to which has the same length).

Pseudocode:

    Set states(i,j) as unvisited for all (i,j) 
    Set Min[i][j] to Infinity for all (i,j) 

    Min[0][M]=0 

    While(TRUE) 

Among all unvisited states(i,j) find the one for which Min[i][j] 
is the smallest. Let this state found be (k,l). 

If there wasn't found any state (k,l) for which Min[k][l] is 
less than Infinity ‐ exit While loop. 

Mark state(k,l) as visited 

For All Neighbors p of Vertex k. 
If (l‐S[p]>=0 AND 
Min[p][l‐S[p]]>Min[k][l]+Dist[k][p]) 
Then Min[p][l‐S[p]]=Min[k][l]+Dist[k][p] 
i.e.
If for state(i,j) there are enough money left for
going to vertex p (l‐S[p] represents the money that
will remain after passing to vertex p), and the
shortest path found for state(p,l‐S[p]) is bigger
than [the shortest path found for
state(k,l)] + [distance from vertex k to vertex p)],
then set the shortest path for state(i,j) to be equal
to this sum.
End For 

    End While 

    Find the smallest number among Min[N‐1][j] (for all j, 0<=j<=M); 
    if there are more than one such states, then take the one with greater 
j. If there are no states(N‐1,j) with value less than Infinity ‐ then
such a path doesn't exist.

Here are a few TC problems for practicing:

Jewelry – 2003 TCO Online Round 4
StripePainter – SRM 150 Div 1
 QuickSums – SRM 197 Div 2
ShortPalindromes – SRM 165 Div 2

Advanced

The following problems will need some good observations in order to reduce them to a dynamic solution.

Problem StarAdventure – SRM 208 Div 1:

Given a matrix with M rows and N columns (N x M). In each cell there’s a number of apples.
You start from the upper­left corner of the matrix. You can go down or right one cell. You need to arrive to the bottom­right corner.
Then you need to go back to the upper­left cell by going each step one cell left or up. Having arrived at this upper­left cell, you need to
go again back to the bottom­right cell.
Find the maximum number of apples you can collect.
When you pass through a cell – you collect all the apples left there.

Restrictions: 1 < N, M <= 50 ; each cell contains between 0 and 1000 apples inclusive.

First of all we observe that this problem resembles to the classical one (described in Section 3 of this article), in which you need to go
only once from the top­left cell to the bottom­right one, collecting the maximum possible number of apples. It would be better to try to
reduce the problem to this one. Take a good look into the statement of the problem – what can be reduced or modified in a certain way
to make it possible to solve using DP? First observation is that we can consider the second path (going from bottom­right cell to the
top­left cell) as a path which goes from top­left to bottom­right cell. It makes no difference, because a path passed from bottom to top,
may be passed from top to bottom just in reverse order. In this way we get three paths going from top to bottom. This somehow
decreases the difficulty of the problem. We can consider these 3 paths as left, middle and right. When 2 paths intersect (like in the
figure below)

we may consider them as in the following picture, without affecting the result:

This way we’ll get 3 paths, which we may consider as being one left, one middle and the other – right. More than that, we may see that
for getting an optimal results they must not intersect (except in the leftmost upper corner and rightmost bottom corner). So for each
row y (except first and last), the x coordinates of the lines (x1[y] , x2[y] and respectively x3[y] ) will be : x1[y] < x2[y] < x3[y] .
Having done that – the DP solution now becomes much clearer. Let’s consider the row y. Now suppose that for any configuration of
x1[y­1] , x2[y­1] and x3[y­1] we have already found the paths which collect the maximum number of apples. From them we can
find the optimal solution for row y. We now have to find only the way for passing from one row to the next one. Let Max[i][j][k]
represent the maximum number of apples collected till row y­1 inclusive, with three paths finishing at column i, j, and respectively k.
For the next row y, add to each Max[i][j][k] (obtained previously) the number of apples situated in cells (y,i) , (y,j) and (y,k). Thus
we move down at each step. After we made such a move, we must consider that the paths may move in a row to the right. For keeping
the paths out of an intersection, we must first consider the move to the right of the left path, after this of the middle path, and then of
the right path. For a better understanding think about the move to the right of the left path – take every possible pair of, k (where
j<k), and for each i (1 i<j) consider the move from position (i­1,j,k) to position (i,j,k). Having done this for the left path, start
processing the middle one, which is done similarly; and then process the right path.

TC problems for practicing:

MiniPaint – SRM 178 Div 1

Additional Note:

When have read the description of a problem and started to solve it, first look at its restrictions. If a polynomial­time algorithm should
be developed, then it’s possible that the solution may be of DP type. In this case try to see if there exist such states (sub­solutions)
with the help of which the next states (sub­solutions) may be found. Having found that – think about how to pass from one state to
another. If it seems to be a DP problem, but you can’t define such states, then try to reduce the problem to another one (like in the
example above, from Section 5).

Mentioned in this writeup:
TCCC ’03 Semifinals 3 Div I Easy – ZigZag
TCCC ’04 Round 4 Div I Easy – BadNeighbors
TCCC ’04 Round 1 Div I Med – FlowerGarden
TCO ’03 Semifinals 4 Div I Easy – AvoidRoads
TCCC ’03 Round 4 Div I Easy – ChessMetric
TCO ’03 Round 4 Div I Med – Jewelry
SRM 150 Div I Med – StripePainter
SRM 197 Div II Hard – QuickSums
SRM 165 Div II Hard – ShortPalindromes
SRM 208 Div I Hard – StarAdventure
SRM 178 Div I Hard – MiniPaint
Computational Complexity: Section 1
By misof — topcoder member
Discuss this article in the forums

In this article I’ll try to introduce you to the area of computation complexity. The article will be a bit long before we get to the actual
formal definitions because I feel that the rationale behind these definitions needs to be explained as well – and that understanding the
rationale is even more important than the definitions alone.

Why is it important?

Example 1. Suppose you were assigned to write a program to process some records your company receives from time to time. You
implemented two different algorithms and tested them on several sets of test data. The processing times you obtained are in Table 1.

# of
10 20 50 100 1000 5000
records

algorithm 1 0.00s 0.01s 0.05s 0.47s 23.92s 47min

algorithm 2 0.05s 0.05s 0.06s 0.11s 0.78s 14.22s

Table 1. Runtimes of two fictional algorithms.

In praxis, we probably could tell which of the two implementations is better for us (as we usually can estimate the amount of data we
will have to process). For the company this solution may be fine. But from the programmer’s point of view, it would be much better if
he could estimate the values in Table 1 before writing the actual code – then he could only implement the better algorithm.

The same situation occurs during programming challenges: The size of the input data is given in the problem statement. Suppose I
found an algorithm. Questions I have to answer before I start to type should be: Is my algorithm worth implementing? Will it solve the
largest test cases in time? If I know more algorithms solving the problem, which of them shall I