10849 - Move the bishop

[neno_uci]

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]

The answer can also be 0.

[neno_uci]

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

[sumankar]

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]

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]

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]

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]

Well, this was just the only difference between yours and my code in the algorithm. Post your full source.

Just for the record, how is possible this runtime?

Tweaked I/O. Without optimizations, my program runs ~ 0.035 sec.

[sumankar]

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

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

[sumankar]

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]

CUT

[sohel]

Yes, that is right.

[Jared]

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

Thanks in advance.

[helloneo]

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