Codeforces 546E - Soldier and Travelling

Problem Statement:
546E - Soldier and Travelling

Solution:
Firstly notice that we can think of the problem as an instance of linear programming. For each city i, let x[i][j] be the number of soldiers that move from city i to city j (in particular, x[i][i] is the number of soldiers that stay in the city).

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 #290 (Div. 1 C / Div. 2 E) - Fox and Dinner

Problem Statement:
512C - Fox and Dinner

Solution:
I've always been fascinated with maximum flow problems. The author to this problem is brilliant, and his official editorial is very well written, succinct and sweet. This post is mostly for my future reference, but feel free to read through the discussion :)

We can certainly identify that this problem is a matching problem, but what exactly is the type of matching we are interested in? On the first glance it seems to require some notion of tables, in which each table must contain at least 3 elements. That sounds like a random constraint, but as it turns out, a pretty fundamental observation to this problem can leads to a very clever representation of the problem that can easily enforce the constraints described in the problem statement.

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.

UVa 11167: Monkeys in the Emei Mountain

Problem Statement:
UVa 11167 - Monkeys in the Emei Mountain

Solution:
A pretty tough maxflow problem. Oh yes, this is a bipartite matching problem between N monkeys and 50000 time intervals. The simplest way to think about this problem is to have N nodes representing monkeys, 50000 nodes representing time intervals, and two nodes S and T which are source and sink respectively. A monkey has to drink v times, hence we add an edge between S and that monkey with capacity v. This monkey can drink from time interval s to t, so we add an edge to each time interval from s to t by capacity 1 each. Finally, each time interval can only be shared between M monkeys, so for each time interval we add an edge to T with capacity M. The maximum flow from S to T will give us the maximum bipartite matching between the monkeys and the time intervals. If this maximum flow exactly equals to the total times all monkeys have to drink, we have found a valid matching.

Topcoder SRM 633 Div. 1 600 - DoubleTree

Problem Statement:
SRM 633 Div. 1 600 - DoubleTree

Solution:
It is interesting to know that this problem is actually a Maximum Flow problem. When we fix a node as the root of both of the trees, we reduce the problem to maximum weight connected sub graph problem. Let's say we have chosen a root R. R will be inside the subset S in question. We run a depth first search on both tree starting at R, forming two trees A and B. Then we build a graph G such that:
1. for each node v, we connect v with its parent u in A and B each with an edge with infinite capacity. This means that if we pick node v, then we have to also pick u, so we ensure that v and R is connected.
2. introduce two new nodes, source s and sink t. For each v in G, if v has a positive score m, add an edge between s to v with capacity m. Otherwise, m is negative, then we connect v with t using an edge with capacity -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.

a bit of greedy: UVa 100249 - The Grand Dinner

Problem Statement:
UVa 100249 - The Grand Dinner

Summary:
Given several groups of people, each group consisting of several people, and given several tables of varying capacities, is it possible to place everyone in the tables such that people from the same group are not seated in the same table? If so, print out the possible arrangement.

Solution:
Apparently the problem is solvable by modeling it as some kind of matching problem and by finding the max-flow on the matching graph. However, apparently also, the problem can be solved using a greedy strategy by first sorting the groups in order of size, as well as the table in order of capacity, and start trying to assign each person in the group starting from the largest group down the sorted order of tables. Haven't thought of a proof yet...

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

/* First IDEA:
sort by no of ppl, sort by table
for each group, go through table in sorted order assign what is available
if possible, print arragement, otherwise no arrangement is possible
proof: dunno yet
*/

vector<pair<int,int> > ppl, tbl;
int pp[73] /*, tt[53]*/;
int ppp[73][103], ttt[73];
int main(){
    int N,M;
    while( cin >> M >> N ){
        if(N+M==0) break;
        ppl.clear();
        tbl.clear();
        for(int i=0;i<M;++i){
            int u;
            cin >> u;
            ppl.push_back(make_pair(u,i));
        }
        for(int i=0;i<N;++i){
            int u;
            cin >> u;
            tbl.push_back(make_pair(u,i));
        }
        sort(ppl.begin(), ppl.end());
        sort(tbl.begin(), tbl.end());
        reverse(ppl.begin(), ppl.end());
        reverse(tbl.begin(), tbl.end());
        for(int i=0;i<M;++i){
            pp[ppl[i].second] = i;
        }
        for(int i=0;i<N;++i){
            //tt[tbl[i].second] = i;
            ttt[i] = tbl[i].first;
        }
        bool ok = true;
        for(int i=0;i<M;++i){
            int sz = ppl[i].first;
            int k = 0;
            for(int j=0;j<sz;++j){
                bool found = false;
                for(;k<N;++k){
                    if(ttt[k] > 0){
                        found = true;
                        ppp[i][j] = tbl[k].second;
                        --ttt[k];
                        break;
                    }
                }
                if(!found){
                    ok = false;
                    break;
                }
                ++k;
            }
            if(!ok) break;
        }
        if(!ok) printf("0\n");
        else {
            printf("1\n");
            for(int i=0;i<M;++i){
                int sz = ppl[pp[i]].first;
                for(int j=0;j<sz;++j){
                    if(j != 0) printf(" ");
                    printf("%d", ppp[pp[i]][j]+1);
                }
                printf("\n");
            }
        }
    }
    return 0;
}