Baltic OI 2015 - Tug of War

Making Cycles

Imagine we have a bipartite graph where each spot is a node and each person is an edge between the two spots they're willing to take.

If any node has degree equal to 0, then it's not possible to assign the teams.

If any node has degree equal to 1, then we must assign the person willing to take that spot to it. After assigning that person, we can delete the node and edge from the graph.

We can repeatedly assign people to and delete nodes with degree equal to 1 by using a BFS. After doing this, all nodes will have degree greater than 1.

However, if any node has degree greater than 2, then by the pigeonhole principle, there must be a node with degree equal to less than 2, which isn't possible.

Thus, we are left with several disjoint simple cycles. Since this is a bipartite graph, these cycle lengths are all even.

Using Knapsack DP

Let the set of all cycles be $C$ and let the difference in strengths from the nodes we previously deleted be $d$.

Consider a single cycle. Notice how if a person/edge is assigned to some side, then the next person must be assigned to the opposite side.

This means that each cycle contributes a fixed amount to the difference in strengths! Let the absolute value of this amount for the $i$-th cycle be $V_i$.

We now only need to check whether there exist 2 disjoint sets $S$ and $T$ such that $S\cup T=C$ and

This is the same as checking whether a subset $S$ of $C$ exists such that

We can check this using knapsack DP in $\mathcal{O}(NK)$ time.

Since we are only checking whether we can obtain some value, we can use a bitset to speed this up.

The final complexity is $\mathcal{O}(NK/64)$, which is fast enough for 100 points.

Code

1#include <bits/stdc++.h>
2using namespace std;
3
4multiset<pair<int, int>> graph[60001];
5bool visited[60001];
6bitset<600001> possible;
7int tot = 0, sm = 0;
8
9void dfs(int node) {
10    visited[node] = true;