20 by 25

This post is a list of things I want to do by the time I finish 25 years. I am Inspired by a lot of people who shared their 30 by 30 list. 30 seems too far, and hence the 20 by 25 list.

I am 23 years and 140 days old, so I got 1 year and 7 months before I turn 26, that’s exactly 587 days.

So here goes the list in no particular order.

  1. Visit 25 different countries. (Been to 15, but in most cases I have been to cities in different countries. Want to experience it differently this time)
  2. Have lunch/dinner with Sachin Tendulkar (Really got to do this somehow!)
  3. Start an offline business. (emphasis on offline, not a social network for cats)
  4. Reduce body fat percentage to < 16% (Currently >25% :-()
  5. Build a toy house for my niece (DIY one, large enough in size to annoy my sister)
  6. Sponsor total education for atleast 25 kids
    Continue reading

Machine learning everywhere, why not in Competitive programming?

After reading the title if your first thought was like “ML model that is capable of solving competitive programming tasks?”, then this is going to be disappointing – we are not yet there 🙂

In this post I will write (and sort of prove) some ideas which uses ML and can help us build better competitive programming platforms, help us learn better. I will end the post with a bunch of ideas that are worth studying in deep. Let’s talk about some of the issues in CP platforms currently:

  1. There is no recommendation system – Would it not be amazing if you get recommendations for similar problems based on what you have already solved?
  2. Tags are mostly broken – Currently problems are tagged manually and there are multiple issues with this. Tags are high level. They tell if a problem has math involved or binary search involved but does not give us any information about what in math or how complex it is. There are a lot of problems with out tags.
  3. It is very common for beginners to get struck on problems. Currently they search for an editorial or short explanations. Many problems do not have editorials or explanations (spoj, lots of regional contests, other coding camp problems, etc).
  4. Also, in the case where an editorial exists, the programmer reads it and gets an idea of the whole solution. So that is a jump from 0 to 1. It would be better to give progressive hints on how to solve the problem, this will make them think more about the problem.

I believe 3 and 4 can bring a big change. A lot of programmers give up when they are struck on problems or when they are not able to learn. Likewise, 1 can help them solve more similar problems and understand the concepts better. In this post I will propose possible solutions for them.

Continue reading

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 almost none of the Indian programmers knew 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 an year and half back, but from then there is a spike up! We can expect more problems on this in future contests.

1) State a problem
2) Explain a simple solution which takes O(N^2)
3) Slight modification to above algorithm. It still runs in O(N^2)
4) Explain an algorithm to solve above problem and state its correctness
5) Proof for complexity of above algorithm – O(Sqrt(N) * N)
6) Explain where and when we can use above algorithm
7) Problems for practice and sample code

State a problem

Given an array of size N. All elements of array <= N. You need to answer M queries. Each query is of the form L, R. You need to answer the count of values in range [L, R] which are repeated at least 3 times.
Example: Let the array be {1, 2, 3, 1, 1, 2, 1, 2, 3, 1} (zero indexed)
Query: L = 0, R = 4. Answer = 1. Values in the range [L, R] = {1, 2, 3, 1, 1} only 1 is repeated at least 3 times.
Query: L = 1, R = 8. Answer = 2. Values in the range [L, R] = {2, 3, 1, 1, 2, 1, 2, 3} 1 is repeated 3 times and 2 is repeated 3 times. Number of elements repeated at least 3 times = Answer = 2.
Continue reading

When 2 guys talk, its not always about girls/sports ;)

Let me introduce to you my friend Archit Karandikar. I met him at Directi last summer, we were interns, since then we are good friends :). I was quite impressed with his skills. Many of us know that he is awesome at math and programming. Let me tell you, majority of the Indian programming community do not know him only because he does not take part in codechef long contests 😛

archit
Continue reading

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 : COTMKTHNUM

Consider the following question :

Given a linked list, you need to support 2 operations. 1) Update the first x values. 2) 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 of new linked list to (x+1)’th node of previous linked list. This way we allocated only x units of memory per update operation.

Consider the following example.

Initial linked list : 1 2 3 4 5 6 7 8 9 10.
Update 1 : x = 4, new elements : 12 13 14 15
Update 2 : x = 2, new elements : 20 21
Update 3 : x = 6, new elements : 1 2 3 4 5 6
Update 4 : x = 1, new elements : 100

Initial linked list will look like this

head[0]-->[01]-->[02]-->[03]-->[04]-->[05]-->[06]-->[07]-->[08]-->[09]-->[10]

After first update total data will look like this

head[0]-->[01]-->[02]-->[03]-->[04]-->[05]-->[06]-->[07]-->[08]-->[09]-->[10]
                                      /
head[1]-->[12]-->[13]-->[14]-->[15]--'

Continue reading

Heavy Light Decomposition

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

Why a Balanced Binary Tree is good?

Balanced Binary Tree
Balanced Binary Tree

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 reach root node from any other node
  • You need to visit at most 2 * log N nodes to reach from any node to any other node in the tree

The log factor is always good in the world of competitive programming 🙂

Now, if a balanced binary tree with N nodes is given, then many queries can be done with O( log N ) complexity. Distance of a path, Maximum/Minimum in a path, Maximum contiguous sum etc etc.
Continue reading