[Meetup] Square Root Decomposition Algorithm With Anudeep Nekkanti

If you were given a chance to add a new denomination(one that’s not in use today, but was perhaps used in past) to Indian currency, what would it be? And why?

Well, that’s the question that got everyone thinking , at the HackerEarth meetup on competitive programming with Anudeep Nekkanti.

We had invited Anudeep Nekkanti, an amazing competitive programmer from India, to a competitive programming meetup at HackerEarth. Anudeep was selected for the 2014 ACM ICPC World Finals in Ekaterinburg. Having bested a whopping 25000 teams at the National-level and State-level of Infosys Aspirations 2020 programming contests held in 2012. Anudeep could well be among the most talented programmers today.

He was happy enough to give us some insights into the world of competitive programming and what it takes to make it to the top. He talked about his experience at the prestigious programming competition in Russia. And he definitely made the meetup a gem of a session by speaking about SQRT decomposition in some detail and how it could be used to tackle problems at various levels.

What in god’s name is SQRT decomposition? ?

We all know how powerful the base 2 numbers are; they form the numeric system and that’s how we represent the numbers in computer systems too. See how versatile these numbers are, that we can form any decimal by using each of these powers just once.

The concept of doubling gives rise to log factor, multiples of 2’s, and to know that they are used in various concepts of programming like segment trees, binary search, square root decomposition etc and still we do not really realise it.  Square root decomposition is not as obvious as it should be.

Here are some excerpts from the meetup –

Talking about how to reach the top, Anudeep tells us, intelligence or ability to learn quickly, hard work and being persistence are the important skills to have. Well, of course, luck is one of them. It is all about striking the right balance. Competitive Programming is about learning new things and not giving up in frustrating times and staying in that uncomfortable zone. Well, what’s the point of walking every day when you are practicing running, right? That’s just how it is with competitive programming too. You need to try for the next level. If u have solved X number of problems, make sure to solve X + 1 as well.

In Competitive Programming, it’s better to break the problem into smaller problems, solve them in order, and think about the efficiency. This helps in better planning.It’s crucial to know when to go for help. Did you know that you can relate the Algorithm’s logic to real-world scenarios? see if you can get an analogy of that in the real world.

Without knowing it, people use most of the sorting techniques in their everyday lives, without realising,  for example, to find a word in the dictionary, almost everyone will go for a binary search as the dictionary is already sorted.Even the shopkeeper arranges his daily earnings by segregating the notes into heaps of 10s, 50s, 100s, 500s and so on, and then merges them, and they are sorted. That’s nothing but bucket sort. The clock too works on Modulo operations.

To solve a problem, it is important to understand the proof of the algorithm and the math behind it. There is math in everything and it’s crucial to know it, not that you need to be an expert in it. What is also imperative is that you  understand the logic of algorithms.

Anudeep explained square root decomposition in detail. Check out this video where ace programmer Anudeep tells you all you need to know about square root decomposition.