__builtin__wolfy's blog

By __builtin__wolfy, 9 years ago, In English

I was thinking about the following problem (I don't know if it's out there already) and wanted to know how people here would approach it.

You are given a N x M matrix and Q (say these values are <= 1000) transpose operations to execute each of which is a square sub-matrix to be transposed. Print the matrix after executing all operations.

Can we do better than brute force? My thoughts so far are: store the matrix as a list of diagonals. Transposing a sub-matrix is the same as reversing contiguous sub-arrays of some diagonals. The reversing can be done efficiently using lazy propagation but we still have to iterate over the diagonals of the sub-matrix. Can we do better?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

O(N * Q * logN) — the algorithm you described should be able to work in time, thou you may want to use Treaps (not segment trees) for reversing.