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...
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...
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.
That's something very important I should have pointed out, thanks :D . When dealing with small alphabets it's nearly Linear memory. When dealing with large you are right, but the problem is that your searching and insertion complexity would do go bad also in that case :D.
But in competitive programming, most of the times we...
Motivation: Given an array of N integers. You have to answer some queries in form (l, r, k). To answer this query you have to print the number of integers less than k in the sub-array array[l .... r].
You should be able to solve the problem in O(log^2 n) per query at least. How? You can use Merge Sort Trees.
Now what is a Merge Sort Tree? Merge Sort Tree is actually a Segment Tree but each node contains a vector. If the range of the node is [l,r] then the vector will contain the elements of array[l...r] but in sorted order.
To solve the above problem we can make a Merge Sort Tree first and go into relevant segments and binary search on the vector that was stored in those nodes to count how many numbers are less than k. This will give O(log^2 n).
I think O(nlog^2 n ) is not an acceptable time limit for this problem. It is only meant to be solved in O(nlog n). I tried writing it using merge sort tree but was getting TLE even with fast io. You can solve it using BIT or persistent segment tree in nlogn time.