InsaneNerd's blog

Getting WA while using Greedy+DP approach in CSES Projects problem
By InsaneNerd, history, 4 years ago, In English

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?

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Your DP is unsound, at least with respect to sorting by end-time. Consider a test case like this one:

3
1 5 1
6 8 2
4 9 4

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 i is 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.

→ Reply