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.

Forgive me for my very noobish question but my initial thoughts about Div1 Medium was to ternary search on X-coordinate separately and Y-coordinate separately and get the answer.

Why does this not work?

I think this could work. :)

Doesn't work

Oh, sorry, it can't work because we have a[i]=a[i+1] for some i, so we can't use ternary search. The a[] may look like {..,9,8,7,6,5,4,4,4,4,4,4,5,6,7,8,9,...}.

For example you can't find the '1' in '000000001000000000000' by ternary search (if so that would be too crazy, right?).

Oh yeah, crap.

P.S: you mean to say "you can't find the '1'...." right?

Thanks a lot for the help. :)

Yes, fixed.

I believe there's a difference between 9,8,7,6,5,4,4,4,4,4,4,5,6,7,8,9 and 000000001000000000000. Since in our case only minimum can occur multiple times it seems everything will work. My code using this idea passes my tests, I only doubt if it runs fast enough.

I believe that the ternary search on X and Y is correct, but your solution doesn't seem to account for the hexaminoes portion at all. That is, it has the foxes all converge on the same square, instead of forming a connected hexamino. For example, in the test where all the foxes are in a line (already connected), the answer is 0, but you give 9, which is what would be expected if the foxes all had to touch the same square (then the distance is 2+1+0+1+2+3 = 9).

UPD: Ah, as CGY said, the ternary search might be wrong as well. But I believe the main issue is the hexaminoes thing (I tried a complicated sort of grid search, and was able to pass all of the provided tests, except my hexamino search TLE'd because I was doing it in a stupid way).

Yes, this is one more detail I totally screwed up. Thanks :)

Ternary search has been shown to be wrong by CGY but I feel that the bitonic nature of the problem should be possible to use somehow. :(

No problem!

The way I searched was to cut the grid into 64 squares, test the center of each square, and recurse on the best square (making the grid half as large, i.e. 4 by 4 squares, in order to give me a little room for error). This seemed to work on all of the problem statement's test cases (I was able to get the correct answers on my machine, and the grid search was always very fast, but my hexamino portion TLE'd as I mentioned).

EDIT: Oh, I forgot to mention: once this grid search returned a cell, I would try to place the hexamino anywhere in a 20x20 grid surrounding the cell, to account for small amounts of error.

Oh, in fact you can, because we only have a[i]=a[i+1] when we get maximal values.

You should write something like:

Can you also upload tests? It's not clear when practice rooms will be up.

It is hard to do that.

We don't have an "export to text" function in the system.

You can test your solution by run random data and compare result with the reference solution. (For Div1-Hard, if you pass the last sample and don't get TLE for maximal data then it has high probability to be correct, and for Div1-Med, random tests should work.)

Hmm, is sample #5 for 1100 right? It looks like this:

but I think that actually answer is 0.

I checked my samples, require is {0} in them. Do you really see {1}?

Yep, sorry, it was either a plugin bug or me editing this test case when I was debugging.

Does the idea of problems design of Div.1 hard come from New Year Shopping?

No, in fact I get that idea when I find the tree DP in 512D - Лиса и путешествие could be optimized to O(n^2) by DFT. (of course we didn't use that version in Round #290, the implementation is much more harder than today's Hard)

rng_58 told me we can use the same algoritm in New Year Shopping to solve 1D version of today's Div1 Hard in O(n^2 logn). But that solution couldn't work for 2D.

Could you do a DIV 2 tutorial ?

Div2-Easy: http://ideone.com/V1lc7O

First we find the position of 'S', then simulate it step by step.

Div2-Medium: http://ideone.com/uFdGNl

DP[i][j] := can we get a total of i dollar by buying j item?

Div2-Hard: http://ideone.com/TLoazT

First search all shapes (fixed polyominoes) of size k. Then try to place them on the board by try all offsets of x and y.

Could you please add some more details to the explanation of Div-2 Hard? More specifically, how to generate all the polyominoes of size 8 ? Through backtracking?

Why do zeroes disappear when we use odd length?

DFT({1,0,0,...,1,0,0,...}) = {1+r^(0*t), 1+r^(1*t), 1+r^(2*t), ...} where r^N = 1 mod 10^9+9, and t is the index of 1.

If N is even then we have r^(N/2) = -1 mod 10^9+9 that means we may get a zero at somewhere.

But if N is odd then there is no e such that r^e = -1.

You can also deal with zeros like this: we calculate both the product of non-zero values, and the number of zeros in rectangles from (0,0). By this way we can still calculate products of any subrectangle.

Thanks, this is such a wonderful problem, I would never imagine DFT can be useful without FFT.

There is another task that uses DFT but not FFT wrote by me a long time ago: SplittingFoxes2

I really like the theory behind the hard problem, though I'm not too familiar with number theory so I'm not sure how you would choose the constants.

Can someone elaborate on the number theory aspects of this problem? (i.e. looking over the code, it seems we chose "13" and "3507", and I would like to know the reasoning behind that). Thanks in advance.

13 is primitive root of 10^9 + 9.

We want our N to be:

among them, 3507 is the smallest one.

You can read this: http://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)#Number-theoretic_transform

Ok, I see, that makes sense. Thanks for the response :)

If N were equal to 2500, we would lose the last coefficient (number of ways to spend 2500), so we want N larger than 2500, no?

Oh you are right, fixed. Thanks for pointing this out.

Can we do the same if module M is not prime?

UPD: It seems that we can do that, but it's not easy to find generator with order d.

On Div1 Medium: "Then we need to decide the position of our final shape."

Can anyone give me a hint on this step?

Tried to upsolve SRM 651 Div1-hard. Get following result for test 6 for solution in c++. http://paste.ubuntu.com/10550162/

Then copied bad test to test-code of kawigi.Edit, and no problem was found. My code with tests: http://paste.ubuntu.com/10550152/

Could you please explain what is the problem? Is there another bug in my code or bug in topcoder checker? It seems strange that in verdict there was no RE and that I did not return any vector as answer in this case.

I've got the same. And I think that the problems is on server side.

Will the problem statements be available on the TopCoder problem archive?

I can see all problems from SRM 650 and 652, but 651 problems are all missing.