The solution for 414B can be more efficient regarding memory we dont need 2D dp we can easily do it using 1D dp

we can make in-place changes in the dp array...

as dp[i] (sequences starting with $$$i$$$) only transitions from multiples j where $$$j \ge i$$$, and I iterate $$$i$$$ from $$$1 \to N$$$, fetching dp[j] (where $$$j \gt i$$$) guarantees we are reading the value from the previous step ($$$k-1$$$)

this makes the space complexity from O(n*k) to O(n) only

TC is still O(k*nlog(n))

• runtime — 78ms
• memory — 100KB

int n, k;
cin >> n >> k;

vector<int> dp(n + 1, 1);
int sum = 0;
k--;
while (k > 0)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 2 * i; j <= n; j += i)
        {
            dp[i] = add(dp[i], dp[j]);
        }
    }
    k--;
}
for (int i = 1; i <= n; i++)
{
    sum = add(sum, dp[i]);
}

cout << sum << "\n";

website : https://tesseract-2k26.vercel.app/sandbox

First two questions on website were practice sample questions

contest link : https://mirror.codeforces.com/contests/668703

invitation: https://mirror.codeforces.com/contestInvitation/cdcb0a8dff488daed793fb1d18a36d4056e43ce9

Editorials : https://mirror.codeforces.com/blog/entry/150754

Thanks!

It should have been KERNEL instead of KERNAL :_(

Contest Link : Link

Let;s Go!