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 .

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

Definite way to develop programming logic Well,first of all what is programming logic exactly? According to me,it is the ability to efficiently apply programming constructs and techniques to solve a problem. So,the question now is, how do you develop programming logic? Almost every programmer starting out gets stuck in this vortex when you learn the basic constructs but have absolutely no idea how to apply them or how to make things with it.Today all your questions will be answered. Programming Techniques, Right now you're probabaly always approaching problems with a brute force ideology. Now: Start researching and learning techniques like - Divide and Conquer Dynamic Programming Backtracking Greedy Algorithms These techniques definitely will make your life easier as they provide you with new tools in your arsenal to approach problems Algorithms and Data Structures Algorithms and data structures are the most core of Computer Science . All the computation...

WHY USE PYTHON FOR COMPETITIVE CODING Well a very good reason is that python is a language which radically cuts short the time you spend writing code ,rather you could spend that time thinking about the logic that is needed for the question. In these kind of competitions speed is necessary,I am not talking about the speed of the language but rather about the speed of the programmer.Python syntax is extremely clutter free and elegant which allows us to not get tangled up in complicated details of a programming language. Python also has a very vast variety of tools in its standard library and these tools can be very well utilised in competitive programming. Here's a list of a whole lot of other reasons why you would want to use python: Common inbuilt functions: Python has common functions like count,min,max,sorted etc.These functions allow you to easily go ahead and skip writing code for these trivial procedures which often prove to be very helpful,rest assured: Pytho...