vibster's blog

By vibster, history, 4 years ago, In English

Hey!

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!

ACCEPTED CODE, WA Code

Problem

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.