Sub-problems
Abstraction
http://web.mit.edu/6.005/www/fa15/classes/10-recursion/#choosing_the_right_recursive_subproblem
Think about several ways to break down the problem, and try to write the recursive steps. You want to find the one that produces the simplest, most natural recursive step.
https://www.topcoder.com/community/competitive-programming/tutorials/how-to-find-a-solution/
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.
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.
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.
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.
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.
Abstraction
http://web.mit.edu/6.005/www/fa15/classes/10-recursion/#choosing_the_right_recursive_subproblem
Think about several ways to break down the problem, and try to write the recursive steps. You want to find the one that produces the simplest, most natural recursive step.
https://www.topcoder.com/community/competitive-programming/tutorials/how-to-find-a-solution/
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.
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.
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.
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:
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).
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).
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.
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.
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):
- Every possible configuration (subset) of items. These configurations should respect some given rules.
- 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
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.
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.
