Persistent Centroid Tree

I have described about Centroid Decomposition in my earlier blog post (original @ quora). I had authored a problem on codeforces which involves a nice reduction of making the centroid tree persistent, which enables us to perform more powerful operations in sublinear complexity. I call the trick Persistent Centroid Tree. This article is to give some visibility to the problem and the trick explained by me in the editorial of the problem.  The links to the problem and the editorial are given below.

Problem: https://codeforces.com/contest/757/problem/G

Editorial & Explanation: https://codeforces.com/blog/entry/49743

If you have seen problems that require a similar trick, or can be solved more efficiently using this trick, please comment below and I’ll create a list here.

Happy Coding!

Online FFT

Link to pdf slides.

Kindly comment below for any mistakes/typos in the slides and I will try to fix them.

 

Problems for practice:

http://codeforces.com/problemset/problem/553/E

https://csacademy.com/contest/archive/#task/jetpack

https://csacademy.com/contest/round-24/#task/colored-forests

Dominator Tree of a Directed Graph

Link to pdf version.

Introduction : In this article I am going to explain the concept of Dominators in a directed graph, its applications and an efficient algorithm for construction of dominator tree published by Robert Tarjan [1].

Since there is a lot of content to be covered, the post is going to be a bit long. So, please be patient. 🙂

Pr-requisites : dfs in directed graphs. DSU

Centroid Decomposition of a Tree

Introduction : Centroid Decomposition is just a divide and conquer technique which is used on trees and turns out useful in many problems. It is also known as “Separator Decomposition”. In this article I will first explain How do we do centroid decomposition followed by it’s applications (i.e. Why do we do it ? ) . In the end, I will discuss a few problems that can be easily solved using centroid decomposition.
So, let’s begin 🙂

Pr-requisites : Basic graph theory. DFS . (Basic) Divide and Conquer.

Treaps : One Tree to Rule ’em all ..!! Part-2

Introduction : This is a continuation of my article on treaps (Link to Part1 ). In this article, I would be covering Implicit Treaps.

Pr-requisites : Basics of treap(covered in part1). Interval trees (like segment tree or fenwick tree).

 

Treaps : One Tree to Rule ’em all ..!! Part-1

Introduction : Well, don’t get too much carried away by the title of the blog. By the end of this article you shall realize the motivation behind it. 🙂
So, let’s begin :

Pre-requisites : Binary Search Tree and Binary Heap.

The “Bridge Tree” of a graph

Introduction : Bridge Tree is a term coined by me that refers to the tree formed by shrinking 2-edge biconnected components of the graph . The 2-edge biconnected components shall be referred to as “bridge components” in the further post. The concept is very intuitive so let’s see more about it.

Pre-requisites : Basic Graph Theory. Dfs and Bfs .Bridges in a graph. Biconnected Components and Block-Cut Tree (not really needed to  understand but experience with this would be helpful in easier imagination :))