10849 - Move the bishop

neno_uci · Post by **neno_uci** » Sat May 21, 2005 1:36 pm

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

Am i right???, if no, please tell me a counter-example, thanx in advance, frustraded,

Yandry.

Per · Post by **Per** » Sat May 21, 2005 1:38 pm

The answer can also be 0.

neno_uci · Post by **neno_uci** » Sat May 21, 2005 1:55 pm

Thanx a lot Per, that was really a very nice trick for me!!!

sumankar · Post by **sumankar** » Wed May 25, 2005 3:09 pm

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

mf · Post by mf » Wed May 25, 2005 3:21 pm

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 · Post by **Antonio Ocampo** » Thu May 26, 2005 5:46 am

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 · Post by **sumankar** » Thu May 26, 2005 6:08 am

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 · Post by mf » Thu May 26, 2005 6:42 am

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 · Post by **sumankar** » Thu May 26, 2005 7:22 am

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!

mf · Post by mf » Thu May 26, 2005 7:29 am

I submitted the code as C by the web-interface, it gets accepted.

sumankar · Post by **sumankar** » Thu May 26, 2005 7:34 am

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 · Post by **helloneo** » Mon Jul 04, 2005 3:49 pm

sohel · Post by **sohel** » Mon Jul 04, 2005 4:10 pm

Yes, that is right.

Jared · Post by **Jared** » Wed Jul 20, 2005 11:51 am

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

Thanks in advance.

helloneo · Post by **helloneo** » Sat Jul 23, 2005 5:16 am

have you ever thought the 2 bishops are on the same position..?

UVa OJ Board