## 10620 - A Flea on a Chessboard

Moderator: Board moderators

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

### 10620 - A Flea on a Chessboard

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?

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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
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
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?

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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
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.
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
I finally got AC. . 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:
negue wrote:I finally got AC. . 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) ) --> ?

tep

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
tep wrote:
negue wrote:I finally got AC. . 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) ) --> ?

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.
Impossible is Nothing.

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

### 10620 - A Flea on a Chessboard

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

### Re: 10620 - A Flea on a Chessboard

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!