CommonLounge is a community of learners who learn together. Get started with the featured resources above, ask questions and discuss related stuff with everyone.
Tricks and Tweaks to code quickly and efficiently
This discussion is for expanding your array of maneuvers needed to code quickly and efficiently.
The first and most important thing that I'd like to discuss about is the C++ STL. Learning it would enable you to code up an assortment of algorithms and complicated data structures in a matter of seconds.
You can learn to use the C++ STL from the following amazing sites:
Studytonight : Contains syntax and examples for most of the STL containers and algorithms.
Sanfoundry : Shows how to implement what you've learnt in complete programs
Topcoder(Highly recommended) : This place teaches yo...
Dynamic programming is a fancy name for storing intermediate results and re-using the stored result instead of re-computing them each time.
Let's see an example of a dynamic programming problem. Once we solve the problem using dynamic programming, the formal technical definitions will be easier to follow.
Problem: You are given a grid of size n \times 2 and n tiles of size 2 \times 1. In how many different ways can you tile the grid such that the entire grid is covered and no tiles overlap. (The tiles look identical to each other. Two ways of tiling are different based on whether the tiles are placed horizontally or vertically).
Example: There are 3 possible ways of tiling a 3 \times 2 grid.
Number Theory is a topic which you will come across frequently in programming contests. I feel this is a topic which has a lot of resources but these resources are scattered. Therefore, I write this tutorial trying to bring in all the best resources together. There are many people who feel I am not good at Math, can I be a good competitive programmer?. This tutorial is for you guys. Don't hesitate to read it as the material here is presented in extremely lucid form and anyone can understand it. Feel free to ask in case you have any doubts.
In many problems especially in problems where the answer can become very very large, you must have found that they ask you to report the answer modulo 10^9+7. Let us learn more about this modulo operator and it's properties.
There is another quick trick to find mod inverse when mod is prime.
Basically, 1/a mod m = a^(m-2) mod m if m is prime (This is derived from Fermat's theorem)
It doesn't work when m is non-prime. What can we do ...
Read more… (73 words)
Read more (73 words)
Binary search: Video tutorial, code and extensions
Binary search is a method for quickly finding a specific target value in a sorted array. It begins by comparing the target value to the middle element of the array. Because the array is sorted, the comparison allows us to determine one-half of the array in which the target cannot lie. The search continues on the remaining half. By doing this repeatedly, we will eventually be left with a search space consisting of a single element, which would be the target value.
It's because if the array or list has the elements unsorted, then we need to sort it first. So the sort time complexity is O(nlogn) and then we use a binary search which takes O(logn). Overall it takes O(nlogn) for unsorted array or list.
If the array given is a sorted array then the search...
Recursion is a fundamental technique used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition.
In computer science, a common method of simplification is to divide a problem into subproblems of the same type. As a computer programming technique, this is called divide and conquer and is key to the design of many important algorithms. Divide and conquer serves as a top-down approach to problem solving, where problems are solved by solving smaller and smaller instances. A contrary approach is Dynamic Programming. This approach serves as a bottom-up approach, where problems are solved by solving larger and larger instances, until the desired size is reached.
It's recommended that you learn mathematical inducti...