Skip to main content

The Underestimated Power of Integer Sum

 There are a few grouping styles that are common in competitive programming to optimise the solution time complexity.

  • Grouping by the powers of 2
  • Grouping by a fixed bracket size

Out of these two, the second one has a special group size, i.e. make the fixed bracket size equal to the Square Root of input size, N.

Solving techniques like Square Root decomposition, are actually based upon this grouping style. For example, you want to compute some property for a subarray that can be calculated using N² complexity only. But if you could figure-out some special property that allows you to merge two blocks of the same array, you can compute for √N size block then, merge √N blocks using the merging technique.

But this article is actually not about square root and square root decompositions.

The problem, I want to address here is related to streaming input, i.e. some query oriented problem that adds a new element to the existing set of input and asks us some result of a query. Something like that.

Suppose you found out that grouping could help here but what will be the grouping size. If you could use a fixed size like 100, 1000, 2500 etc it's well and good, but in a case, the size has to vary with the number of elements currently in the input. How will you deal with such a scenario?

I have a hint, I am not sure if it will help in your scenario or not but you can try. You can make the current group size =previous group size +1, taking the initial group size = 1. And you add a new group every time you exhaust the current group.

1 + 2 +3 +4+5…… = N

What will be the total number of groups in this case?

Well, this will be answered by using the integer sum formula.

suppose, we have 1 + 2 +3 +4 + 5 …. k = N

then we can say that

( k * (k + 1) )/ 2 = N

and using approximations we can conclude that k almost = √N

This makes the total number of groups = √N

and also the group size = √N

Cool, Right?

This simple technique can be used in so many streaming techniques which can help in making the group size dynamic and easy to handle.

Comments

Post a Comment

Popular posts from this blog

CodeChef March Challenge 2021 — Consecutive Addition

“You are given two matrices A and B, each with R rows (numbered 1 through R) and C columns (numbered 1 through C). Let’s denote an element of A or B in row i and column j by A(i,j) or B(i,j) respectively….. ” You can read the whole problem here . Problem description in short Given two matrices, A and B. Task is to transform A to B using special some addition-based criteria. The criteria for transformation is as follows we are given a number K 2 ≤ K ≤ min(R, C), where R is row size and C is column size we have to take any submatrix of size Kx1 (i.e. along the column) or 1xK (i.e. along the row), in A, and to all the numbers that fall under that submatrix have, add some integer v, this can be chosen by us. This has to be done in such a way that finally A transforms to B. The actual problem is to check if this kind of transformation is possible, given A and B. Ideation…. Befor e  I begin I wanna say that it is an observation based problem, can have many solutions and my solution is no...
2 comments
Read more

Solving a Tree Problem

Balanced Binary Tree T ree problems are quite popular among competitive programming questions.  A ll the fame  is because of the co mplexity of thought they deliver to the mind of a beginner and sometimes they even scare the intermediate programmers, who have been programming for a while. Here in this blog, I will discuss a general problem that has similar complexity issues and share a thought to break the solution. Some Prerequisites Sites all over the internet are filled with basic level tree problems like Finding the depth of a node in a tree Finding the height of a tree Sum of a subtree rooted at some internal node of the tree Finding LCA (Lowest Common Ancestor)of two nodes of a tree (in O(N)) Finding LCA of any two nodes of a tree (in O(logN)) Generally speaking, all such problems are the building block for the tree-problems of intermediate level, like one discussed below. A Generic Problem The problem starts with a description of a tree and clearing out what all kind of...
Post a Comment
Read more

What is 'Is this the Reason?' or ITTR?

This is my plan. Nothing is done yet to put it like a series where all the posts that belong to this series are styled in a way to SPECULATE the reason for something. I know you might be not convinced with the idea but things will become clear as you read the posts. More or less the Idea will be here to put up a question and then trying to guess any obvious or not-so-obvious reason behind that. Can be factual can be imaginative and definitely intuitive. The fun will become multifold with the engagement of readers as new brains mean new ideas mean more speculations. That it. :) See you there!
Post a Comment
Read more