10849 - Move the bishop

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

Moderator: Board moderators

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

10849 - Move the bishop

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 :cry:

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

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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

The answer can also be 0.

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

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

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

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

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

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
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

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
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

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

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
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Thu May 26, 2005 7:22 am

mf wrote:... Post your full source.
Small change: :D
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:

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

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:

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

10849 - Move the bishop

Post by helloneo » Mon Jul 04, 2005 3:49 pm

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

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

ja..

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

Yes, that is right.

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

10849 - Move the bishop

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

hhh

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

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

Post Reply

Return to “Volume 108 (10800-10899)”