Saturday, January 15, 2011

Solution to the alternating jumps problem

Let me remind about the problem: we alternate jumps to the left and to the right, possible jumps to the left are given as set A, possible jumps to the right are given to set B. Is any integer point reachable?

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

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

Tuesday, January 11, 2011

Codeforces Beta Round 50: how to avoid stupid bugs?

Today I've solved another Codeforces round, with very disappointing results. That was even more disappointing given the fact that the problems were very nice (and they are always both in Russian and English there - no excuse for you not to participate in the next round on Friday :)), and I was able to see the solutions quickly.

Two of my five solutions failed. The first one, for problem B, had this bug (here's a link to full solution):

036                    if (bx < 0 || bx * by > hblock * wblock || (bx * by == hblock * wblock && bx < hblock)) {
037                        bx = hblock;
038                        by = wblock;
039                    }

Line 36 must have "bx > hblock" instead of "bx < hblock": this is an implementation of the tie-breaker which asks us for minimal value, not maximal value.

The second one, for problem E, had this bug (here's a link to full solution):

067                double rc = Math.min(ra + Math.PI / 2, rb);
...                ...
070                if (rc > rb + EPS) {
071                    ++b;
072                else {
073                    ++a;
074                }

The condition in line 70 must be "rc > rb - EPS" or "ra + Math.PI / 2 > rb + EPS" instead of "rc > rb + EPS". This code iterates over two sets of segments, and needs to advance one of the pointers based on which segment ends first. I've even had the correct condition with "- EPS" in the beginning, but has found that this would shift pointer b in case of a tie. For some reason, I've decided that it's better to shift a instead to be on the safe side (now I realize it doesn't matter) - but changed the code in such a way that it will always shift pointer a!

What do you think is the best way to find such bugs during the contest or to not make them in the first place? I used to do the latter automatically, it looks like I need to improve in this area.