My solution:
1. (A+C+F+H)-(B+D+E+G)=const => if const!=0 then IMPOSSIBLE
2. While we have to destroy some we do two operations. (3,4)
   3. If we can do one of (AB, BC, CD, DA, EF, FG, GH, HE, AE, BF, CG, DH)- we do it.
   4. If AG => BF+ AB- GF-
      If BH => CG+ BC- HG-
      If CE => DH+ CD- EH-
      If DF => AE+ DA- FE-

Why it gets WA #5?
Is it wrong algorithm or wrong realization?

My code:

Here was nearly AC code :)

Edited by author 30.05.2005 05:31

though I don't know what "2. While we have to destroy some we do two operations. (3,4)" mean, I think you solution is right,because I got AC in the same way.maybe there's some bugs in your code.

2, 3 and 4 are right.
1 is wrong. const may be different from 0 when there is a solution

Are you sure? Can you give me example?

I can prove it:
We process operation with pair of vertexes.
The one is in {A,C,F,H} another is in {B,D,E,G}.
So (A+C+F+H)-(B+D+E+G)=const
Supose we already annighilated all 'troubles' then
A=B=C=D=E=F=G=H=0 => const=0 =>
If const is not equal to zero we can't annighilate all 'troubles' => IMPOSSIBLE

What is wrong in it?

Algorithm is Ok, but in my code was one misprint.