Problem: https://www.spoj.com/problems/ACTIV/
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).
IMHO & from what I've been able to see from solutions of other people(inTheProcessOfDebuggingMine) this logic is correct. For various reasons I'm getting a TLE in my solution and getting WA in some testCases that I'm testing myself. I've not been able to debug my code and for that any insight into what might be going wrong is highly appreciated. Thanks!
My Code: https://pastebin.com/fVKmMBdM
Spoj submission ID: 22172501
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