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.



Firstly, since two adjacent foxes i and j, \(a_i + a_j\) must be some prime number p. Since \(a_i \geq 2\), we know that p must be larger than 2! This observation alone simplifies the problem into a very manageable state:
1. For any two adjacent foxes, one of them must be odd, and the other must be even, or else their ages won't sum up to a prime number.
2. Consider a fox i with an odd \(a_i\) seated in a certain table T. Since every table must have at least 3 foxes, it means that fox i _must_ have 2 neighbours j and k (!). What do we know about j and k? They must both have ages with even parity! Hence in other words we can say that every fox must be matched with another two foxes of opposite parity.

This means bipartite matching between odd parity foxes and even parity foxes! It's now a matter of representing these foxes in the bipartite graph. For each odd parity foxes i, we place an edge of capacity 1 from i to an even parity fox j if their ages add up to a prime number. Furthermore, we connect source s to each odd parity foxes with capacity 2, and connect each even parity foxes to a sink t with directed edge with capacity 2. This will establish the constraint in which each fox must be seated next to two foxes with different parity. We run a maximum flow algorithm from source to sink to find the maximum matching. There is a solution to the problem if and only if the maximum flow is equal to the total capacity out of s and total capacity into t.

A very good problem.

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

/*
Every odd number must have 2 even number as its neighbor, and vice versa
source -> 2 -> odd -> even -> 2 -> sink
*/
int mark[100000];
int cap[203][203], f[203][203];
int val[203], par[203];
int N, S=201, T=202;
int maxflow = 0;
int odd = 0, even = 0;
int vis[203];
int INF = 1234567;
vector<vector<int> > adj;
vector<vector<int> > temp;
int augment_path(int v, int mf){
    int u = par[v];
    if(v == S) {
        return mf;
    }
    bool backedge = false;
    if(cap[u][v]-f[u][v] <= 0 && f[v][u] > 0) backedge = true;
    if(backedge) {
        mf = min(mf, f[v][u]);
    } else {
        mf = min(mf, cap[u][v] - f[u][v]);
    }
    mf = augment_path(u, mf);
    if(backedge) {
        f[v][u] -= mf;
    } else {
        f[u][v] += mf;
    }
    return mf;
}

void edmondskarp() {
    maxflow = 0;
    while(1) {
        bool augmented = false;
        for(int i=0;i<203;++i)vis[i] = 0;
        queue<int> q;
        q.push(S);
        vis[S] = 1;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int i=0;i<203;++i){
                if((cap[u][i]-f[u][i]>0 || f[i][u] > 0)  && !vis[i]) {
                    vis[i] = 1;
                    par[i]=u;
                    if(i==T) {
                        maxflow += augment_path(T, INF);
                        augmented = true;
                        break;
                    }
                    else q.push(i);
                }
            }
            if(augmented)break;
        }
        if(!augmented)break;
    }
}

void dfs(int u) {
    vis[u] = 1;
    temp.back().push_back(u);
    for(int i=0;i<adj[u].size();++i){
        if(vis[adj[u][i]])continue;
        dfs(adj[u][i]);
    }
}

int main(){
    for(int i=2;i*i<100000;++i){
        for(int j=i;j*i<100000;++j){
            mark[i*j] = 1;
        }
    }
    scanf("%d",&N);
    for(int i=0;i<N;++i){
        scanf("%d",&val[i]);
    }
    for(int i=0;i<N;++i){
        if(val[i]%2) {
            cap[S][i] = 2;
            ++odd;
        } else {
            cap[i][T] = 2;
            ++even;
        }
        for(int j=i+1;j<N;++j){
            if(mark[val[i]+val[j]])continue;
            if(val[i]%2)cap[i][j] = 1;
            else cap[j][i] = 1;
        }
    }
    edmondskarp();
    if(odd * 2 != even * 2 || even * 2 != maxflow) {
        printf("Impossible\n");
        return 0;
    }
    adj = vector<vector<int> > (N+3);
    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            if(cap[i][j] > 0 && f[i][j]>0){
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    for(int i=0;i<N;++i)vis[i]=0;
    for(int i=0;i<N;++i){
        if(vis[i])continue;
        temp.push_back(vector<int>());
        dfs(i);
    }
    printf("%d\n",(int)temp.size());
    for(int i=0;i<temp.size();++i){
        printf("%d", (int)temp[i].size());
        for(int j=0;j<temp[i].size();++j){
            printf(" %d",temp[i][j]+1);
        }
        printf("\n");
    }
    return 0;
}