I'll try to mimic the Codeforces editorial style for a TopCoder problem, BoardPainting.

We can easily paint each black square separately, that's allowed although not optimal. So we want to join some black squares, the adjacent ones. Let's put dots in the middle of the square borders that could be potentially joined, let's call them joints. As we are not allowed to take turns during painting, some joints collide with another. We have a graph G then: joints are vertices and edges connect the joints that collide which one another.

Formula for the solution is blacks - (potentialJoints - impossibleJoints). We want to minimize the impossibleJoints to reach the lowest total number. From our graph G we need to remove some vertices, so that only non-colliding joints are left. From there I needed to gather some theory, that was new for me, following route 1. Then I discovered I really didn't need that knowledge and could use route 2.

Route 1

After we leave only non-colliding joints, there will be no more edges between them. If we consider graph G', having edges only where G had no edges, that would be a clique in this graph. A clique is complementary to vertex cover in graph G. So we need to find a vertex cover in G (actually it may be noticed directly). Bad news, finding minimal vertex cover is NP-complete. Good news, not for bipartite graphs! König's theorem tells us that it's as easy as finding the maximum matching in a graph. That's what we almost always do in 1000 point problems. Apply a flow algorithm or something of that genre.

Route 2

We would like to remove some vertices from G. After this removal we want to have no connections between any joints. This cut should be minimal. Is this a minimal cut problem? Simply.

---

Not so short as it was supposed to be, anyway, I had fun. Especially the route 1 and all its connections are so interesting. It reminds me why I love maths.