## 10849 - Move the bishop

Moderator: Board moderators

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

### 10849 - Move the bishop

Hi:

I just wanted to know if my algorithm was right, 'cause I could not get AC during the contest

1. When abs(f1 - f2) == abs(c1 - c2) the min number of moves is 1.
2. When odd(f1 + c1) == odd(f2 + c2) the min number of moves is 2.

else no move...

Yandry.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
The answer can also be 0.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
Thanx a lot Per, that was really a very nice trick for me!!!

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
I am trying to go from (sx, sy) to (tx, ty).All coords are long ints.

Code: Select all

``````            if can't move
{
print "no move\n";
}
else
{
/* calculate, what else! */
print #"\n";
}``````
Removed spoiler...
Last edited by sumankar on Thu May 26, 2005 7:37 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
What is wrong here?
This is wrong, I think:

Code: Select all

``if ( (sx+sy+tx+ty)&1L ) ``
My AC code checks the "no move" case like:

Code: Select all

``if (((x0 + y0) & 1) != ((x1 + y1) & 1)) {``

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Hi for all

Just for the record, how is possible this runtime??

Code: Select all

``````1 0:00.006 64 mjf f C 2005/05/25-13:17:40.387 3593783   (H0)
``````
Is there any better algorithm or is just an I/O improvement?

Regards

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
mf wrote:
What is wrong here?
This is wrong, I think:

Code: Select all

``if ( (sx+sy+tx+ty)&1L ) ``
My AC code checks the "no move" case like:

Code: Select all

``if (((x0 + y0) & 1) != ((x1 + y1) & 1)) {``
Well what you are doing is checking if the parity of the sum of the x & y coords of the start and end points are same or not. The sums can either be Odd or Even, and if they are same, summing two Odds would give me an even number and so on for the Even sums...which is why I would think the code for no move is correct.

Suman.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Well, this was just the only difference between yours and my code in the algorithm. Post your full source.
Antonio Ocampo wrote:Just for the record, how is possible this runtime?
Tweaked I/O. Without optimizations, my program runs ~ 0.035 sec.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
mf wrote:... Post your full source.
Small change:
from

Code: Select all

``````if ( ((sx+sy+tx+ty)&1L) )
``````
to

Code: Select all

``````if ( ((sx+sy+tx+ty)&1L) || (tx>n || ty>n) || (sx<1L||sy<1L||sx>n||sy>n))
``````
Thanks mf, your post was an eye-opener of sorts!I was staring back at the code and then suddenly realized where is the size of the board coming in to the picture and...Voila!
Last edited by sumankar on Thu May 26, 2005 7:31 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I submitted the code as C by the web-interface, it gets accepted.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
mf: Is that my code you are talking about?This is the link I use
http://acm.uva.es/problemset/submit.php.
Thanks for taking all that trouble.

One more thing:tweaked i/o, can you possibly enlighten me a tad bit more?:)
Suman.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### 10849 - Move the bishop

CUT
Last edited by helloneo on Tue May 22, 2007 7:53 am, edited 2 times in total.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### ja..

Yes, that is right.

Jared
New poster
Posts: 3
Joined: Wed Jul 20, 2005 11:50 am

### 10849 - Move the bishop

It seems to be a easy problem, but I got WA always.
Is there any tricky I/O ?