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

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...

Fibonacci Sequence: Running Sum

This article is in continuation of this one . R ecap In the previous article , I had tried to emphasize how nᵗʰ Fibonacci Number = Number of ways to climb n step staircase, where you have only two possible options to move, either by climbing 1 step or 2 steps at a time. In the same article, I have mentioned some other p ossible representations of the Fibonacci Sequence. One of them is the number of ways to tile a N x 1 board with a 1 x 1 square and 2 x 1 domino. By writing the recurrence relation for the same, we can state that NoOfWaysToTile(n) = nᵗʰ Fibonacci Number. Recurrence for the Tiling problem Tiling Problem Relation and Fibonacci Number Reversing the above Equation In this article, I am going to discuss my approach to the Running Sum Identity of the Fibonacci Sequence using the same relation. The Running Sum of Fibonacci Sequence The Left Hand Side (L.H.S.) The L.H.S. of the equation has 2 parts Fib(n) and (- 1) . Fib(n) = nᵗʰ Fibonac...

Chocolate in the Boxes

Counting problems have been irritating people for ages. They are generally long and weird with additions — substractions going on in different parts with meanings difficult to understand. Out of all the popular counting problems, one can be solved using some chocolates and boxes, which I am going to discuss in this article. The Problem For the given equation, find the number of ways such that a, b, c, d has a whole number solution, i.e. a, b, c, d ≥ 0. Most of you might know the formula for the pr o blem, here we are going to discuss a thought on how to tackle such a problem and formulate it as people find it tough to memorize and often forget. Before discussing further let’s see what the chocolate problem is. The Chocolate Problem Let’s say, we have 10 chocolates, that we need to put in 4 different boxes. It is assumed that all the chocolates are identical, and we are asked to count the number of ways to put the chocolates into the boxes. Putting no chocolates at all into the box is t...

My Board My Chalk

Search This Blog