10952 - Pattern Transformations

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Tomzy
New poster
Posts: 1
Joined: Sat Oct 08, 2005 6:22 pm

10952 - Pattern Transformations

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
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

10952 - Pattern Transformations

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
New poster
Posts: 10
Joined: Thu Jul 18, 2002 2:40 pm
Location: Russia
Contact:

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

Are the tests for this problem correct? :)

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

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
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm

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

has this problem been fixed yet?

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

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

i also agree with tomzy. can any one please clear us?
Self judging is the best judging!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10952 - Pattern Transformations

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

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.
Self judging is the best judging!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

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?
Self judging is the best judging!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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.

Post Reply

Return to “Volume 109 (10900-10999)”