CommonLounge

Categories

Message

Follow

Anudeep Nekkanti

Past: Competitive Programming, Algorithms. Present: Googler turned Entrepreneur.

Active In

International Olympiad in Informatics

Member

Artificial Intelligence

Member

Deep Learning

Member

Startups

Member

Featured Contributions

Contributed 100%

2.

tutorial

MO’s Algorithm (Query square root decomposition)

Once again I found a topic that is useful, interesting but has very less resources online. Before writing this I did a small survey and surprised that most competitive programmers do not know this algorithm. Its important to learn this, all the red programmers on Codeforces use this effectively in Div 1 C and D problems. There were not any problems on this topic an year and half back, but after that there was a spike! We can expect more problems on this in future contests.

- State the problem
- A simple solution which takes O(N^2)
- Slight modification to above algorithm, still runs in O(N^2)
- MO's algorithm to above problem and its correctness
- Proof for complexity of MO's algorithm – O(sqrt(N) * N)
- Explain where and when we can use above algorithm
- Problems for practice and sample code

Read more…(1463 words)

Category: Competitive Programming

Contributed 100%

3.

tutorial

Persistent segment trees: Explained with SPOJ problems

In this post I will introduce the concept of persistent data structures. We shall deal with a couple of problems: COT, MKTHNUM

Consider the following **question**:

Given a linked list, you need to support 2 operations.

- Update the first x values.
- Print the linked list after k’th update (k <= number of update operations made till now)

Simple solution is to create a new linked list after each update operation. print it when needed. Let us optimize it for memory.

We are only updating first x elements of the linked list. That means the new linked list will be almost same as previous linked list if x is small. We shall take advantage of this and avoid allocating memory for some elements. We can allocate memory for x elements, store new values in them, then point the next pointer of x’th node...

Read more…(1718 words)

Category: Competitive Programming

Contributed 100%

4.

tutorial

Heavy Light Decomposition

This is a long post with lot of explanation, targeting novice. If you are aware of how HLD is useful, skip to “**Basic Idea**”.

A balanced binary tree with **N** nodes has a height of **log N**. This gives us the following properties:

- You need to visit at most
**log N**nodes to r...

Read more…(2701 words)

Category: Competitive Programming

Load More