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 mod 1,000,000,007).
---------------------------------------------------------------------

Solution

What approach do you have in mind ? I approached it as dynamic programming problem.
Let us consider a function $f_{i,j}$ denoting the number of sequences such that it has size equal to i and it ends at $j$. $A_{1}, A_{2}, A_{3}, A_{4}, .......A_{i}=j | A_{x} \le A_{x+1}$ or $A_{x} mod A_{x+1} != 0$ $\forall x \lt i$

Now let us try to form a recurrence relation for $f_{i,j}$. We know that $f_{i,j}$ can be reached from $f_{i-1,1},f_{i-1,2},f_{i-1,3}.......f_{i-1,j}$ as all these will form valid states. Other than these we also have some states which can land us upto $f_{i,j}$ like any state which is greater than $j$ let’s say p and $j$ does not divide it as in this case $f_{i-1,p}$ can lead us to $f_{i,j}$.

So, if we try to write it mathematically we get a clear idea.
$f_{i,j} = \sum_{t=1}^{t=j}f_{i-1,t} + \sum_{t=j+1}^{t=k}f_{i-1,t} \mid t\ mod\ j !=0$
This seems perfect with only one problem that the time complexity to calculate this recurrence is clearly $O(k)$ and It seems overall complexity of this solution is $O(n.k^2)$ which is an obvious case of Time Limit Exceeded.

Now the question remains is how to reduce it? One observation we can make while seeing the recurrence is what if we do a $\sum_{t=1}^{t=k}f_{i-1,t}$ . This includes all the cases in above recurrence as well as some extra terms like those states of t where $t\ mod \ j == 0$. So in all we need to subtract these cases. Since these cases will be very few like for $t=2$ there will be approximate $k/2$ cases for $t=3$ approximate $k/3$ cases and so on, so overall complexity for each substructure will be $O(logk)$. Check this link for detailed analysis here.

By storing sum of all previous $\sum_{t=1}^{t=k}f_{i-1,t}$ we can get rid of loop. we will need just one loop for iterating over those multiplicants of $j$ greater than j and less than eqaul to $k$ and subtract them from our stored sum . Therefore overall complexity is $O(n.k.logk)$, which is good enough to pass. Let us see the implementation.

include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef vector<int> vi;
typedef vector< vi > vvi;
 
class DivFreed2 {
 public:
 int count(int n, int k) {
  int f[100005][15];
  int sum =0 ; 
  vvi div(100005);
  for(int i=1;i<=k;i++){
   for(int j=2*i ; j<=k ; j+=i){
    if(j%i == 0 ){
     div[i].push_back(j);
    }
   }
  }
  for(int i=1; i<=k ; i++){
   f[i][1] = 1;
  }
  sum = k;
  int newsum=k;
  for(int col=2 ; col<=n ; col++){
   int tmp=sum;
   newsum = 0;
   for(int row = 1; row<=k ; row++){
    for(int t = 0 ; t < div[row].size() ; t++){
     tmp = (tmp - f[div[row][t]][col-1]+mod)%mod;
    }
    f[row][col] = (tmp+mod)%mod;
    tmp = sum;
    newsum =  (newsum+f[row][col])%mod;
   }
   sum = newsum;
  }
  return newsum;
 }
};

I enjoyed solving this problem, I hope you enjoyed it too. See you all in the next post. Thank you.