UVa 563 - Crimewave

Problem Statement:
UVa 563 - Crimewave

Solution:
At first, the problem seems to be of an undirected graph maximum flow, which can be tedious to do. Furthermore, each vertices (i.e. crossings) on the map has a capacity of 1. We need to transform this representation into a more friendly one, and as it turns out, we can transform this problem into our old familiar directed graph maximum flow.

Codeforces Rockethon 2015 Problem F1 - Scaygerboss

Problem Statement:
513F1 - Scaygerboss

Solution:
Happy to solve another maximum flow problem :) The official editorial to this problem is well-written so check them out if you have not. Here I will discuss on the approach for the easier version of the problem only, as that is the max my brain can currently comprehend :D

Every maximum flow problems are interesting, and this one further reinforces that statement. Here we are to match the males and females into a cell for which each cell can be associated with at most a pair of matching. We are to find the minimum possible time for all the males and females can move to their designated cells, amongst all possible matching. Here we can use binary search to guess the minimum value, and check whether that value can result in a valid matching using maximum flow.

Codeforces Round 284 Div.1 Problem C - Array and Operations

Problem Statement:
498C - Array and Operations

Solution:
Another interesting max-flow problem, but I think coming up with the correct model may require some level of familiarity with the concept and intuition, since the runtime complexity analysis can be a bit subtle.

The clever idea behind this problem is to consider each prime one by one. We start out with a source S and a sink T. Then since \(i_k + j_k\) is guaranteed to be an odd number, we conclude that \(i_k\) and \(i_j\) has different parity, i.e. one is odd, and another is even. So we actually have a bipartite matching task, between the odd-indexed and the even-indexed \(a_i\)s. From here, we build a graph as follows:
1. Choose a prime \(p\).
2. For each pair of odd indexed \(a_i\) and even indexed \(a_j\), we find the maximum number of times each of them can be divided by \(p\), call it n and m respectively.
3. Next, we connect S to \(a_i\), \(a_i\) to \(a_j\) and \(a_j\) to T.
4. The capacity of the edges are set as follows:
    - capacity of (S, \(a_i\)) is n.
    - capacity of (\(a_j\), T) is m.
    - and capacity of (\(a_i\), \(a_j\)) is the minimum of n and m.

a bit of graph: A little note on Maximum Flow

This is a scrap note for Maximum Flow - Minimum Cut Algorithm for KIV purposes...

Terminology:
1. Capacity of an edge: \(c(u,v)\)
2. Flow : \(f\)
3. Residual Graph : \(G_f\)
4. Residual capacity : \(c_f(u,v) = c(u,v) - f(u,v)\)
5. Backedge : \(c_f(v,u) = f(u,v)\)
6. Flow Conservation: \(\sum_{u \in V} f(v,u) = \sum_{u\in V} f(u,v)\)
7. Max Flow - Min Cut Theorem: Finding maximum flow is equivalent to finding the minimum cut of the flow network.

Ford-Fulkerson Algorithm
Let \(P\) be a simple \(s-t\) path on the residual graph called the augmenting path. Let bottleneck(P) be the lowest valued edge in path \(P\) on the residual graph.

augment(f, P):
    set b = bottleneck(P)
    for (u,v) in P:
        if u,v \(\in E\):  \(f(u,v) = f(u,v) + b\)
        else \(f(u,v) = f(u,v) - b\)
    return b

Ford-Fulkerson(G,E):
    Initialize \(G_f\), f = 0
    while exist augmenting path \(P\):
        f = f + augment(f, P)
    return f

Bound: \(O(C|E|)\)
Using Edmonds-Karp Algorithm (BFS Implementation of Ford-Fulkerson), running time is pseudo-polynomial

Push-Relabel Algorithm:
Terminology:
1. height-function \(h(v)\)
2. preflow
3. excess flow (on overflowing vertex) \(e(v)\)
4. preflow property: on every vertex, in flow must be at least equals to out flow: \(\sum f(v,u) - \sum f(u,v) \geq 0\)
5. If \((u,v) \in E_f\), then \(h(u) \leq h(v) + 1\)

Push:
6. Can only push downhill: in particular, can only push on edge (u,v) if \(e(u) > 0\) (i.e. u is overflowing vertex) and \(h(u) = h(v)+1\)

push(u,v):
    e = \(min \{ c_f(u,v), e(u) \} \)
    if u,v \(\in E\):  f(u,v) = f(u,v) + e
    else f(v,u) = f(v,u) - e
    e(u) = e(u) - e
    e(v) = e(v) + e

7. Push is saturating iff (u,v) disappear from \(G_f\), otherwise unsaturating.
8. If saturating push, then \(u\) is no longer overflowing vertex.

Relabel:
9. Can only be performed on overflowing vertex, and only if push cannot be performed: for all \(u,v \in E_f\), \(h(u) < h(v) + 1\)
10. Since \(u\) is overflowing, it is always true that there is at least an edge \((u,v) \in E_f\).

relabel(u):
    d = \(min_{(u,v) \in E_f} \{ h(v) \} \)
    h(u) = d + 1

Push-Relabel(G,E):
    Initialize \(f, h, e, G_f\) such that:
        for all v, h(v) = 0, except source: h(s) = \(|V|\)
        for all v, e(v) = 0.
        for all (s,v) \in E:
            f(s,v) = c(s,v)
            e(v) = c(s,v)
            e(s) = e(s) - c(s,v)
    while can push or relabel:
        push or relabel accordingly!
    return the max flow f

Correctness: hinges on a lot of lemmas, a few important ones:
1. There is no s-t path in \(G_f\). Proof: by contradiction using height function property and a fact about a simple path.
2. Invariant: preflow property is always conserved. Hence if the algorithm terminates, that means we cannot push or relabel, hence there is no overflowing vertex anymore, which means the preflow is indeed the flow, and since no s-t path in \(G_f\), by Max Flow - Min Cut theorem the flow is max flow.
Run-time: \(O(V^2E)\), the proof is very elaborate.