dtalamas24's blog

By dtalamas24, 8 years ago, In English

Hi,

If you are located at the bottom left corner (0, 0) of a plain with H x W cells, and you move U positions up and R positions right in each step, how to calculate if you will eventually arrive to a specific cell after any amount of steps? (If you fall to the right of the plane, you get to the left of the plane. Same with falling up)

Thanks.

 
 
 
 
  • Vote: I like it
  • -13
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

You must find an integer k that satisfies: (k*r)%w=x & (k*u)%h=y. If (w*h)<=10^8 you can simply try all k: 1<=k<=lcm(w,h). Or you can solve system of two Diofant's equations: k*r=a*w+x & k*u=b*h+y. Just use extended Euclid algo. Good luck!

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    But the extended euclid algorithm solves for x and y in ax + by = gcd(a, b), where is the gcd part in k*r=a*w+x & k*u=b*h+y ?

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      First, let's solve Diofant equation with two variables: a*x+b*y=c. It's obvious that linear combination of a and b must be divisible by their GCD. So, if c is not divisible by their GCD => there is no solution. We can try to find a solution in a such form: x=x1*(c/d) & y=y1*(c/d), where d=GCD(a,b). Our equality can be rewriten as: a*x1*(c/d)+b*y1*(c/d)=c => a*x1+b*y1=d, which can be solved by the extended Euclid algo, as you know. x1 and y1 are the initial values, general solution can be obtained in a such way: x(n)=x1+n*(b/d) & y(n)=y1-n*(a/d), n — any integer. So, we can solve both equations of our system and then intersect solutions like two modular equations. Also I recommend you to read about CRT — it is a general method of solving systems of modular equations.

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You can answer that question in O(1). For each step when you go up y coordinate increases with U and for each step you go right x coordinate increases with R. Because you start walking from (0,0) you can go to every cell with coordinates (X,Y) if and only if X%R = 0 and Y%U=0 and X/R = Y/U.

»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Can You share the link to the original problem,please?