Apptica

In the last post i discussed few basics required for DP on digits. Now i am going to explain you a  problem so as to relate to what that post meant.  Problem : Given a range \([L,R]\) , how many numbers are there such that its two adjacent digits form a number which is a perfect square. Solution: Problem asks us to count numbers like \(125\) as \(25\) is a prefect square, \(198\) is not valid as there are no two adjacent digits for which the number is a perfect square.  First of all let us discuss some state variables.  \(pos\) : \(pos\) tells us that you are going to place any digit on this position \(isequal\) : Discussed already in previous post, this tells us whether the number formed till now is equal to the prefix of the limiting number starting from \(1\) to \(pos-1\). For example let us count numbers less than \(1269\) then for the status \(126 __\) , \(isequal\) will be \(1\). \(started\) : This tells us whether number formation is start...

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