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

Sort 13 Discussions, By:

  • alex_fotland
     + 0 comments

    This problem is definitely easier than a fair number of the medium-rated DP problems. At least in this case it's obvious how to relate the desired solution to the solution to a smaller version of the problem. Sure, you need to figure out how to condense some of the sub-problems together so you can handle large P without running out of time or memory, but that's a much more straightforward problem.

  • thecodingsoluti2
     + 0 comments

    Here is P-sequences problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-p-sequences-problem-solution.html

  • brunopaulsen
     + 0 comments

    The algorithm is correct

    Still it will not work for very large number TestCases: 10,11,13,16,17 and 18. They exceed computational capacity of 53bit integers. Then, a special multiplication procedure will be needed in order to get the correct modulus without errors induced by those really really really really big numbers,,,,,

    function pSequences(n, p) {
    // Write your code here
    const MOD = 1000000000+7
    let root = parseInt(Math.sqrt(p)),
        last = root*2-((root*(root+1)>p)?2:1),
        qtty = [], val=[], calc=[], i=0, j=last, accum=0, size=last+1
    while (accum < p) calc[j--] = (accum += (val[i] = (qtty[i++] = (parseInt(p/parseInt(p/(accum+1))) - accum))))
    while(n-->=2) {
        let next = new Array(size)
        accum = 0
        for(i=0,j=last;i<=last;i++,j--) next[j] = (accum = (accum + (val[i] = ((qtty[i] * calc[i])%MOD)))%MOD)
        calc = next
    }
    return accum % MOD
}

  • er_vikramsnehi
     + 0 comments

    In JavaScript, 

    var result=0;
    for(var i=1;i<=n;i++)
    {
        for(var j=1;j<=n;j++)
            {
                if(i*j<=p)
                {
                    result = result+1;
                }
            }
    }
    return(result)

    something is not working here.

  • 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;
}
Load more conversations