10620 - A Flea on a Chessboard

negue · 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?

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

negue · 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?

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

Good luck.

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

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 · Post by **tep** » Thu May 06, 2004 4:29 am

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) ) --> ?

Thx in advance

tep

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

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) ) --> ?

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.

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

http://ideone.com/jMVcQB
Why WA ?

brianfry713 · 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).

OJ Board