Skip to main content

Contact

Name

Email

Message

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

Climbing the Fibonacci Sequence

  Climbing Staircase Problem T he Story begins with a Problem Yesterday, I was solving a very famous DP problem,  the climbing stairs . The problem is quite simple. You are climbing a staircase. It takes  n  steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Solution The solution is also pretty straight forward. Suppose we have climbed up some steps and we are left with some  i  steps to reach the top. Let’s say,  NoOfWays(i)  be a function that returns the number of ways to climb  i  steps to reach the top. If we climb by 1 step, then we are left with (i-1) steps. Using the above formula, the number of ways to climb (i -1) steps = NoOfWays(i-1). Similarly, if we climb by 2 steps, then we are left with (i-2) steps, and using the formula, the number of ways to climb (i -2) steps = NoOfWays(i-2). Since we can climb in one of the two fashions only so the number of ways...
Post a Comment
Read more