### EarthMessenger's blog

By EarthMessenger, history, 11 months ago,

You're given an integer n, answer the number of inversions in all the derangement permutations of length n. For example, if n = 3, there are two derangement premutations, 231 and 312, so the answer is 4.

There is such a sequence in OEIS. But I want to know how this is derived.

It's welcomed if you have other linear solution.

• +25

By EarthMessenger, history, 11 months ago,

Hello guys, I've made a short video editorial about the upcoming april fools day contest.

Video solution on youtube

• +68

By EarthMessenger, history, 17 months ago,

## Problem Statment

You're given a matrix of $N$ rows and $M$ columns, and $Q$ queries. $(1 <= N, M, Q <= 1000)$

For each query $(x, y, c)$, you need to rotate clockwise the square child matrix whose upper left corner is $(x, y)$ and lower right corner is $(x+c-1, y+c-1)$.

Print the final matrix as result.

## Sample

input:

4 5 3
9 9 3 4 5
5 0 2 1 3
9 3 6 4 3
5 9 3 9 0
1 3 1
2 1 2
2 2 1


output:

9 9 3 4 5
9 5 2 1 3
3 0 6 4 3
5 9 3 9 0


Obviously there is an $O(n^3)$ brute force algorithm which is not fast enough. Are there any solution faster than $O(n^3)$?

I guess the technique of dancing links may be useful.

thanks :-)

• +10