Ну вообще без палева — боян с полуфинала.

I guess their solutions used wrong assumptions, which leads to wrong solutions, which can be easily challenged with big random tests.

It's not that surprising — the first thing to expect is a greedy strategy, and many such strategies can be invented, but it doesn't actually work.

Firstly, only relative positions of corresponding rings of the lock matter, so you can replace pairs of (original,target) positions by just their differences D₀[i]. You can add a correctly placed ring to the left of the lock and transform the sequence of differences to a new one: D[i] = D₀[i] - D₀[i - 1] (mod 10). In this case, an operation is just adding 1 to D[i] and subtracting 1 from D[j] for any pair (i, j), or just adding/subtracting 1 from D[i] (that corresponds to rotating several rings at the right side of the lock).

We want to convert the array D to all zeroes using a sequence of operations; the order of operations doesn't matter. If we'd add 1 to D[i] and subtract 1 from D[k] (or from no D[k]), and at some other time subtract 1 from D[i] and add 1 to D[j] (or to no D[j]), it can be replaced by one operation, for example (D[j], D[k]). That means we only rotate each ring in 1 direction.

Let's sum up D[i] of rings which are rotated up, and sum up 10 - D[i] of those rotated down; denote them as x and y. The answer is obviously , and x - y is constant (), so if we could find all possible x, we could obtain the result quite easily. And x < 10N, so it's now clear that a DP works. Let dp[i][j] be  > 0 if j is a subset sum from the first i entries of array D, 0 otherwise; dp[i + 1][j + D[i]] = dp[i][j + D[i]] + dp[i][j].

The time required for this is O(10N²); it can be cut down by half if we're not interested in j + D[i] for j > 5N (because then we just have y > x, and we don't want even larger y); it can also be cut down on memory to O(10N) if we only remember the last 2 rows of the array. I haven't coded it during the contest, but it should pass.

That's normal on topcoder, they can't make the input string too big because challenges are not like codeforces where you can upload a generator or something