What if there are no \(1\)’s on the blackboard?

In this case, if we add an edge between the pair on which we can perform an operation, that will be a bipartite graph, so we can use maximum flow algorithm to get the answer.

Now we consider the general case. Since we can erase two \(1\)’s at once, we cannot directly use max-flow algorithm.

Suppose we erase \(1+1=2\) \(k\) times, and pair the remaining \(1\)’s with even numbers. If we can erase a pair of odd and even numbers \(f(k)\) times, the operation is performed \(f(k)+k\) times in total.

Here, if it is shown that \(f(k)+k\) is concave, then we can do trinary search between \(0\) and \(\lfloor \frac{x}{2}\rfloor\), where \(x\) is the number of \(1\)’s.

We can proof that \(f(k-1)-f(k)\leq f(k)-f(k+1)\) by contradiction. (\(f(k-1)-f(k)\> f(k)-f(k+1)\) contradicts to the fact that \(k\) yields maximum matching.)

Thus, \(f(k)\) is concave, and so is \(g(k):=k\), so their sum \(f(k)+k\) is concave too. Thus, the problem has been solved.

Some solutions don’t require trinary search.

Considering the values of \(f(k)\), we can see that increasing \(1\) does not decrease the maximum matching, while increases at most by the number of new \(1\)’s, so \(f(k)\) is between \(f(k+1)\) and \(f(k+1)+2\).

By the concavity, the differences of adjacent terms of \(f(k)+k\) are \(+1,\ldots,+1,0,\ldots,0,-1,\ldots,-1\) (where some of \(+1,0,-1\) may not be present).

Thus, the leftmost and rightmost values of \(f(k)+k\) uniquely determines \(k\) that yields the maximum.

Hence we can find the answer with \(3\) max-flows without trinary search.

Sample code (C++)