I was doing Projects problem from CSES ProblemSet.
I was trying with something like a mixture of Greedy+DP.
Firstly I sorted the projects based on the ending time of the project just like the classic Activity Selection Problem.
On these projects, I applied DP based on the time elapsed. If it is possible to include the (i+1)th activity try it by both including and excluding it. If it is not possible then just skip the (i+1)th project and move to the next one.
The CSES DP Editorial by icecuber uses a totally different approach, I wanted to know is my approach optimal or not? My code was able to pass 10/13 test cases. The three test cases left were having 20000 projects, hence, I was not able to determine where did it went wrong.
Is there some mathematical proof against my method or some other error?
Your DP is unsound, at least with respect to sorting by end-time. Consider a test case like this one:
The correct output should be 4, but, if I understand correctly, your code will output either 3 or 5 depending on the order in which the two recursive calls are made when
iis 0.EDIT: Sorry if this was an unwanted necro-post! I saw one comment 90 minutes ago and didn't notice the blog was months old. Takeaway: The DP memo should usually have the same inputs as the solve function it memoizes.