Solved all problems with Haskell. I really like your problems! :D :D :D

It was hard to find a solution during contest, but after reading the editorial the solutions were pretty clear and easy to understand. Also implementation was not diffcult. This is the first round I was able to solve all problems. Thanks for really well-made problems, alex256.

I compressed the range of input numbers to [1:n] and counted the number of swaps needed to make the array sorted in increasing and decreasing orders (what is so called inversion count) using Fenwick tree, and chose the minimum. But I have failed. Reading your explanation it seems you also calculated same thing. Would you let me know what's the difference?

code

I misunderstood the problem. It's that any two elements can be swapped, not two adjacent elements.

A path should contain exactly one of arrows in the picture. (there are A up-arrows and B right-arrows)

• The number of pathes that contain u1 is f(0,B+M-1)f(X,Y-B-M)
• The number of pathes that contain u2 is f(1,B+M-1)f(X-1,Y-B-M)
• ...

So, the answer is:

In fact it's wrong. I'm finding a new formula. But the idea was:

p = the number of pathes from (0, 0) to (A+1, B+1)
q = the number of pathes from (A+1, B+1) to (A+N-1, B+M-1)
r = the number of pathes from (A+N-1, B+M-1) to (X,Y)
the number of pathes can't be taken = pqr

To reach from (0,0) to (X,Y) you need to go right X steps and go up Y steps. Let's regard a step as an arrow. If there is no building, you can make combinations of X right-arrows and Y up-arrows. That's C(X+Y,X) or equivalently C(X+Y,Y).

Now, there is a building that covers (A,B) to (A+N,B+M). Let f(X,Y) be the number of combinations can be made with X right-arrows and Y up-arrows. That is, f(X,Y) = C(X+Y,X) = C(X+Y,Y).

Then the number of pathes is as follows:

f(X,Y) — f(A+1,B+1)f(M-2,N-2)f(X-A-N+1,Y-B-M+1)

• special case: f(x,y) = 0 where x < 0 or y < 0.

I don't understand your code but this is my iterative DP code. It took me some time to debug an out of array bound error :/

http://codeforces.me/contest/431/submission/20790745

Let the root's depth be 0.

dp[i][j][0]: from root to depth i, number of paths whose cost is j, and no edge has a weight equal or greater than d.

dp[i][j][1]: from root to depth i, number of paths whose cost is j, and at least one edge has a weight equal or greater than d.

The answer is the sum dp[1][n][1] + ... + dp[n][n][1].

I found the problem. it was modulo operation: for(int j = left; j <= right; j++){ dp[i][j] = j-1 >= 0 ? dp[i][j-1] : 0; dp[i][j] += (psum[min(MAXGAP, j + 2*k)] - (j - 1 >= 0 ? psum[j - 1] : 0)) % MOD; dp[i][j] -= (psum[max(0, j - 1)] - (j - 2*k - 2 >= 0 ? psum[j - 2*k - 2] : 0)) % MOD; dp[i][j] = dp[i][j] % MOD; }

When I calculate dp[i][101], it uses not dp[i][100], but (dp[i][100] % MOD). How stupid I was :(

I popped that final modulo calculation out to another loop and now it gives me correct answer.

I tried to implement your formula but it gives me some negative intermediate result. With dp[i][j] = dp[i][j-1] - sigmaA + sigmaB, I found that there are cases where sigmaA > sigmaB so dp[i][j] goes negative. Is my implementation wrong 'cause sigmaA > sigmaB will never happen technically or do I need special treatment for this case?

http://codeforces.me/contest/712/submission/20563138

My attempt to Div2 D (Ant Man). is it valid?

mark s as visited. start from s, find the next unvisited position with minimum jump cost. Let it be y1.

mark y1 as visited. start from 'y1', find the next unvisited position with minimum jump cost. Let it be y2.

... doing like this, we get a greedy path: s — y[1] — y[2] — ... — y[n-2] — e

For convenience we can say s = y[0] and e = y[n-1].

Let's assume this is not the optimal path. then there exist some i,j such that exchanging y[i] and y[j] decreases the total cost.

But exchanging y[i] and y[j] causes following change:

from

• cost[i-1, i] + cost[i, i+1]
• cost[j-1, j] + cost[j, j+1]

to

• cost[i-1, j] + cost[j, i+1]
• cost[j-1, i] + cost[i, j+1]

But

• cost[i-1, i] <= cost[i-1, j] for all j
• cost[i, i+1] <= cost[i, j+1] for all j+1
• cost[j-1, j] <= cost[j-1, i] for all i
• cost[j, j+1] <= cost[j, i+1] for all i+1

There is contradiction. Therefore the greedy path is optimal.

Haskell is only functional language I know.

Well just call me codeonwort :)