(c++) How to effectively make ascending sequences (dyn. solution)

Question

I am currently trying to make a program which involves ascending sequences. N is for the size of the sequence and K is the maximum number, for example

Input: 2,3

Output: 6 (1,1 - 1,2 - 1,3 - 2,2 - 2,3 - 3,3)

My current code outputs the right answer however it takes way too much time to get to the right answer. What is the fastest solution of this and how do I do the dynamical solution? Here is the code with the slow solution :

#include<iostream>
using namespace std;
int n,k,cnt=0,mod=1000000007;
int seq(int n, int k, int first, int depth){
   if(depth > n){
       cnt = cnt + 1;
       return cnt;
   }
   else {
       for(int i=first;i<=k;i++){
            seq(n,k,i,depth+1);
       }
   }
   return cnt;
}
int main()
{
    cin>>n>>k;
    cout<<seq(n,k,1,1)%mod<<"\n";
    return 0;
}

In your recursive call, what happens with the returned value? — Some programmer dude, Nov 12 '16 at 09:18
1.0 seconds is the acceptable time. The current time for an example is 1.5 — Nson, Nov 12 '16 at 09:20
Your code here runs instantly for me and shows `6`. As a note, the use of `long long` is really irregular. If you want huge numbers, maybe `int64_t` is what you mean? Normally recursion is a bad way to solve these sorts of problems. Not only would simple loops help, you only have two layers here anyway, but I bet you could solve this algebraically in a much easier way. — tadman, Nov 12 '16 at 09:21
I have problems with the time limit, not the memory limit and I am not sure why. long long shouldn't be a problem — Nson, Nov 12 '16 at 09:24
I need these variables for it to work. Edit : Ohhhh. I understand now xD — Nson, Nov 12 '16 at 09:25
If you're talking about permutations here, all you need to do is compute factorials. This is [a common problem](http://stackoverflow.com/questions/5721796/how-do-you-implement-the-factorial-function-in-c). — tadman, Nov 12 '16 at 09:32
No, this is not permutations. This is *ascending sequences* with allowed repetitions — Nson, Nov 12 '16 at 09:32

score 1 · Accepted Answer · answered Nov 12 '16 at 10:09

I have solved this problem using dynamic programming.

    #include<bits/stdc++.h>
    #define up(j,k,i) for(i=j;i<k;i++)
    #define down(j,k,i) for(i=j;i>k;i--)
    #define pp(n) printf("%lld\n",n)
    #define is(n) scanf("%lld",&n)
    #define ips(n) scanf("%lld",n)
    #define ss(s) scanf("%s",s)
    #define cool 0
    #define pb push_back
    #define mp make_pair
    #define F first
    #define S second
    #define f(i) cout<<i<<endl;
    #define pll pair<lld,lld> 
    #define pi acos(-1)
    #define ds(n,m) scanf("%lld %lld",&n,&m)
    #define ts(n,m,k) scanf("%lld %lld %lld",&n,&m,&k)
    typedef long double ld;
    typedef long long int lld;
    using namespace std;
    const lld M =1e3+7;
    const lld mod=1e9+7;
    const lld infi =LLONG_MAX;
    lld i,j,ans,k,n,x,y,m,mymax=LLONG_MIN,mymin=LLONG_MAX,b,c,z,sum;
    lld dp[M][M],s[M][M];
    int main()
    {
      lld n,k;
      ds(n,k);
      up(1,k+1,i)
      { 
        s[1][i]=1+s[1][i-1];
      }
      up(2,n+1,i)
      {
        up(1,k+1,j)
        {
          s[i][j]=s[i][j-1]+s[i-1][j];

        }
      }
      pp(s[n][k]);

            return 0;
    }

This is perhaps the best solution but it looks too hard to understand it — Nson, Nov 12 '16 at 10:29
I also want to ask why do you have so many functions defined that you do not even use? and variables — Nson, Nov 12 '16 at 10:30

score 0 · Answer 2 · answered Nov 12 '16 at 10:09

You can count sequences S(M) started from number M in range 1..K:

Imagine that you have sequence of N equal numbers M, M, M, M, M (N times)

To make non-descending sequence, you can use L = 0..K-M ones for incrementing sequence members (and all subsequent numbers). For example, using two ones, you can make valid sequence M, M, M+1, M+1, M+2. Note that there are C(L-1, N-1) variants to do this (you may insert N-1 vertical lines between L-1 dots ...|..|.. )

So

   S(M) = Sum{L=0..K-M} (C(L-1,N-1))

and

   A(N, K) = Sum{M=1..K}(S(M))

(c++) How to effectively make ascending sequences (dyn. solution)

2 Answers2