Tutorial 2006-09-02

From FeitWiki

Pizza sponsor

Subjects:	Network flow and brute force
Responsible:	Nils
Time:	2006-09-02 12:00
Place:	P15-324

1 Program
2 Network flow
- 2.1 Optimizations
- 2.2 Problems
3 Brute force

[edit]

Program

For those who do not know basic network flow, I will go through my intuitive understanding of the Ford Fulkerson variants.
TopCoder tutorial on maximum flow problems
Selected flow problems.
You read about brute force problems below.
(Selected brute force problems?)

[edit]

Network flow

Go through the max flow tutorial on TopCoder, get an account, and do the problems.

To find which contest a problem was part of, choose "Algorithm" --> "Statistics" --> "Problem Archive" in the menu.

Usefull articles on Wikipedia:

Network flow - Theoretical introduction to network flow problems.
Ford-Fulkerson - Simple and general solution.
Edmonds-Karp - How you usually implement Ford-Fulkerson.

[edit]

Optimizations

In most contests, the time limits are set in such a way that minor optimisations are not necessary. But some things could come in handy, if you notice that the input specification is a bit special, or if you are to write real-world software :)

If the graph is very sparse, it might pay off to make edge lists. This brings Edmonds-Karp from $O (V 3 E)$ to its proper $O (V E 2)$ .
In a bipartite matching problem, you get $| V - 2 |$ edges less if you skip the super source and sink, and each augmenting path search is two steps shorter (a lot, if you use BFS). Implementing this is a bit tricky, but trying is a nice exercise. Use an array match (with default value -1) telling who is matched to who (or not matched yet).

[edit]

Problems

Taxi from the training session 2006-04-29. Nobody solved this during the session. It is a rather tough one.

[edit]

Brute force

Brute force solutions are useful when:

It is the only known solution. (NP-hard problems)
The problem input is small enough to use it. Always consider this when reading a problem statement!
You want to check the correctness of another implementation. Do this when writing libraries!

For the brute force problems, there are in general two cases: The subproblems are independent, or they are not. When they are independent, you can often use memoisation or DP to speed up the search for the best solution. See for example the section on matching below.

I recomend that you implement everything below in your own favourite competition programming language (Java, C or C++), and put it in you snippet library. In most competitions (including NCPC), you can bring any written material.

Often you only need to find the cost of the best solution, but sometimes you must also find a minimum solution, all minimum solutions, or the lexicographically smallest minimum solution. If you have time, you should expand your snippets with this. Finding the lexicograpically smallest of the minimum solutions first can often be done by being particular about the order in which you search.

[edit]

Selections

There are $2 n$ ways of selecting a subset of $n$ elements, if you include the empty set.

A selection can be represented by a boolean array, where A[i] = 1 means that element i is selected. Instead of an array of booleans, you can just use the bits in an integer. Traversing all the selections is equals to traversing all numbers from 0 to $2 n$ . A normal integer will usually be enough. To read out bit j, you binary and with 1 << j, and check if the result is non-zero.

# Traverse all 2^n selections
n = 4
# 1 << n == 2**n
for i in xrange(1 << n):
   # read out which bits are set
    A = []
    for j in xrange(n):
        if i & 1 << j:
            A += [j]
    print A

PS: Notice the low precedence of the operators & and | (lower than < and >).

How large an $n$ this is doable for, depends on how much you need to do in each iteration.

Problems where you need to brute in this way are maybe not that common. If you see some problem in which you need to select some elements, optimise some (simple) function on your selection, and have some limitation, you have a 0-1 knapsack problem. If the capacity of your knapsack is $W$ (an integer), and you have $n$ elements, you solve by dynamic programming in $O (W n)$ .

[edit]

Permutations

Going through all $n!$ permutations is useful for Traveling salesman-like problems (TSP). In these problems, you need to determine the cheapest way of visiting $n$ states. You typically have transition costs $C_{i \rightarrow j}$ , and want to find the order $s_1, s_2, \dots, s_n$ which minimises the cost $C_{s_1 \rightarrow s_2} + C_{s_2 \rightarrow s_3} + \dots + C_{s_{n-1} \rightarrow s_n}$ . You could do by traversing all $n!$ permutations of $1,2,\dots,n$ , and remembering a permutation with minimal cost.

How to generate the next permutation of an order $A$ :

Find the rightmost element $A i$ smaller than the one after it ( $A i + 1$ ). If no such element exists, we must have a permutation in the reversed sorted order, which is the last permutation.
Find the rightmost element $A j$ which is larger than $A i$ . The rightmost will be the smallest, if not, we would have found a different $A i$ .
Swap $A i$ and $A j$ , as $A j$ was "next in line" for a position this far left.
Reverse the order of all elements right of position $i$ . These elements were reverse ordered. If not, we would not have found the $A i$ we did. Now we start iterating over the permutations of those elements from the beginning again.

# Generate the next permutation in the the sorted order.
# 
def nextPerm(A):
    n = len(A)
    i = n - 2
    # Find the rightmost element A[i] smaller than the one after it A[i+1]
    while True:
        if i < 0:
            return False
        if A[i] < A[i+1]:
            break 
        i -= 1
    # Find the rightmost element behind A[i] which is larger
    j = n - 1
    while A[i] >= A[j]:
        j -= 1 
    # Swap them, as A[j] is "next in line" for a position this far left
    A[i], A[j] = A[j], A[i]
    # Reverse the order of the elements behind the new A[i]
    p = i + 1
    q = n - 1
    while p < q:
        A[p], A[q] = A[q], A[p]
        p += 1
        q -= 1
    return True
    
A = range(1, 5)
while True:
    print A
    if not nextPerm(A):
        break

TSP can also be solved in $O (n 22 n)$ (less than $O(n \cdot n!)$ . (But I am not familiar with this solution.)

[edit]

Unordered selections of k elements

There are ${n \choose k} = \frac{n!}{(n-k)!k!}$ ways of selecting $k$ out of $n$ elements (when you do not care about their order). This is equivalent to asking in how many different bit vectors of length $n$ have $k$ bits set. A nice surprise here is that we can use our nextPerm:

n = 5
k = 3
A = [0] * (n-k) + [1] * k
while True:
    print A
    if not nextPerm(A):
        break

nextPerm does not care what the elements of the array are. It just gives the next unique ordering sorted in the lexicographic order.

[edit]

Ordered selections of k elements

Of course, if you care about the order of the elements you select, you can just go through all $k!$ permutations of them:

n = 4
k = 3
A = [0] * (n-k) + [1] * k
while True:
    B = []
    for i in xrange(n):
        if A[i]:
            B += [1+i]
    while True:
        print B
        if not nextPerm(B):
            break
    print
    if not nextPerm(A):
        break

The number of ordered selections is $\frac{n!}{(n-k)!}$ .

[edit]

Matchings

If a you want to make a maximal matching in a bipartite graph, you do it with flow, as shown in the max flow tutorial. If the graph is not bipartite, finding for example a minimum cost perfect matching is a bit harder. There exist polynominal time algorithms for this, but they are rather complex.

Going through all the matchings is most easily done recursively, and keeping track of which elements have already been matched.

Take a random unmatched element
For every other unmatched element
1. Find the cost of matching these two
2. and recursively matching the rest of the elements
Return the lowest cost found

To keep track of which elements have already been matched earlier in the recursion, you could have a boolean array marking this. But $n$ will never be large, you can keep the bits in an integer. This gives two immediate advantages: Firstly, you get an automatic "pass-by-value" recursive call. This means you do not have to clean up bits when returning to the caller, as you were only passed a copy of his integer. Secondly, this integer can be used as an index into an array for memoisation. If you had a complex value, you would neet to hash it somehow, and use a hash table.

Here is a recursive solution using memoisation.

def bestmatching(C):
    n = len(C)
    memo = [-1] * (1 << n) # table for memoisation
    def match(M):
        if memo[M] != -1:
            return memo[M]
        # find first 1
        i = -1
        for k in xrange(n):
            if M & 1 << k:
                i = k
                break
        if i != -1:
            best = float('Inf')
            # try all possible second 1's for a match
            for j in xrange(i + 1, n):
                if M & 1 << j:
                    # ... and recursively match the rest
                    best = min(best, C[i][j] + match(M & ~(1 << i | 1 << j)))
        else:
            # no 1's left, matching has zero cost
            best = 0
        memo[M] = best
        return best
    return match((1 << n) - 1)

from random import *
n = 10
C = [[None] * n for i in xrange(n)]
for i in xrange(n):
    for j in xrange(n):
        if i <= j:
            C[i][j] = randrange(1,10)
        else:
            C[i][j] = C[j][i]
print bestmatching(C)

Do take note of the requirement for using matching here. The matching of two elements must not affect the matching of another two elements!

The number of matchings is given by the recurrence:

$T(n) = \begin{cases} 1 & \mbox{if }n=2 \\ (n-1) \cdot T(n-2) + 1 & \mbox{if }n > 2 \end{cases}$

What is the solution?

If you did not solve it yet, you should try Jogging Trails from last training session. It is a really pretty problem!

PS: Memoising complex input parameters for recursive functions is sometimes useful, and making a string representation of the parameters is often simple. Just use for example "param1,param2,param3" (if the parameters do not contain commas).

[edit]

Summing up

There are tons of brute force problems which do not fit into these categories. But if you know how to program these, you should be able to solve many of them. A lot of brute force problems consists of selecting the cheapest of many possible solutions, where the solutions are obvious (like "pick coordinates $x, y$ ), but computing the cost is a bit trickier.

[edit]

Problems

Topcoder: SillySudoku. Div 1 500.
TopCoder: EnclosingRectangle. Div 1 1000.
TopCoder: Wizarding. Div 1 1000.

Search in TopCoder's Problem Archive to find more brute force problems.

Retrieved from "http://feiten.idi.ntnu.no/wiki/index.php/Tutorial_2006-09-02"

Tutorial 2006-09-02

From FeitWiki

Contents

Program

Network flow

Optimizations

Problems

Brute force

Selections

Permutations

Unordered selections of k elements

Ordered selections of k elements

Matchings

Summing up

Problems

Views

Personal tools

Navigation

Search

Toolbox