OJ Board

Could someone clarify sample input for this problem.

. XO . .
. . OX .
. XX . .

. . XO .
. XX . .
. . OX .

You don't have to swap any symbols but the answer for this sample input is 1???
What's wrong with this transformation?

The sample output is wrong for this problem. It should be 0, 0, -1.
It seems I never ran my solution on the sample input, and didn't see the correct answer by manual inspection... terrible sorry for that!

Are the tests for this problem correct?

I hope so I think a tester (Derek?) was a assigned to the problem to verify my own solution. As I said, the sample input was hand crafter and it seems the solution program was never used on them (stupid I know).

I, too, think that the test cases might not be correct.
May I ask you to check them once more? I can send you my solution, if you like.

There was a bug in my judge solution to this problem, sorry! I've corrected it, and hopefully it will be reflected on the juge in a couple of days.

Again, sorry for wasting your time finding non-existent bugs

To remove any other confusion Derek Kisman was suposed to write alternate for this problem but he could not manage time but when I knew it I had already sent the template so I could not mention that it too did not have alternate solution.

has this problem been fixed yet?

Doesn't look like that. I guess it will be rejudged immediately when it's fixed, and since I know there will be at least one who has the correct answer you just have to look for when the accept rate becomes greater than 0.

i also agree with tomzy. can any one please clear us?

You probably have an old version of the problem statement. It was fixed, check the new version here: http://acm.uva.es/p/v109/10952.html

Hmm... I see! You are right! I had older version!

Now, how to solve it? Can you please give me some hint?

It seems augmenting path might work. But swap is making all the trouble.

My idea is: Augment path with out making swap. if all the chars are matched then ans is 0. if not then start sweep augmenting path. so andwer is: unmatched/2 where unmatched after first augmneting process. if in the second augmenting process there still remains unmatched chars then -1.

But i think this is wrong process. can anyone please put me on the right track?

Thanks in advance.

I've used dynamic programming: a state is a row number and a pair of bitmasks. My program has O(h 4^w) states, does O(2^w) work per each state, so total complexity is O(h 8^w).

However, I've also got accepted with a pure brute force solution.

What is the meaning of 0 and 1 in bitmask? and what do those two bitmask represent?

Bitmasks tell which cells of the previous row are vacant (so a letter can be moved there from below), and in which cells of the current row a letter from above is to be moved.