10952 - Pattern Transformations

Tomzy · Post by **Tomzy** » Sun Oct 30, 2005 11:21 am

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?

Yarin · Post by **Yarin** » Sun Oct 30, 2005 5:02 pm

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!

Renat · Post by **Renat** » Sun Oct 30, 2005 8:27 pm

Are the tests for this problem correct?

Yarin · Post by **Yarin** » Sun Oct 30, 2005 11:50 pm

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).

mf · Post by mf » Mon Oct 31, 2005 8:24 pm

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.

Yarin · Post by **Yarin** » Tue Nov 01, 2005 1:05 am

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

shahriar_manzoor · Post by **shahriar_manzoor** » Tue Nov 01, 2005 4:34 pm

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.

gush · Post by **gush** » Wed Nov 02, 2005 6:52 am

has this problem been fixed yet?

Yarin · Post by **Yarin** » Wed Nov 02, 2005 2:38 pm

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.

shanto86 · Post by **shanto86** » Thu Jul 06, 2006 6:26 pm

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

mf · Post by mf » Mon Jul 10, 2006 3:29 am

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

shanto86 · Post by **shanto86** » Mon Jul 10, 2006 5:07 am

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.

mf · Post by mf » Mon Jul 10, 2006 5:37 am

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.

shanto86 · Post by **shanto86** » Mon Jul 10, 2006 7:11 pm

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

mf · Post by mf » Tue Jul 11, 2006 12:41 pm

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.

OJ Board