allthecode's blog

Reachability of a point
By allthecode, history, 8 years ago, In English

You are in position (0, 0) of a coordinate plane. You want to determine if you can reach point (x, y). There are n different types of steps that you can make. Step type i is represented by two non-negative integers ai, bi which means that a step of type i moves you ai steps to the right and bi steps up.

How to determine if it is possible to reach point (x, y) using only those type of steps? You are allowed to use a type of step multiple times but you can't do half of a step.

Can this problem be solved with time complexity better than O(x * y * n)?

  • Vote: I like it
  • +4
  • Vote: I do not like it

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

Is complexity O(a1·b1·n) enough? And what is the source of this problem?

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

    I came up with this problem. I was just wondering if it could be solved with run time better than O(x * y * n)

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wait do you mean O(x * y * n) or do you really mean O(a1 * b1 * n)?

    If you do mean O(a1 * b1 * n) what is your algorithm?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I meant what I wrote, but now I see that I made a mistake. I thought about the following solution:

      If (i, j) is reachable, then also (i + a1, j + b1) is reachable. Let denote dp[i][j] (i < a1, j < b1) denote the minimum k such that (i + k·a1, j + k·b1) is reacheable. We can run BFS on states dp[i][j]. But it isn't enough to consider i < a1, j < b1. We must consider those (i, j) that i < a1 or j < b1. The complexity is O((a1·y + b1·x)·n).

      → Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Is there a polynomial algorithm for solving the problem in one dimension?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    1 mln dollars question

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was being sarcastic. Good reference though, I suppose this answers the question.

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

        I got it, but couldn't just pass by :)

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hmm I don't quite understand where is the sarcasm in your comment haha. I think the one dimension version of the problem is not trivial. For example, if your possible steps are (a, 0), (b, 0), (c, 0) how do you determine if a point (x, 0) is reachable?

        Well, a necessary condition to be reachable is that x needs to be divisible by gcd(a, b, c) but that is not a sufficient condition.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I mean that on 1D (steps of type 0, a), it is a variation of the knapsack problem, which is NP.

          → Reply
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

It can be done in almost the same way as 1D problem. Make a rectangle with (2x + 1) * (y + 1) cells. Put 1 in cells (0, 0), (a1, b1), (a2, b2)... (an, bn), and 0 in rest of cells. Now create a polynomial where coefficient attached to xi is value in cell ( i mod (2x + 1),  floor(i / (2x + 1)) ) (or something similar). Now use FFT to get this polynomial raised to the power of 2. For all numbers apply a = min(a, 1) (to avoid overflow) and for all values in cells (a, b) such that (a > x) set this values to 0. Your rectangle now tells you to which cell you can get in at most 2 moves. There is trivial observation, that we won't do more than x + y jumps, so we jut have to raise this polynomial to the power of x + y (and remember about overflows). Complexity is O(x * y * log(x * y) * log(x + y)). It's easy to modify this solution to get minimum number of jumps (without changing complexity).

→ Reply