# [Tug of War](https://oj.uz/problem/view/BOI15_tug)

## Subtask 1
$N \leq 10$ suggests some kind of brute-force solution. Since there are only $2N=20$ contestants in the worst case, with each having 2 options, we can try all $2^{20}$ assignments. We can then check the validity of each one in $O(N)$, which is fast enough. This is a lot of points for little code.

## Subtask 3
Since $s_i=1$, any valid assignment of teams will have a strength difference of $0$. This can be done as follows: create a bipartite graph with contestants on the left side and spots on the right side. There is a solution iff there exists a perfect matching in this graph. Drawing for the second sample (ignore the fact that some $s_i \neq 1$):

2 5
1 1 1
1 2 4
2 2 1
2 1 4


In fact, a perfect matching exists in this graph, highlighted in white:

So if all $s_i$ had been $1$ for sample 2, then the answer would be `YES`.

Is this fast enough? We have $V=30000$ and $E=60000$. In theory, a normal DFS-based matching algorithm runs in $O(VE)$, which suggests that it should not run fast enough. However, bipartite matching runs much faster in practice. A good introduction is this:

https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html

## Subtask 2
We will draw a different graph. Every rope spot will be a node, and every person is an edge. A cheesy way to think of this is that whenever there are pairs of numbers in the input, at least check if it's productive to think of the pair as being an edge. Let's draw sample 2 once again.

Now, our goal is to match every edge to one of its adjacent nodes. To do this quickly, we need some lemmas.

### Lemma 1: if a node has degree 1, we must match the edge to it
Proof: obviously true. Assume that we have the edge $a \leftrightarrow b$ and $deg(a)=1$. Every spot must be filled, so if we match the edge to node $b$, then $a$ will be unmatched, implying that some person remains unmatched.

Thus, the first thing we will do is to recursively take degree 1 nodes and match its adjcent edge to it, then remove both the node and edge. Note that these choices are forced, so we do not lose generality from it.

### Lemma 2: after running the reduction step from Lemma 1, the graph consists of several components, each being a cycle
First, if there are isolated nodes (degree 0), then it's impossible. If we have a component with $V \neq E$, then it's impossible: if $E < V$, then there aren't enough edges to match. If $E > V$, then some other component will have $E < V$, since $E=V$ in total for the whole graph (note that this is preserved from our earlier procedure of popping degree-1 nodes). So we are left with several components with $E=V$ and no degree-1 nodes. It can be proven that such a component must consist of a single cycle, i.e., every node has degree 2.

### Lemma 3: in each cycle, there are exactly 2 possible assignment
Simply take some edge and match it to one of its nodes. Now, the choice is forced, and we can use the algorithm from Lemma 1 to find the assignemnt.

Overall, we have that all possible assignments can be constructed by choosing one of the two assignemnts for each cycle. Note that all of these are valid assignments if we only consider the team balance. Thus, this solution also solves subtask 3. Now, each of these assignments adds some strength to the first team. Let $S = \Sigma s_i$. Now, there exists a solution iff we can find an assignment of strength such that team 1 has a strength in $[S/2-k, S/2+k]$ (up to off-by-one errors). Naively, this would run in $O(2^{\text{num components}})$. Thankfully, we have simplified the problem enough to use DP.

Our problem is as follows exactly: given $N$ pairs of numbers $(a,b)$, for each one we can add either $a$ or $b$ to a counter, find the set of all attainable counters. To reduce this to the standard subset-sum, start by assuming that we take the smaller of $a$ and $b$. Now, we don't start at 0, but at $\Sigma \text{ } min(a,b)$, and in every choice we can choose between $0$ and $max(a,b)-min(a,b)$. We have now reduced the problem to standard SUBSET-SUM. The DP is as follows:

S=sum of all s_i
vector<int> dp(S+1);
dp[0]=1;
vector<int> options = max(a,b)-min(a,b) for all (a,b) pairs
for (int o : options) {
    for (int i = o; i < dp.size(); i++) {
        if (dp[i-o]) dp[i] = 1;
    }
}

// dp[i] = 1 if strength if i can be attained
// note that we can't forget that we have transformed all (a,b) pairs 

This solution runs in $O(N^2 s_{max})$, which is too slow if $N=30000$.

## Subtask 4
We only need to optimize the previous solution. The classical optimization uses bitsets:

bitset<30001*20> dp;
dp[0]=1;
vector<int> options = max(a,b)-min(a,b) for all (a,b) pairs
for (int o : options) {
    dp |= dp << o;
}

This runs in $O(N^2 s_{max}/64)$, which for $N=30000,s_{max}=20$ gives $3 \cdot 10^8$, which is fast enough.

This problem can also be solved in $O(\frac{(N s_{max})^{1.5}}{64})$, which runs in 44ms. See "subset sum speedup 1" in this blog https://codeforces.com/blog/entry/98663.