Apptica

DP is one of the most important trick used in programming. This article discusses about a variant that can be used to solve problems like how many numbers are there between \(a\) and \(b\) such that they contain a digit \(x\). Now since this one may be easy and you can think of some formula but DP can be used as a very nice approach here. Suppose you have been given a number \(1608\) and you want to enumerate all the numbers which are lesser than or equal to it. This can be done easily using the following process. Let us assume we have four blanks \( ___ ___ ___ ___\) . Now what can be the first digit from left it can be either \(1\) or \(0\). i.e. \(0 ___ ___ ___\) and \(1 ___ ___ ___\) . Now if we have placed \(0\) in the beginning it is a clear observation that we have not made any \(4\) digit number so the second digit can take values \(0\) to \(9\), but if we have placed \(1\) there then the next digit will be always \(0\) to \(6\) or else number will be greater than the re...

Range query problems are generally solved by either Binary Indexed Tree or Segment Tree. But sometimes when total queries are very large then you need some another data structure such that query time is almost constant and prefetching or pre-processing time is \(N log (N)\). The data structure is Sparse Tables. Assume a range query problem where \(10^7\) queries will be asked. Problem Statement :  You are given an array of size \(10^5\) and \(10^7\) queries to find the minimum of all the numbers in range \([L..R]\) then segment tree will be too slow, so we need something very fast. In sparse table we use the concept of binary numbers (Binary Lifting to be specific). The concept is to break down the complete linear array in chunks of powers of 2 and then utilize them to solve the queries. For example - let array indexes be \(0,1,2,3,4\) then break the array in chunks of powers of two as below - \(Row_0 : [0..0], [0..1], [0..3]\) \(Row_1 : [1..1], [1..2]...