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.
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>usingnamespacestd;intpSequences2(intn,intp,intprev_num){intcount=0;if(n==1){// if its the last number// all subsequent numbers are those that are less than p/prevcount+=(p/prev_num);}else{for(inti_p=1;i_p<=p;i_p++){if(prev_num*i_p<=p){count+=pSequences2(n-1,p,i_p);}else{break;}}}returncount;}intpSequences(intn,intp){intcount=0;// generate all possible first values of sequencecount=pSequences2(n,p,0);returncount;}intmain(){ofstreamfout(getenv("OUTPUT_PATH"));vector<vector<int>>seqs;intn;cin>>n;cin.ignore(numeric_limits<streamsize>::max(),'\n');intp;cin>>p;cin.ignore(numeric_limits<streamsize>::max(),'\n');intresult=pSequences(n,p);fout<<result<<"\n";fout.close();return0;}
P-sequences
You are viewing a single comment's thread. Return to all 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