vibster's blog

By vibster, history, 4 years ago, In English


I've been stuck at this problem for the past 2 days. I came at a DP recurrence DP(i) = 1+DP(i+1)+DP(nextPossibleInterval(i)), where DP(i) represents all possible subsets of classes b/w ith and nth interval(sorted by endTime).

IMO & from what I've been able to see from solutions of other people(inTheProcessOfDebuggingMine) this logic is correct. For some reason I'm getting WA in some testCases that I'm testing myself & while submitting. I've not been able to debug my code and for that any insight into what might be going wrong is highly appreciated. Thanks!



Sample test case:

8 4 9 1 15 2 18 4 5 7 19 14 25 19 20 3 26 -1 Expected Output: 00000017; Actual Output: 00000026

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
2 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Just think this releation:

ll rec(ll l,vl& dp,vl& aa,vl& bb,ll& n){
  if(l==n)return 0;
  if(dp[l]!=-1)return dp[l];
  auto it=lower_bound(aa.begin()+l+1,aa.end(),bb[l]);
  ll ans=rec(l+1,dp,aa,bb,n)%mm;
  ans= ((ans%mm)+1+ (rec(it-aa.begin(),dp,aa,bb,n)%mm))%mm;
  return dp[l]=ans;

  • »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    This guy was in school when he wrote this blog. Now his kids are in school.