Getting WA while using Greedy+DP approach in CSES Projects problem

Revision en1, by InsaneNerd, 2020-09-10 13:18:41

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.

My Code can be seen here

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?

Tags #dynamic programming, dp, greedy, cses

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English InsaneNerd 2020-09-10 13:18:41 1129 Initial revision (published)