canvas_melody's blog

Greedy vs DP
By canvas_melody, history, 43 hours ago, In English

I sometimes get confused when to use greedy and when to use DP. I have this problem — https://codeforces.me/contest/455/problem/A where I thought my solution which is greedy would be correct but it went wrong on a 100 element array when submitted. I don't seem to find any mistake or failing test case for my solution. Can someone help? My solution: https://codeforces.me/contest/455/submission/299737860

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
43 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by canvas_melody (previous revision, new revision, compare).

→ Reply
»
43 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by canvas_melody (previous revision, new revision, compare).

→ Reply
»
42 hours ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

When a={1, 2, 3, 4} your code prints 5, although it's also possible to first select 4 and delete 3 and then select 2 and delete 1, for a sum of 6.

The main reason is that your code sometimes thinks choosing an element will result in too many elements being deleted, without considering the case that they already are.

I'm not sure there is a greedy solution, but it can definitely be solved with DP.

As for when you should use DP, it's generally used when:

  • You want to calculate the number of ways or minimize/maximize a value
  • (This is how I usually recognize DP problems) You have to make a series of decisions (for example, in the classic coin problem, the decision is which coin to choose next, in knapsack problems the decision is whether to choose the next item or not etc.)

You'll get better at recognizing DP problems with time (even if you solve problems you already knew were DP), because you'll understand these patterns better, so keep practicing!

→ Reply