When we first approach this problem, the alternating jumps condition restricts our thinking, so the natural move is to get rid of it. How? Let's pair up the jumps to the left and to the right. Then we have a new set of possible jumps C = {b - a, for b from B and a from A} that consists of all differences between B and A. We can then jump by numbers from C arbitrarily, so the sub-problem that we need to solve is:
Given a set C of integers, which integer points are reachable if we jump by numbers from C starting from 0?
This is where you have to apply the previous knowledge. More specifically, the fact we're interested in is: given a set of integers C = {c1, c2, ...}, their greatest common divisor g (the largest positive integer that divides every number in C) is representable as g = q1c1 + q2c2 + ... where q1, q2 and so on are integers.
This fact is about what we need to solve our sub-problem. First, we note that every integer point that is reachable by jumping by numbers from C is divisible by g (as a sum of several numbers divisible by g). What we hope for is that the reverse is true as well: every point divisible by g is reachable.
The above representation of g = q1c1 + q2c2 + ... almost gives us the strategy to reach point g: each qi means the number of times we jump by the corresponding amount ci. The only problem that some qi may be negative, and we can't do a jump minus one times.
Now the question is: take one number c from C. How do we jump by -c? If we can do that, we can use the above formula to reach point g. Let's consider the case where c is positive. Here's where we need another non-trivial idea: let's check if there's any negative number if C. If not (all numbers in C are non-negative), it's obvious that we can't reach -c (or any other negative number). However, if there's a negative number -d in C, we can reach -c by doing the -d jump c times, then doing the c jump d-1 times: -d*c+c*(d-1)=-c.
In case c is negative, a similar argument shows that if there's a positive number in C, then we can reach -c, otherwise we can't reach any positive number.
Let's summarize the result that we've arrived at. If C has at least one positive number and at least one negative number, then we can reach point g. We can reach point -g in the same manner. But then we can reach any point divisible by g by repeating the sequence!
Having (almost) solved the sub-problem, we return to the main problem. The solutions for the sub-problem correspond to the points that we can reach after an even number of steps. What about points reachable after an odd number of steps?
First, consider the case where C is "bad" - has only non-negative or only non-positive numbers. We know that not all points are reachable via even number of steps. Moreover, we know that a lot of points are not reachable via even number of steps: all positive points or all negative points. But then it's obvious that not all points are reachable via odd number of steps as well: if we'll always be at a non-negative point after an even number of steps, one more step can only bring us this far into the negative half of the line - so all numbers below a certain value (minus maximal element of A) are not reachable, and the answer to the main problem is "NO".
Then, consider the case where C is "good". We know that every number divisible by g is reachable via an even number of steps. What does one more step (subtracting a number from A) change? We can reach every point that has the same remainder of division by g as minus number from A. But what remainders of division by g can numbers from A have?
Since g = gcd(a1-b1, a2-b1, ...), then a1-b1 and a2-b1 are divisible by g. But then their difference, which is a1-b1-a2+b1=a1-a2, is divisible by g. Similarly, the difference between any two numbers in A is divisible by g. So all numbers from A have the same remainder x of division by g!
We've finally summarized all numbers that are reachable: those divisible by g and those that have the remainder of g-x of division by g. When does that cover all numbers? When g equals 1, or when g equals 2 and x equals 1. With larger g, some remainders are not covered. With g equal to 2 and x equals 0, odd numbers are not covered.
We're almost there - here's what we have now. When all number from C have the same sign, the answer is "NO". Otherwise, if g is the greatest common divisor of C, then the answer is "YES" if and only if g equals 1 or g equals 2 and a1 is odd.
The only problem is that C may have too many elements: when A and B have 10000 elements each, C may have as many as 100 million! The last step is to notice that we don't need to find C. All we need to know is:
- does C have a positive number?
- does C have a negative number?
- what is the greatest common divisor of all numbers in C?
The first question (and the second one similarly) is answered easily. C has a positive number if and only if the largest element of B is larger than the smallest element of A.
And the last question can be answered using the trick mentioned above. Consider an arbitrary element of C: ai-bj. Since we already know that differences between numbers in A (or numbers in B) are divisible by g, we can represent this number as the sum of three numbers divisible by g: ai-bj=(ai-a1)+(a1-b1)+(b1-bj). That allows us to consider the greatest common divisor g1 of the following set C1 of numbers: a1-b1, ai-a1 for all i, and b1-bj for all j, and prove that g1 equals g. This is easy: g divides g1 since g1 is the greatest common divisor of numbers that are differences of numbers from C. But g1 divides g for the same reason: every number in C is a sum of three numbers from C1! So g1 equals g, and we can find g as the greatest common divisor of C1 which has at most 20000 elements.
Phew! This was a long solution, not because it's complicated, but because it has many steps that have to be carefully executed. Each particular step is either obvious or represents a relatively easy mathematical fact. However, in order to successfully walk the entire path and not make any mistake along the way (take a look at the contest results: the problem in question is problem A) you have to be really careful and have a good understanding of where you are and what is left to prove. That's why I said this problem is really about formal reasoning skills.
To spice up the long textual post, here's a picture of our Moscow State University team at the ACM ICPC 2003 World Finals in Beverly Hills (by David Hill, from the official World Finals photo archive):
