I think it's really a matter of psychology/experience with programming competitions and how TC problems (IIRC just recently) don't conform to it.

It's easy to make small mistakes when coding, especially with easy standard problems with easy short implementations, where we don't tend to pay attention to every bracket. The very reason why multiple samples / pretests / full feedback / no time penalties / subtasks / you name it exist is to decrease the impact of these small bugs on the final result — you're either free to test your code more, or submit it and get it... checked at the cost of small penalties. The more contests you do, the more you're able to utilise this.

When there are 5 samples, 2 of which are trivial and the other 3 random, passing them actually gives you hope that your solution is correct. You don't just miss possible bugs, you're told to not look for any (so to speak). Gee, what a surprise when 70% of all submissions fail.

To reply to Mimino's profile quote on TC, the game is rigged against us :D

You mean like all solutions that have a small bug that can be easily fixed? That's not a good idea.

Not too long ago, I used characters A instead of Y (as what's supposed to appear on the input) and it still passed all samples. Why even have them, why not make it fully blind coding? Because that's what it effectively is.

Also, my short experience as TC problemsetter includes: nobody cares about the content of tests.

The problem I am going to describe is that of determining whether the translation (tx, ty) can be obtained as a combination of several shifts along the sides of a triangle. The reduction from the original problem to this one is described somewhere above in this thread.

Notice that any two sides of the triangle suffice because the third one always can be expressed as their difference and we are not interested in optimizing the number of translations.

Suppose the triangle is degenerate. Then the problem is essentially one-dimensional and we are interested if our (tx, ty) point can be reached from (0, 0) using the smallest step we have in our disposal (viz. the greatest common divisor of the lengths of our two triangle sides, though be careful not to introduce fractional numbers). That is of course if the corresponding vector is parallel to the line that our triangle vertices are on.

Otherwise, the affine transformation

maps the triangle (0, 0), (a, b), (c, d) to (0, 0), (1, 0), (0, 1) and preserves point-line incidence so all that is left is to check whether the image of (tx, ty) has integer coordinates.

The general question is this: Can you represent a vector v by an integer combination of vectors from a set S?

Since we're only dealing with two dimensions (though we can do n-d with this), we should be able to represent the whole set of obtainable vectors by choosing at most two appropriate combinations from S. This is intuitive since we can do this if we're allowed to take linear combinations, but note that we're dealing with something more restricting here.

If we had linear combinations, we'd do Gaussian elimination. So we'll do something similar here. The idea is to apply Euclid's algorithm to each dimension in order. Here's what I mean: as long as there are at least two vectors with non-zero x-coordinate, we apply the Euclid's algorithm to two such vectors until one x-coordinate becomes zero. Once there is only one such vector (or maybe none) we proceed to y (excluding the vector with non-zero, if it was found, from further consideration).

In the end, since there are only two dimensions, we'll have at most two non-zero vectors. Since the operations we applied are reversible, the two vectors obviously represent all the possible integer combinations of the initial set. Also, at most one of the vectors has a non-zero x-coordinate, so it's easy to check whether a vector v is a combination of those two vectors (the x-coordinate must come from the one with non-zero x, and the rest comes from the one with zero x).

In comments above you can see good analytic solutions (honestly, I am not so good at math, so it took some time for me to understand them, but now it seems that i've got it; thank you, guys:) ).

During contest I used a naive brute-force. I'll describe it here. This solution is ugly, but requires less math :D Let's assume that you already fixed unpaired mirroring operation, or you don't have unpaired mirroring operations at all. Now you want to solve a*v1+b*v2+c*v3=v4, where a,b,c are integers, a+b+c=0; v1, v2, v3, v4 are vectors. Looking at constants, first idea is "I see 10^6 instead of 10^9, it means that there is a naive solution with brute-force". Trick is — if there are no solution with at least one "relatively small" coefficient, then there are no solutions at all. Let's assume that a is small (and later just copy-paste same solution for b and c). In this case you can try all possible integer values of a, and for fixed value you have new equation b*v2+c*v3=v5, where b+c=A. Now you can set v6=v2-v3, and get even easier equation — A*v2-X*v6=v5. This is a linear equation with a single variable X:) You just have to check that values of X are integer and equal for both coordinates.

But there is actually 2 variables if you look more attentive