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

CrazyTerabyte
New poster
Posts: 25
Joined: Fri Jul 16, 2004 3:19 am
Location: Brazil
Contact:

Post by CrazyTerabyte » Fri Jul 14, 2006 2:07 pm

hey, wait! The sample output says the first pattern requires 0 swaps, but the problem description says it requires 1 swap... Something is very wrong here.

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

Post by mf » Fri Jul 14, 2006 2:48 pm

It's a mistake. Zero swaps is the correct answer.

CrazyTerabyte
New poster
Posts: 25
Joined: Fri Jul 16, 2004 3:19 am
Location: Brazil
Contact:

Post by CrazyTerabyte » Fri Jul 14, 2006 4:46 pm

One more question: In this problem, we must discover if we can transform the first pattern into second one in *one* step, right? So: X.. and ..X would answer -1. Is this right?

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

Post by mf » Fri Jul 14, 2006 6:29 pm

That's right.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sat Jul 15, 2006 5:08 am

My brute force code and bitmap code both getting tle i can't understand why!

any idea:

Code: Select all

REMOVED
Last edited by shanto86 on Sat Jul 15, 2006 10:37 am, edited 1 time in total.
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sat Jul 15, 2006 10:36 am

Well... now i need help. I am getting WA. can you please give me some sample input output?

PS: (I had some mistake in the code. so i fixed and avoided TLE. it is giving WA in 2sec.)
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 » Sat Jul 15, 2006 4:53 pm

Here are some tests:

Code: Select all

13

3 4
.X. .X.
.OX XO.
..O .O.
... ...

2 3
XO OX
.. .X
OX XO

2 4
XO OX
.. .X
OX XO
.. ..

4 4
OXOX XOXO
XOXO OOXX
OXOX XOXO
XOXO OXOX

2 2
OO XO
XO OO

5 3
.XO.. ..XO.
..OX. .XX..
.XX.. ..OX.

4 4
OXOX XOXO
XX.O OX.X
O..X X..O
XOXO OXOX

4 5
.... ....
.XO. .OX.
.X.. ..X.
.OX. .XO.
.... ....

4 4
XXOX O.XO
O.OO XXOX
OX.X .XXO
XOXX OXOX

8 8
XOXOXOXO OXOXOXOX
XOXOXOXO OXOXOXOX
XOXOXOXO OXOXOXOX
XOXOXOXO OXOXOXOX
XOXOXOXO OXOXOXOX
XOXOXOXO OXOXOXOX
XOXOXOXO OXOXOXOX
XOXOXOXO OXOXOXOX

8 8
XOXOXOXO XOOXOXOX
XOXOXOXO OXOXXOOX
XOXOXOXO OXXOOXOX
XOXOXOXO OXOXOXOX
XOXOXOXO XOOXOXOX
XOXOOXXO OXOXOXOX
XOXOXOXO OXXOOXOX
XOXOXOXO OXOXOXOX

8 8
XOXOXOXO .XOXOXOO
XOXOXOXO XXOXOXOO
XOXOXOXO XOXXOOXO
XOXOXOXO XXOOXXOO
XOXOXOXO OXOXXXOO
XOXOXOXO XXOOXOXO
XOXOXOXO XOXXOOXX
XOXOXOX. XXOOXXOO 

8 8
XOXOXOXO OOOOOOOO
XOXOXOXO XXXXXXXX
XOXOXOXO OOOOOOOO
XOXOXOXO XXXXXXXX
XOXOXOXO OOOOOOOO
XOXOXOXO XXXXXXXX
XOXOXOXO OOOOOOOO
XOXOXOXO XXXXXXXX

Code: Select all

-1
-1
-1
0
0
0
0
1
3
32
26
9
0

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sun Jul 16, 2006 2:32 am

got AC. thanks!

Poor timing using bitset of stl! :(
Self judging is the best judging!

Post Reply

Return to “Volume 109 (10900-10999)”