Competitive Python

In this post we will go through the basics of generating random numbers and also see how they can be generated within a range along with best practices. Java provides support to either generate random numbers through java.lang.Math package or java.util.Random . Using java.lang.Math There exists a static method inside this class, Math.random . It is very convenient to use and returns a double between the range 0.0 and 1.0 i.e. it returns a floating point number between 0 and 1. public static void main(String[] args){ double randNum = Math.random(); System.out.println(randNum); } Random number within a range - To generate a random number within a range we need to further process the number returned by Math.random() public static void main (String[] args){ double min = 10.0; double max = 100.0; double randNum = randRange(min, max); System.out.println(randNum); } public static double randRange(double min, double max){ double x = (Math.rando...

This article is divided into 3 parts, so feel free to skip around to the part you find useful - Need for the algorithm Intuition and Algorithm Implementation Need for the algorithm Multiplication is an elementary concept known to all of us since a very early age. But multiplication of very large numbers becomes a difficult problem that can't be solved mentally unless you're a mathematical genius and hence we use calculators and computers. Computers too can efficiently multiply numbers but as the length of digits of the number increases, the time complexity also increases along with it quadratically. To calculate the product of humongous numbers we need a better algorithm. Any algorithm that even slightly increases the runtime will prove to be very beneficial for large values of n, say 100000. Karatsuba multiplication algorithm brings down the number of operations by a factor of one and gives a huge boost. Intuition and Algorithm Okay so, to boost up the speed of...

Tuple is a linear data structure which more or less behaves like a python list but with a really important difference, that a tuple is immutable . Immutable means that this structure can't be changed after it has been created, it can't be mutated if I may. Tuples being immutable are more memory efficient than list as they don't over allocate memory . Okay, so what this means is, when a list is created it takes up and reserves extra spaces of memory than needed for the original elements as new elements might be added to the list later and allocating memory on every addition would be quite inneficient but tuples, once created surelly won't change the numbers of elements in it later on, so it allocates exactly how much memory is needed. Almost all the list operations work for tuples except the ones which mutate it, for example, insert, append, remove etc. Declaring a tuple : Tuples can be initialise in a manner similar to list, But there's an important c...

Lambda functions are simply functions that don't have a name. They are also called anonymous functions and are pretty useful for certain cases. They are extensively used in functional programming . Lambda expression is useful for creating small, one time use functions though the functions can also be given a name. It can have multiple arguments but just a single expression as the function body. The basic syntax to create a lambda function is lambda arguments: function body For example lambda x : x **2 This function takes in x and returns x 2 . Here, lambda is the keyword, x is the argument and the expression after the colon is the function body. These functions can also be given a name, sqr = lambda x : x **2 sqr(5) #output : 25 Multiple arguments can also be provided lambda x,y: x * y or lambda x,y,z: x*y*z These functions when given a name are equivalent to the functions defined by using the def keyword. For example def solve_quad(a,b,c): d = b**2 - (4*a*c) x1 ...

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

If you want to learn about Stack or Queue, follow the link to the tutorials- Queue Stack Questions- Maximum Element Equal Stacks Balanced brackets Simple Text Editor Queue using two stacks Castle on the grid Stock Span Problem Celebrity Problem Next greater element

Today, we will talk about another linear data structure , a Queue. It is a data structure thay basically acts like a real life queue. It works on FIFO (First in First out) principle. It means that the element that gets added to the queue first gets removed the first, it's like first come first serve basis.In a queue, the operations take effect at rear and front end of the list. Enque adds the element to the back of the queue and Dequeue removes the element from the front of the queue. Queue is a very essential data structure and also form the basis for some advanced data structures. Applications of a queue- CPU procces scheduling Real life simulations The methods associated with a queue are - Enque(): Adds an element to the back of the queue Deque(): Removes an element from the front of the queue isEmpty(): Returns wether the queue is empty or not size(): Returns the size of the queue Here is the implementation of the Queue data structure, in this implementation we...

Stack So, now we're going to talk about stack , a linear data structure and also we will see its implementation. In another post which will be linked below later will discuss its uses. So what is a stack ? Visualise a pile of coins or a stack of trays put one over the other. The item that has been put at the last has to be removed first as it is over all the other items. Hence, it is a data structure that works on LIFO (Last in First out) principle. Which simply means that the element that has been added the last will be removed first. It is a very useful data structure and has several applications like expression evaluation and HTML validat or or a bracket matching verifier . In this data structure we only have operations that take their effect only at one end of the list. Both, the front or the end of a list can be used to implement it but using the tail(back-end) of the list is more efficient. The main operation or methods on a stack are - Push : Adds element at the...

Sorting Why do we need to sort? Merge Sort Quick Sort Why do we need to sort? Sorting is among the most important, and well studied, of computing problems. Python does have a built in method for sorting a collection but it is very advance and highly optimised, it's known as timsort , even java's inbuilt sorting method uses this algorithm. A programmer should usually depend on built-in sorting functions than rolling out a search algorithm from scratch. But with that being said it is still imperative to have a deep understanding of how sorting algorithms functions as it makes you more and more aware about your program in terms of efficiency and space complexity We will see and study two of the quicker sorting algorithms, mergesort and quicksort .Both these algorithms work on divide and conquer design pattern. Merge Sort Merge sort is a recursive algorithm.It works by splitting the list into half and then calling mergesort on both the halves independently. Once the two...

Binary Search Okay, so how do you think we can search for a paticular element in an array? One obvious way will be to loop through the array and return true at which the element is found and to return false if it doesn't exist in the array. But the problem with this algorithm known as linear search is that it can very quickly turn out to be very costly in terms of space and time as this algorithm takes O(n) or linear time. This turns out to be highly costly for a large number of elements in an array. #Linear Search --> def linear_search(array , n ): for i in array: if i == n : return True So, the solution to this is to use an algorithm called binary search . Binary search is an algorithm that works on the divide and conquer technique and is also extremely efficient.It works on O(logn). But the only catch to this algorithm is that the array it is being applied on needs to be sorted . #Binary Search --> def binary_search(array, n ): #Setting up search ...

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

Divide and Conquer Divide and Conquer is an algorithmic paradigm used in many problems and algorithms . Some of the most common algorithms use divide and conquer principle and are highly effective. A Divide and Conquer algorithm solves a problem in 3 steps : Divide: Break the given problem into subproblems of same type. Conquer: Recursively solve these subproblems Combine: Appropriately combine the answers It starts of by breaking down a problem into multiple parts that are simple enough to be solved and then all these subparts are solved individually. For the last part , the algorithm combines all the solutions into one. Some common examples of Divide and Conquer in algorithms are - Binary Search Merge Sort Quick Sort Divide and Conquer is the principle applied to recursion and thus it is a very important technique and is of immense use for programmers. Resources - Wikipedia Technical details

Analysis of Algorithms Why do we need to analyse algorithms? Well,every algorithm uses up resources and to figure out which algorithm is best in its class , we need to find out which algorithm takes up minimum resources while producing the desired results . You might wonder : There must be some way else to analyse and compare algorithms like based on the time it takes to execute, but that is a comparison that is machine dependent . The time taken by an algorithm will depend on the processor of the computer its being executed on . Hence , asymptotic analysis of algorithms is the best way to analyse algorithm. How to analyse algorithms? To analyse algorithms we use "Big-O" notation, here is a video by Harvard explaining Asymptotic Notation And here is an incredible text tutorial - Analysis For any queries leave a comment below and if you like the content, hit subscribe on top of the page to stay in the loop for further posts

Why do we study Algorithms First of all , what exactly are Algorithms? According to wikipedia, Algorithms are defined as - An unambiguous specification of how to solve a class of problems. Well,that is pretty accurate but let me break it down: I would call it a set of instructions to complete a certain task but on the condition that the instructions are precise enough for a computer to follow. Algorithms affect every sphere of our lives, they exist in every domain in our world. Why do we need to study Algorithms ? Here's why, we learn from other people's experience.When we study algorithms, We discover new algorithm design and problem solving techniques We see real life examples of the algorithm techniques by learning different algorithms. Studying Algorithms can help us take our coding skills to the next level as these algorithms provide an efficient way of accomplishing a task.

Project Ideas for Python Well , python is an extremely versatile language , several different types of projects can be made in python from Graphical user interfaces to Web apps. It being a language with a very extensive standard library has a lot of potential. Project Ideas: Web Development Using python frameworks like Django , Flask , Web2py etc ,a web application or a website can be developed very easily. But to make a project first you will have to learn the framework you choose. Frameworks : Flask - Flask Mega Tutorial Django - Video Tutorial Web2py - Tutorialspoint-Web2py Website Ideas : Notes app Blog To do list Voting App Twitter Clone (fairly complex) Games Python can be used to develop games using pygame . It is very simple to write games in python in pygame and really anyone with basic python skills can get a game up and running in a very short time. Game examples : Flappy Bird 2048 Tic-Tac-Toe Desktop GUI (Graphical User Interface...

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