# DP problem

**URL:** <https://discuss.codechef.com/t/dp-problem/103516>\
**Category:** help\
**Created:** [October 7, 2022, 12:52pm UTC](https://discuss.codechef.com/t/dp-problem/103516 "2022-10-07T12:52:53Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![codespeed](https://discuss.codechef.com/user_avatar/discuss.codechef.com/codespeed/32/24644_2.png) [@codespeed](https://discuss.codechef.com/u/codespeed)\
**Post date:** [October 7, 2022, 12:52pm UTC](https://discuss.codechef.com/t/dp-problem/103516/1 "2022-10-07T12:52:53Z")

</div>

Hi,

I recently came across this problem in an online hiring test.

```auto
Given an integer d, find the number of **pure-number** sequences of length d.

a pure-number sequence is a sequence of digits where any digit (0 - 9) can come at any index i iff -
1. n is 0
2. any divisor of n (except 1) has been placed at an index j ( j < i). 

First number can be anything from 1 to 9.

eg - 246 is a pure number
201 is not a pure number, there is no divisor of 1 behind it.

Return the total number of sequences modulo 1e9 + 7

constraints : 1 <= d <= 1000

```

And here’s what I did

```auto
int dp[1001][1025];
int solve1(int i, int& d, int bitmask) {
    if(i == d) return 1;
    if(dp[i][bitmask] != -1) return dp[i][bitmask];

    int ans = 0;
    // place the current digit
    for(int cur = 0; cur <= 9; cur += 1) {
        // check if any of it's divisors have already been placed
        for(int j = 0; j <= 11; j += 1) {
            if( j == 1 && cur != 1) continue;
            if(bitmask & (1<<j)) {
                if(j == 0 || cur % j == 0) ans = (ans + solve1(i+1, d, bitmask | (1<<cur))) % MOD;
            }
        }
    }

    return dp[i][bitmask] = ans % MOD;
}

void solve(int cs)
{
    memset(dp, -1, sizeof(dp));
    int n;
    cin>>n;

    int ans = 0;
    int bitmask = 0;
    for(int i = 1; i <= 9; i += 1) {
        ans += solve1(1, n, bitmask | (1<<i));
        ans %= MOD;
    }
    cout<<ans<<"\n";

}

```

I am quite sure I have the idea correct, but I couldn’t pass most of the testcases. Any help would be appreciated.

---

<div class="post-metadata">

**Author:** ![whymihere](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@whymihere](https://discuss.codechef.com/u/whymihere)\
**Post date:** [October 7, 2022, 7:43pm UTC](https://discuss.codechef.com/t/dp-problem/103516/2 "2022-10-07T19:43:45Z")

</div>

Updated:  
**@codespeed Your solution fails for n = 3 as it gives 164 while the correct answer is 71** according to the problem.

@codespeed Do tag me if you find any counter example for my solution.

_Update:_ I have changed few things. Like adding vis to f function and changing lookup[1].

**My Solution:**

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int mod = 1e9 + 7;
const int mxn = (1 << 9) + 1;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	vector<vector<int>> lookup(10);
	lookup[1] = {};
	lookup[2] = {2, 4, 6, 8};
	lookup[3] = {3, 6, 9};
	lookup[4] = {4, 8};
	lookup[5] = {5};
	lookup[6] = {6};
	lookup[7] = {7};
	lookup[8] = {8};
	lookup[9] = {9};

	int n; cin >> n;

	int dp[n + 1][mxn];
	memset(dp, -1, sizeof dp);

	function<int(int, int)> f = [&](int i, int bm) -> int {
		if(i == n) return 1;
		if(dp[i][bm] != -1) return dp[i][bm]; 
		int ans = 0;
		if(i == 0) {
			for(int j = 1; j <= 9; j++) {
				ans = (ans + f(i + 1, bm | (1 << j))) % mod;
			}
		} else {
			ans = (ans + f(i + 1, bm | (1 << 0))) % mod;
			int vis = 0;
			for(int j = 1; j <= 9; j++) {
				if((1 << j) & bm) {
					for(int k: lookup[j]) {
						if((vis & (1 << k)) == 0) {
							ans = (ans + f(i + 1, bm | (1 << k))) % mod; 
							vis |= (1 << k);
						}
					}
				}
			}
		}
		return dp[i][bm] = (ans % mod);
	};
	cout << f(0, 0) << '\n';

	return 0;
}

```

---

<div class="post-metadata">

**Author:** ![codespeed](https://discuss.codechef.com/user_avatar/discuss.codechef.com/codespeed/32/24644_2.png) [@codespeed](https://discuss.codechef.com/u/codespeed)\
**Post date:** [October 8, 2022, 4:40am UTC](https://discuss.codechef.com/t/dp-problem/103516/3 "2022-10-08T04:40:09Z")

</div>

@whymihere thanks for your response. But the numbers 10, 11, 12, 13, 14… are invalid. Problem statement says any divisor except 1.  
Answer for n = 2 is 23 only.

---

<div class="post-metadata">

**Author:** ![whymihere](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@whymihere](https://discuss.codechef.com/u/whymihere)\
**Post date:** [October 8, 2022, 4:42am UTC](https://discuss.codechef.com/t/dp-problem/103516/4 "2022-10-08T04:42:38Z")

</div>

Could you list all the possible combination for n = 2? @codespeed

---

<div class="post-metadata">

**Author:** ![codespeed](https://discuss.codechef.com/user_avatar/discuss.codechef.com/codespeed/32/24644_2.png) [@codespeed](https://discuss.codechef.com/u/codespeed)\
**Post date:** [October 8, 2022, 4:48am UTC](https://discuss.codechef.com/t/dp-problem/103516/5 "2022-10-08T04:48:28Z")

</div>

only 10 in top row I suppose, rest you mentioned are fine @whymihere

---

<div class="post-metadata">

**Author:** ![whymihere](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@whymihere](https://discuss.codechef.com/u/whymihere)\
**Post date:** [October 8, 2022, 4:50am UTC](https://discuss.codechef.com/t/dp-problem/103516/6 "2022-10-08T04:50:54Z")

</div>

Changing

```auto
lookup[1] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

```

to

```auto
lookup[1] = {}; // means once we start with 1 only 0's appear after it eg 10, 100, 1000, ...

```

Should work I guess? @codespeed

---

<div class="post-metadata">

**Author:** ![codespeed](https://discuss.codechef.com/user_avatar/discuss.codechef.com/codespeed/32/24644_2.png) [@codespeed](https://discuss.codechef.com/u/codespeed)\
**Post date:** [October 8, 2022, 5:22am UTC](https://discuss.codechef.com/t/dp-problem/103516/7 "2022-10-08T05:22:19Z")

</div>

Yeah sorry for the late reply, needed to understand your solution. Yup what you proposed should solve the problem. Could you also tell me the reason for adding this line

```auto
ans = (ans + f(i + 1, bm | (1 << 0))) % mod;

```

in the else block.

I know I am asking too much, but how would you go around writing a brute force solution for this? Writing a test generator is fairly easy for this, but I need to know the solution is absolutely fine.

---

<div class="post-metadata">

**Author:** ![whymihere](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@whymihere](https://discuss.codechef.com/u/whymihere)\
**Post date:** [October 8, 2022, 5:41am UTC](https://discuss.codechef.com/t/dp-problem/103516/8 "2022-10-08T05:41:53Z")

</div>

@codespeed as 0 can appear after anything right. Similar to 10, 20 is also valid so is 30 and so on.

Some things I changed in my solution.

1. Added vis so that same function in not called multiple time as one digit can have multiple divisor before it.
2. As you pointed out by you only 0 can appear after 1.

I will drop the brute force solution here:

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int mod = 1e9 + 7;
const int mxn = (1 << 9) + 1;

int brute(int n) {
	int ans = 0;
	function<void(vector<int>)> f = [&](vector<int> v) -> void {
		if((int)v.size() == n) {
			// To print all the valid number commnet the section below
			// for(auto& e: v) cout << e; cout << '\n';
			ans++;
			return;
		} 
		if(v.size() == 0) {
			for(int i = 1; i <= 9; i++) {
				v.push_back(i);
				f(v);
				v.pop_back();
			}
		} else {
			v.push_back(0); 
			f(v);
			v.pop_back();
			set<int> seen;
			for(int i = 1; i <= 9; i++) {
				for(auto& e: v) {
					if((e != 1 and e != 0) and i % e == 0 and seen.find(i) == seen.end()) {
						v.push_back(i);
						f(v);
						v.pop_back();
						seen.insert(i);
					}
				}
			}
		}
	};
	f({});
	return ans;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	vector<vector<int>> lookup(10);
	lookup[1] = {};
	lookup[2] = {2, 4, 6, 8};
	lookup[3] = {3, 6, 9};
	lookup[4] = {4, 8};
	lookup[5] = {5};
	lookup[6] = {6};
	lookup[7] = {7};
	lookup[8] = {8};
	lookup[9] = {9};

	int n; cin >> n;

	int dp[n + 1][mxn];
	memset(dp, -1, sizeof dp);

	function<int(int, int)> f = [&](int i, int bm) -> int {
		if(i == n) return 1;
		if(dp[i][bm] != -1) return dp[i][bm]; 
		int ans = 0;
		if(i == 0) {
			for(int j = 1; j <= 9; j++) {
				ans = (ans + f(i + 1, bm | (1 << j))) % mod;
			}
		} else {
			ans = (ans + f(i + 1, bm | (1 << 0))) % mod;
			int vis = 0;
			for(int j = 1; j <= 9; j++) {
				if((1 << j) & bm) {
					for(int k: lookup[j]) {
						if((vis & (1 << k)) == 0) {
							ans = (ans + f(i + 1, bm | (1 << k))) % mod; 
							vis |= (1 << k);
						}
					}
				}
			}
		}
		return dp[i][bm] = (ans % mod);
	};

	cout << "brute = " << brute(n) << '\n';
	cout << "ans = " << f(0, 0) << '\n';

	return 0;
}

```

---

<div class="post-metadata">

**Author:** ![codespeed](https://discuss.codechef.com/user_avatar/discuss.codechef.com/codespeed/32/24644_2.png) [@codespeed](https://discuss.codechef.com/u/codespeed)\
**Post date:** [October 8, 2022, 6:48am UTC](https://discuss.codechef.com/t/dp-problem/103516/9 "2022-10-08T06:48:10Z")

</div>

Thanks for the really neat solutions. I picked up some pretty good techniques from you. Thanks a bunch! @whymihere