You are given two sets of positive integers: A and B. You start at point 0 on a line, and alternate jumps to the left and to the right, starting with a jump to the left. Whenever you jump to the left, you jump by a number chosen from A. Whenever you jump to the right, you jump by a number chosen from B.
Is any integer point reachable?
Example: A = {1, 5}, B = {2, 4}. To reach point -2, you can jump by -5, then by 4, then by -1, yielding -5+4-1=-2.
Example: A = {1, 5}, B = {2, 4}. To reach point -2, you can jump by -5, then by 4, then by -1, yielding -5+4-1=-2.
Constraints: A and B have at most 10000 elements, numbers in A and B are between 1 and 1000000000 (billion). Note that you can't jump to the left or to the right twice in a row - you have to alternate.
Source: SnarkNews Winter Series 2011, Round 2 (the round is over so it's fine to discuss solutions now).
Source: SnarkNews Winter Series 2011, Round 2 (the round is over so it's fine to discuss solutions now).
First, find numbers that can be reachable by even number of steps. Let C be a set of integers that can be written as "-A[i] + B[j]". It's easy to prove that C must have both positive number and negative number. If this condition is satisfied, all multiples of d := gcd{abs(C[i])} is reachable by even number of steps. (use the fact that gcd(x,y) and -gcd(x,y) can be written of the form "mx - ny").
ReplyDeleteAny integer point is reachable if and only if for all 0 < x < d, there exists i s.t. A[i] = x (mod d).
Use the following formula to compute d quickly:
d = gcd(gcd{A[0]-A[i]}, gcd{B[0]-B[i]}, A[0]-B[0])
Correct! There's one optimization possible for the odd number of steps case - the condition you have can be simplified significantly.
ReplyDeleteAll elements in A are equivalent mod d, so there's only 2 cases: d = 1 or d = 2, A[i] are odd.
ReplyDeleteExactly :)
ReplyDelete