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)?
Is complexity O(a1·b1·n) enough? And what is the source of this problem?
I came up with this problem. I was just wondering if it could be solved with run time better than O(x * y * n)
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?
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).
Is there a polynomial algorithm for solving the problem in one dimension?
1 mln dollars question
I was being sarcastic. Good reference though, I suppose this answers the question.
I got it, but couldn't just pass by :)
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.
I mean that on 1D (steps of type 0, a), it is a variation of the knapsack problem, which is NP.
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).