Zhtluo's blog

By Zhtluo, history, 2 months ago, In English

Consider this famous necklace counting problem:

Assume a necklace can be made with $$$n \ (1\le n\le 10^5) $$$ beads. Each bead can be painted with one of the $$$ k\ (1\le k\le 10^5) $$$ colors. We consider two necklaces the same if after rotating and flipping they look identical. How many different necklaces are there in total?

The solution to this problem is often represented in terms of group theory jargon. In this post we will try to explain and demystify the process.

Just wrote a short tutorial on Polya's Theorem as I tried to figure out how to explain it to people without background on group theory. I am not exactly a mathematician so there might be errors and inaccuracies. Any feedback and suggestion would be greatly appreciated. Enjoy :)


Full text and comments »

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

By Zhtluo, history, 11 months ago, In English

Are you scared when you hear about all these pesky data structures like Fenwick Tree, RMQ, Segment Tree in competitive programming?

Are you afraid of writing code to solve problems like finding the minimum, maximum, or sum of some range query, especially when there are updates to the data?

Well, fear no more! In this tutorial I will introduce the Swiss knife of all sequence manipulation data structure, one code that can (theoretically) solve every problem of this kind, one tree to rule them all — the Splay Tree!

So this is a tutorial I wrote on the Splay Tree:


Feedback and additional practice problems are welcomed. Enjoy :)

Full text and comments »

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