__builtin__wolfy's blog

By __builtin__wolfy, 5 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?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By __builtin__wolfy, 5 years ago, In English

Hello all,

Did you know that there is a connection between binary search trees and geometry? Check out this blog post of mine for details.

Feedback is welcome :)

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By __builtin__wolfy, 5 years ago, In English

Hello all,

I'm trying to solve this problem.

The correct output for the following test case (according to IO files) is "Unfair" but I can't figure out why. Could someone help?

Test case:

5
0 0
1 0
2 1
3 0
3 -1

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By __builtin__wolfy, 6 years ago, In English

Hello all,

This is my second blog post and this time it's about the splay operation in splay trees.

Feedback is welcome :)

Read more »

 
 
 
 
  • Vote: I like it
  • +14
  • Vote: I do not like it

By __builtin__wolfy, 6 years ago, In English

Hello all,

This is my first blog post on CodeForces and I wanted to share something I wrote with you. It's about a special type of graphs called chordal graphs.

Feedback is welcome :)

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it