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 *a*_{i}, *b*_{i} which means that a step of type *i* moves you *a*_{i} steps to the right and *b*_{i} 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(a_{1}·b_{1}·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 meanO(a_{1}*b_{1}*n)?If you do mean

O(a_{1}*b_{1}*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+a_{1},j+b_{1}) is reachable. Let denotedp[i][j] (i<a_{1},j<b_{1}) denote the minimumksuch that (i+k·a_{1},j+k·b_{1}) is reacheable. We can run BFS on statesdp[i][j]. But it isn't enough to consideri<a_{1},j<b_{1}. We must consider those (i,j) thati<a_{1}orj<b_{1}. The complexity isO((a_{1}·y+b_{1}·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

xneeds to be divisible bygcd(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 1

Dproblem. Make a rectangle with (2x+ 1) * (y+ 1) cells. Put 1 in cells (0, 0), (a_{1},b_{1}), (a_{2},b_{2})... (a_{n},b_{n}), and 0 in rest of cells. Now create a polynomial where coefficient attached tox^{i}is value in cell (imod(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 applya=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 thanx+yjumps, so we jut have to raise this polynomial to the power ofx+y(and remember about overflows). Complexity isO(x*y*log(x*y) *log(x+y)). It's easy to modify this solution to get minimum number of jumps (without changing complexity).