10620 - A Flea on a Chessboard

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

Moderator: Board moderators

Post Reply
negue
New poster
Posts: 6
Joined: Tue Sep 24, 2002 8:00 pm
Location: Iasi, Romania

10620 - A Flea on a Chessboard

Post by negue » Sun Feb 08, 2004 3:10 am

I get WA for this problem and I don't know why.

My approach is the follwing:
I move the flea step by step, and I check each time whether it is on a black square (including the border) or on a white square. If for a number of steps (depending on S, dx and dy) l don't encounter a white squre then it means I'm stuck on blacks.

Is there a problem with the range of x, y, dx or dy?

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

Post by sohel » Sun Feb 08, 2004 6:46 am

If for a number of steps (depending on S, dx and dy) l don't encounter a white squre then it means I'm stuck on blacks.
Exactly how many times do you iterate the loop. Because that figure is very important.

how do you check for black/white square.
:-?

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Sun Feb 08, 2004 4:30 pm

You must check if the flea is on a white square 1005 times only if 1005 step and flea is on black square then output that flea cannot get to the white square.
Tell if you don't getting Accepted.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

negue
New poster
Posts: 6
Joined: Tue Sep 24, 2002 8:00 pm
Location: Iasi, Romania

Post by negue » Sun Feb 08, 2004 9:25 pm

The number of steps is the period of the sequence of squares, that is the lcm of the periods on x and y, that is per := lcm( gcd(S,dx), gcd(S,dy)). So after per moves the sequence will be the same, so there is no need to check further. In fact if after per moves we are on a white square then the period is 2*per (but it doesn't matter because we won).
The test for white squares is: ((x/S)+(y/S))%2 && (x%S) && (y%S) where x,y is the current position.

Should I show the code?

for Eduard: I don't really get it. You mean I should do exactly 1005 steps? Why?

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

Post by sohel » Mon Feb 09, 2004 5:35 am

Eduard is right about 1005 steps ---- that's what I have done.

But there is a lot of quick rejection test ---- my program got AC in 0.010 seconds. I have sent the Waterloo's Judge's Solution and it took more that 1.3 seconds. the solution of their looked similar to Negue's.

Quick test:
Convert coordinates to square number coordinate - ie left most has (1,1)
and its adjacent are (2,1) and (1,2).
Suppose a square has coordinates (X, Y). then if (X+Y) is odd then it is a white square else black.
This save a lot of time.
Hope it helps.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Mon Feb 09, 2004 12:12 pm

I mean that if you step 1005 times that if flea is not on a white square then he won't ever get to the white square.
Why 1005??
Becuose of test data!!! if you will check 1000 times then you will get WA.You can check 1500 times but it takes mauch time. I checked 1005 times and get Accepted for 0.020 seconts. :D
Good luck.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

negue
New poster
Posts: 6
Joined: Tue Sep 24, 2002 8:00 pm
Location: Iasi, Romania

Post by negue » Tue Feb 10, 2004 2:42 am

I finally got AC. :D. It works with my formula for the number of steps, thought I wrote it wrong in the previous post. It is in fact lcm( S/gcd(S,dx), S/gcd(S,dy)).

Thanks! Seeing the Waterloo test data really helped.

for Eduard: I guess that you are talking about Waterloo's test data. Maybe here they are using the same test data. But I also guess that there could be some tests for which the number of steps would be 1006. I'm trying also to understand the solution not only to get AC.

for sohel:
Convert coordinates to square number coordinate - ie left most has (1,1)
and its adjacent are (2,1) and (1,2).
Suppose a square has coordinates (X, Y). then if (X+Y) is odd then it is a white square else black.
That's also what my test does except that the bottom left most square has (0,0) coordinates. But modulo 2 it is the same thing.
I have sent the Waterloo's Judge's Solution and it took more that 1.3 seconds. the solution of their looked similar to Negue's.
No, their solution (http://plg.uwaterloo.ca/~acm00/040131/data/C.c) is almost like yours (they use a different test for white squares) but uses instead 2000000 steps.

tep
New poster
Posts: 23
Joined: Fri Jun 13, 2003 6:08 am
Contact:

Post by tep » Thu May 06, 2004 4:29 am

negue wrote:I finally got AC. :D. It works with my formula for the number of steps, thought I wrote it wrong in the previous post. It is in fact lcm( S/gcd(S,dx), S/gcd(S,dy)).
Can you tell what's the logic behind the formula? I'm quite weak in number theory..

S / gcd(S,dx) --> what does this means?
S / gcd(S,dy) --> ?
lcm( S/gcd(S,dx), S/gcd(S,dy) ) --> ?

Thx in advance

tep

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Sun Jul 25, 2004 5:41 am

tep wrote:
negue wrote:I finally got AC. :D. It works with my formula for the number of steps, thought I wrote it wrong in the previous post. It is in fact lcm( S/gcd(S,dx), S/gcd(S,dy)).
Can you tell what's the logic behind the formula? I'm quite weak in number theory..

S / gcd(S,dx) --> what does this means?
S / gcd(S,dy) --> ?
lcm( S/gcd(S,dx), S/gcd(S,dy) ) --> ?

Thx in advance

tep
If I get things correctly,
S/gcd(S,dx) means the number of steps to repeat in x-direction
S/gcd(S,dy) means the number of steps to repeat in y-direction
lcm( S/gcd(S,dx), S/gcd(S,dy) ) means the number of steps to complete a cycle as a whole

Hope this can help.
Lemme try this prob now. Bye. :wink:
Impossible is Nothing.

cyberdragon
New poster
Posts: 20
Joined: Fri Aug 30, 2013 5:42 am

10620 - A Flea on a Chessboard

Post by cyberdragon » Sun May 18, 2014 1:17 am


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10620 - A Flea on a Chessboard

Post by brianfry713 » Tue May 20, 2014 2:44 am

Input:
1000 0 499 500 1501

Correct output:
After 1003 jumps the flea lands at (501500, 1506002).
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 106 (10600-10699)”