We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. P-sequences
  5. Discussions

P-sequences

  • ammar_kothari
     + 0 comments

    Hello,

    I don't know how to speed up the runtime of my solution. I think I am missing a way to enumerate all the possible subsequences. If you have any ideas on how I can reduce the runtime, I would really appreciate it.

    One idea I had is to create a map of the parameters (length of sequence, max value, and starting number) that can be used to look up values instead of running through the recursion each time. This seems a little too complicated, but I am currently trying it out.

    Quick Summary of Code: Use recursion to determine the number of subsequences that are valid given a starting number for the sequence. For each recursion, a shorter sequence with a different inint

    #include <bits/stdc++.h>

using namespace std;

int pSequences2(int n, int p, int prev_num) {
    int count = 0;
    if (n == 1) {
        // if its the last number
        // all subsequent numbers are those that are less than p/prev
        count += (p/prev_num);
    }
    else {
        for (int i_p=1; i_p<=p; i_p++) {
            if (prev_num*i_p<=p) {
                count += pSequences2(n-1, p, i_p);
            }
            else {
                break;
            }
        }
    }
    return count;
}


int pSequences(int n, int p) {
    int count = 0;
    // generate all possible first values of sequence
    count = pSequences2(n, p, 0);
    return count;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));
    vector< vector<int> > seqs;

    int n;
    cin >> n;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    int p;
    cin >> p;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    
    int result = pSequences(n, p);
    
    fout << result << "\n";

    fout.close();

    return 0;
}