If A and B have analogous solution, and B and C have analogous solution, can we say what A and C have analogous solution? If so, the problem is simple, otherwise it's a graph problem...

No :) If so the problem becomes too easy.
You have only vertices and edges i.e. graph.

This problem is equivalent to problem about matching in biseparated graph.

Edited by author 08.08.2006 14:26

What if there are several unconnected graphs? Perhaps I should connect them to get the needed matching (N vertices of one color, N of another)....

You have to find maximum matching.
If its size less than N then "IMPOSSIBLE".
What difficults can appear if graph is unconncted?

Okay, the problem of maximum matching is described at Cormen (Ford-Fulkerson algo). But I used another idea. First of all I checked each connected part of the graph (painted it with BFS into black and white). Wherefore I found if the graph is biseparated. After that we have obviously another problem. We have pairs of integers (x1,y1), (x2,y2), (x3,y3) .. (xm,ym). The total sum of all numbers is 2*n. The pair can be inversed. We need to find a combination 100001001 (m digits), such that b1+b2+b3+b4+..bm=N, where bi=xi if i-th digit is 0 and yi otherwise. I used Dinamic programming for that and got WA. Why such approach does not work? (If you want, I can send you my code).

Edited by author 11.08.2006 14:59

Edited by author 11.08.2006 14:59