Hello, I'm the writer of SRM 651.

It turns out this round is unrated due to some system failure. Sorry about the inconvenience it caused. I hope Topcoder can improve their infrastructure soon so that can be as good as codeforces.

I will post the problem statement, reference solution and a short editorial here.

Welcome to discuss the tasks, as well as to give feedback about them!

Problem Statement: http://www.speedyshare.com/2kRaC/task.rar

Reference solution:

Div1-Easy: http://ideone.com/a9siv1

Div1-Medium: http://ideone.com/sbEZSH

Div1-Hard: http://ideone.com/9JXoSL

Div1-Easy: RobotOnMoon

Look at this example:

....
.S.#
....

There will be infinite long perfect safe sequence, why? because we have "RRR...". That means if there is one '#' at any of the 4 direction of 'S', then the answer will be -1..

Then look at this example:

#.##
.S..
#.##
#.##

since there is only 1 cell to the left of 'S', there can be at most 1 'L' in any perfect safe sequence, otherwise if all characters other than 'L' are missing, it will lead the robot to die. So we can have a maximal bound of length of any perfect safe sequence: we have at most 1 'L', at most 2 'R', at most 1 'U' and at most 2 'D'. And we could find "LRRUDD" is perfectly safe: we have only 1 'L' so it is impossible to move outside the board from the left edge, etc.

So if the answer is not -1, then it must be n+m-2.

Div1-Medium: FoxConnection3

The key is notice that there can be few "shapes" of the result connected foxes. In fact if n = 6 there can be at most 216 of them: http://oeis.org/A001168

And then we should figure out which fox goes to which position in the final shape. There will be 6! ways.

Then we need to decide the position of our final shape.

After decide the position, we will calculate how many steps do we need to get it. It is simply the sum of length of shortest paths from s[i] to t[i] where s[i] is the start position of fox[i] and t[i] is the end position of fox[i], because we can ignore "there cannot be two foxes in the same cell at the same time." by this way:

Suppose we want to move O to x in this situation:

.O..o...o.x.

There are 2 foxes block our way, but we can do this:

.o..o...o.x. -> .o..o.....o. -> .o......o.o. -> ....o...o.o.

The if we write down the equation, it will be something like abs(offsetX — u[0]) + ... + abs(offsetX — u[n-1]) + abs(offsetY — v[0]) + ... + abs(offsetY — v[n-1]). We can find we should set offsetX = middle number of u[] and offsetY = middle number of v[].

Div1-Hard: FoxAndSouvenir

It will be quite easy to get a solution run in O(n^4) for each query, a classic DP:

dp[i] = how may ways to get exactly i dollar.

initially we have dp[i] = {1, 0, 0, ...}

For each souvenir of price p, we update new_dp[i] = dp[i] + (i-p>=0 ? dp[i-p] : 0).

So how to improve this? One observation is that this kind of dp can be write into convolutions:

for example, new_dp[i] = dp[i] x {1, 0, 0, ..., 1, 0, .., 0}.

Then one possible improvement is FFT with 2D segment tree, but it will need O(n^4 (logn)^4) which is too slow.

Another observation is that, we shouldn't do lots of FFT to merge segments again and again, for example, the answer will be {1, 0, .. , 1, 0, ..} x {1, 0, .. , 1, 0, ..} x {1, 0, .. , 1, 0, ..} ... We should first transform all of them into frequence domain, do the pointwise product of all of them. then transform back the result into time domain.

The last observation is it: we can transform {1, 0, .. , 1, 0, ..} into frequence domain in O(n) by bruteforce instead of O(n logn) by FFT, because we only have 2 non-zero values. And we just need one point value in time domain, so we can get it by brutefoce in O(n) instead of paying O(n logn) to reconver all elements in time domain.

So the solution looks like: preprocoss s[i][j][k] — the pointwise product of index k in frequence domain of the subrectangle [0, 0] — [i, j]. Then for one query we can find the frequence domain value of index k by calculate s[xMax][yMax][k] * s[xMin-1][yMax][k]^(-1) * s[xMax][yMin-1][k]^(-1) * s[xMin-1][yMin-1][k].

We should do the DFT over GF(1000000009). And we can avoid 0s in s[i][j][k] by use a length of an odd number. There are lots of divisors of 1000000008, we can choose 3507, the smallest odd divisor that is no less than 2500.