Competitive Python

Recently I came across a new website for competitive coding, Kattis and I love it. It is such an amazing platform and has a plethora of question along with multiple long duration contests. The quality of questions is also good and the interface is also very intutive. Follow this link to go to Kattis .

In this post we will explore and implement an algorithm which helps us verify that if the brackets are balanced or validly used. This is a very important application of stacks as a lot of programming languages use brackets very extensively in their syntax and one of the job of a compiler is to check if the brackets are balanced or not. For simplicity's sake we will just use a list with the methods append() and pop(). This will help us emulate a stack without actually needing to implement it. If you want to, you can go and learn about stacks on this link . A set of brackets can be called balanced if all of the brackets in it are properly matched. Examples of balanced brackets : (([]{}{})) ({{}}[]) Examples of unbalanced brackets : (([)]) {{}]}]]) So now getting to the algorithm, what we simply do is that we go through a string of brackets and check that for every closing bracket there is a properly nested opening bracket. This is how we do it - Convert the input string into a...

We are going to look at Dijkstra's two-stack algorithm and see how it's implemented. This algorithm is used to evaluate infix expressions. It uses stacks at its core, so if you don't know about stacks or if you'd want to learn more about them, click this link There are three types of expressions, Infix : Infix expressions are the ones where the operators are used between values, like a + b - c . Postfix : These are the expressions where operators are written after the values, like a b c +- , this translates to a + b - c in infix. Prefix : In these expressions, the operators are written before the values, for example + - a b c . This expression will also be equal to a + b - c in infix. Okay, so what this algorithm does is evaluate expressions like ( ( 3 + 4 ) * 83 ) . It starts by breaking down this expression into a list of stings and create two empty stack, one for housing the values and other for the operators. Then we go through the list one by one. Whenev...

Greedy Algorithms is an algorithmic paradigm just like divide and conquer is. It is a design technique that depends on locally optimal choices to produce an overall optimal solution. It makes a greedy choice at every step based on a condition and hopes that the choice it made will produce the most optimum solution. A lot of times this technique fails to generate algorithms that are optimal but it does make a lot of problems very very easy. Its used in several different algorithms, most famous of them being: Huffman Coding Dijstrika's Shortest path Kruskal’s Minimum Spanning Tree Greedy algorithms basically make up a solution step by step fashion choosing the next piece which offers the most immediate benefit. Some problems based on Greedy Algorithms are - Grocery Bagger School Assembly Boxing Chopsticks Receipt

Sieve of Eratosthenes is an algorithm that is used to generate all the primes up to a particular number . It is a very ancient algorithm but is very useful and also is a frequently seen in questions in competitive programming. This is a very elegant algorithm and is certainly better than trial division method . The idea behind this algorithm is to first select 2 and strike of all the multiples of because we know that they are composite. Then look for the next number that is not stricken off, it will definitely be a prime and then strike off all the multiples of that number. This goes on until the square of the number we select is greater than the limit that we assigned to it. As you will notice there is no need to go further because all of their multiple will already be stricken off by one or the other prime before it. To formalise the algorithm, it can be described as follows : Select the smallest prime from the list of all numbers upto n. Strike off all the multiples of the ...

A prime number is a number that is only divisible by 1 and the number itself. There are multiple ways we could test if a number is prime or not but today we will talk about two ways- Naive method sqrt(n) prime testing (the efficient method) The Naive method One method would be to check all possibilities from 2 to n - 1, n being the number we are testing. This would mean that if a number is prime we will have to search through all the numbers from 2 to n - 1. But if a number is not a prime then we will not have to search through all the possibilities, we will just return false if a number is completely divisible by another number that means it doesn't leave any remainder. def isPrime(n): for i in range(2,n): if n%i==0: return False return True The worst case for this method would be O(N). Sqrt(n) method Okay, so the logic behind this method is that every composite number has at least one factor that lies between 0 and the square root of n. ...

Recursion What is recursion Three rules of recursion Examples Fibonacci Factorial Additional Resources What is recursion? Recursion is a method of solving problems based on divide and conquer.It is a very elegant way to write solutions to problems that would be pretty inefficient in an iterative solution ( using loops ). A recursive function is basically a function that calls itself on a problem that is somehow smaller or more simplified than the original problem . For example see the function sum of list #Iterative Solution---> 1)def listSum( list ) : 2) sum = 0 3) for i in list : 4) sum += i 5) return sum 1)def listSum( list ) : 2) if len( list ) == 1 : 3) return list[0] 4) else : 5) return list[0] + listSum(list[1:]) In the iterative solution we go through each item in the list and keep adding it to the sum variable . But the same can be solved using a recursive solution . First, in line 2 we check for the base case,that is if the list is...