Skip to main content

Posts

Topcoder SRM 684 DivFreed2 Div 2 level 2

Hello all, today I want to share a problem which comes in many forms of counting the number of sequences subject to some constraints on the elements of the sequence. The problem goes like following. link to problem statement ------------------------------------------------------------------- Problem Statement Hero likes some arrays. The arrays he likes are the arrays that have all of the following properties: The length of the array is n . Each element is an integer between 1 and k , inclusive. Whenever A and B are two consecutive elements of the array (in this order), we have (A <= B) or (A mod B != 0). For example, suppose n =4 and k =7. Hero will like the array {1,7,7,2} because it has the right length, all elements are in the correct range, 1 <= 7, 7 <= 7, and 7 mod 2 != 0. Hero will not like the array {4,4,4,2}. You are given the ints n and k . Let X be the number of different arrays Hero likes. Compute and return the value (X mo
Recent posts

Solving CodeChef June Long Challenge Problem "PRMQ" using Segment Tree

Hello folks. Hope you are having a good time. I wanted to share my solution to CodeChef June '17 problem   PRMQ . Though there might be many solutions possible to this problem, I will walk you through a Segment-Tree solution for this. Approach There are nearly 78,000 prime numbers between 1 and 10^6, so in worst case a number in this query range L to R can have maximum of 8 prime numbers as the number of factors. Why 8 see 2*3*5*7*11*13*17*19 > 10^6 . And the root node can have maximum of 78,000 nodes with each prime number in the leaf node merging to form the root node. Now let us think what we should store in a node of segment tree. We may need the following information:- 1. The element of the array so as to compute their prime factors. 2. Some way to combine the factors of each element as key and their count as value, suppose we are having 2 elements say 8 and 9 so when we merge these node in the tree, we have got 2 as a factor with count 3 and 3 as a factor with

Modular Exponentiation

Just wanted to introduce you to very basic concept of Modular Exponentiation through a problem,  Big Mod . We need to calculate A^B % M for large inputs. For a second let's forget about A^B  % M and think about A^B only and say A^B lies within the range of long long int and B is less than 10^7. A basic brute force approach to calculate A^B will be to loop through 1 to B and multiply A every time. The time complexity of this approach is O(n). This is perfect on current constraints but what happens if I change the constraint on B and raise it to 10^12 or so. Now  this approach will give a TLE. An efficient approach is needed. O(n) is not sufficient. We will use a recursive approach for this. Suppose I want to calculate A^B but if B is even, I can calculate A^(B/2) and multiply it to itself, and the way to calculate A^(B/2) is to calculate A^(B/4) and so on you get the idea. But what if B is not even, no problem,  B-1 will be even do the same except replace B with B-1 and separ