Thursday, January 13, 2011

A nice problem to test formal reasoning skills

Here's a problem that I think is easy if you're fluent with formal mathematical reasoning (and some facts from mathematics I don't want to reveal now :)), and close to impossible otherwise.

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.

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).


  1. 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").

    Any 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])

  2. Correct! There's one optimization possible for the odd number of steps case - the condition you have can be simplified significantly.

  3. All elements in A are equivalent mod d, so there's only 2 cases: d = 1 or d = 2, A[i] are odd.