Competitive Coding

Trees: All Branches One place Trees are hierarchal data structures built to store information that is connected to each other. As the name suggests, it is a tree, just upside down that stores data in its leaves and connected through branches .  So, this was the introduction, now let's see what we gonna cover in this blog: Applications of trees Binary Trees Traversals Some Trivial Questions The diameter of a binary tree LCA of Binary Tree Questions(Trivial) This is all we gonna cover. This part is not that much tough, but it's likely to get a little frustrating when it comes to trivial questions. (At least for me 😢 )

I thought it would be the right time for juniors and second years like me, to have some important dates in hand instead of just Mirzapur season release dates. So these are some sites, some annual hackathons, which I researched, and have compiled for you all, also, it includes some internships as well. So, get yourself some pen and paper, and let's start: Hackathons: Some important sites which conduct hackathons: Devfolio Devpost MLH Hackerearth https://www.hackathon.io/network http://www.hackalist.org/ Some important hackathons which occur annually: SIH Some important open source programmes GSOC

The Return of Number Theory  We covered in the First part: Primarily Test Prime Factorisation Sieve of Eratosthenes Binary Exponentiation Euclid's Algorithm for GCD Number of divisors/sum of divisors Segmented Sieve We would cover: Modulus Operations Binomial Coefficients Extended Euclidian Algorithm Diophantine Matrix Exponentiation Fibonacci in O(log(n)) Chinese Remainder Theorem Euler's Totient Function And these are the methods which we would cover only in theory, no questions in the fight: Pollard p-1 Pollard rho algorithm Modulus Arithmetic: Before jumping to the formulas for addition, subtraction, etc., firstly, let's have a look at what is M odular Congruence. Modular Congruences: a and b are modular congruent under n if they give the same remainder on dividing by n. Representation: a  ≡ b(mod n)   What that means is that wherever you are given a%n, you can replace it with b%n and it would have no impact no final answer, for example,  9=13 mod 4 (12+9)%4=21%...

An idea came to me today: let's talk about how to get ideas!  What should be the thought process when we are thinking of an idea.  We all want to make an impact and we all got some great ideas, some of us even take action to complete them, but only a small fraction of us actually succeed in making an actual impact. Let's see some of the rules we should follow: Write down everything! First and foremost, always have a pen and paper while brainstorming about the idea.  Think of the problem first, not the solution! Next, just think of the problems you are facing and how your idea is gonna be helpful for you. And the best part is, many great ideas are revolving just around you, you have to identify your problems and they should be the actual source of the idea.  Next, always think of a simple way out of the problem. Nowadays people are really smart and would only use your product/app/website if they feel that a great need. Making them pay for it is far more difficult. So,...

 Breadth First Search(BFS) Breadth first search's principle is quite simple, traverse level by level until we find the destination. Now, in a grid system we can traverse by making a radial expansion having center as the source cell. So you may see such visualization which is quite self explanatory. But how do you implement that? Algorithm: 1. Make a queue and push the source vertex in it.  2. while(q.length!=0) Pop the element from stack check if any of points  (x+1,y), (x,y+1),(x-1,y) and (x,y-1) are destination vertex. If yes: return If no: push  (x+1,y), (x,y+1),(x-1,y) and (x,y-1) into stack. Code:  class QItem { public : int row; int col; int dist; QItem( int x, int y, int w) : row(x), col(y), dist(w) { } }; int minDistance( char grid[N][M]) { QItem source( 0 , 0 , 0 ); // To keep track of visited QItems. Marking // blocked cells as visited. bool visited[N][M]; for (...

 Bubble Sort This is the most simple sorting algorithm. Just swap adjacent elements until the array is sorted. Like we have to traverse whole array n-2 times and in each traversal we have just this condition: check if the the left node is greater than right. If yes, just swap them. Time Complexity(Average, worst, best)= O(n^2) code(in C++): for (i = 0 ; i < n - 1 ; i ++ ) // Last i elements are already in place for (j = 0 ; j < n - i - 1 ; j ++ ) if (arr[j] > arr[j + 1 ]) swap( & arr[j], & arr[j + 1 ]); Insertion Sort Another Simple and intuitive algorithm, yet an efficient one. Its just the way we normally sort as "normal" humans. Suppose we are at some position of array, i, what we do is to take the element at the i th card and then swap it with the element it should be to make the array before i position ,sorted.  Time Complexity:  O(n^2)(Average and worst)  O(n)(Best case)(When array is alr...

STL: Standard Template Library(C++ Only) As you may have seen vectors now in Arrays, you might be wondering about more such amazing pre-defined data structures and methods. So here is a list of all such "magical containers" STL has to offer and when and how to use them. Introduction to STL: (All misconceptions) STL: Standard Template Library. STL is a library that gives us many predefined functions and "containers" to make our life much easier!  See, many of you now would be wondering: If there are such magical containers, then why learn things like linked lists and all which are quite difficult to understand and implement. Also, is using STL recommended, or is it just a "quick fix".  First of all, STL is not at all "magic". Every container is made by the creators of this library and we can and should use it to make code look a lot cleaner and easy to both understand and write. Secondly, the theory of ...